跳跃链表的设计与实现-数据结构与算法综合设计报告书.docx

1、数据结构与算法课程设计说明书题 目： 跳跃表的实现与应用 学 院： 计算机与信息安全学院 专 业： 姓 名： 学 号： 指导教师： 2017 年 3 月 15 日成绩评定标准及成绩1、 能按照格式进行写作，无抄袭现象（10 分） 2、 报告内容行文通畅，有条理性，无错别字，结构严谨。（10分） 3、 能够按照数据结构课设的格式要求、排版要求和字数要求等，有需求分析，系统分析，详细设计，关键技术的介绍和参考文献。（10 分） 4、 在验收过程中，能合理的回答问题（20 分） 5、 软件能正常运行，实现所提出的功能（40 分） 6、 软件代码规范性较好（5 分） 7、 具有自己的创新或特色（5 分

2、） 总成绩： 摘 要本次课程设计的内容是跳跃链表，跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树。本篇文档共由七大部分构成，分别是前言、需求分析、设计思想与流程、软件运行演示，问题与解决、结语和参考文献。本系统共实现了跳跃链表地创建，插入，删除，查找，输出等基本功能，还实现了性能测试并将测试数据输出到文件。在界面制作上使用 C 语言+GTK 图形化库制作，并加入了后期界面优化，使其具有了更好的用户体验。关键词：界面，GTK，跳表，简约风格目 录1.前言 .12.需求分析 .12.1 软件功能需求分析 .12.2 软 件 判 错 、 抗 压 及 优 化 需 求 分 析 .

3、22.3 软件开发环境需求分析 .22.3.1 系统环境 .22.3.2 编程语言 .22.3.3 附加库需求 .22.4 软件运行环境需求分析 .33.设计思想与实现 .33.1 软件系统全局分析 .33.2 软件流程图 .33.3 程序功能流程图 .43.3 核心代码分析 .51、界面 .52、数据处理 .63.4创新思想 .114.软件运行测试与界面展示 .125.问题与解决 .145.1 界面更新问题 .145.2 输出操作难点 .156. 结语 .157. 参考文献 .1511.前 言在确定了本次课设的题目后，在本着提高专业技能，巩固基础知识的前提下，通过查阅资料，最终选择了使用 C

4、 语言+GTK 图形化界面库来完成本次课设，在确定了之后，便去图书馆找了相关书籍，在简单了解了面向对象的思想之后，将本次程序设计分为了四部分：全局界面布局及核心思想分析，代码实现，程序调试及优化，课程设计报告书书写。在界面布局上，使用菜单栏，功能之间相互切换，每个功能有相应的界面的布局方式，界面使用简约风格设计，在算法刷新界面上有所创新，使用全局变量保存界面相应构件的指针数据，动态刷新界面。然后开始书写代码，由于首次接触 GTK 及面向对象的思想，在书写代码时遇到了 N 多问题，但在查阅相关书籍和网上搜索的帮助下，写出了较为满意的界面，然而在跳跃链表地核心算法上相比较界面花的时间却较少，但相应

5、的功能是比较全面的，性能测试的大数据测试并输出文件，还有各种数据检查，弹窗警告，高效算法等无一不是程序亮点。在完成了基本功能之后，进入后期优化，通过网上学习，对界面加入了背景图片，并仔细调试试用了多种界面风格之后，选用灰色磨砂背景，高亮显示数据提示等，使得界面进一步优化，提高了用户体验。对代码进行了添加注释，多次使用的代码段封装函数等操作。因为本次课设开发环境为 linux，且在运行时需要 GTK 库支持，所以在查阅网上资料后，对程序进行了软件封装打包，使得其可在 windows 下安装并运行。2.需 求 分 析2.1 软 件 功 能 需 求 分 析问题描述：链表存在的一个缺陷是：在有序链表中

6、查找一个元素是否存在，需要从头开始，依 次顺序查找。跳跃链表是有序链表的一个变种，可以进行非顺序查找。 该题目要求实现一个跳 跃链表，并对其与一般链表进行比较测试。 基本要求：（1）设计实现跳跃链表，用于高效地访问链表中的元素。 （2）包括的基本操作：建立、查找、插入、删除等操作。 （3）将其效率和链表、有序链表的效率进行比较。 （4）输入：数据是随机产生；非随机产生两种情况 更高要求（5）将跳跃链表的操作封装为 DLL。 （6）UI 设计与实现。据题目要求，本次课设有如下基本功能：随机创建，按值创建，查找，插入，按值删除，按序删除，性能测试，全层输出，定层输出。在性能测试上使用大数据测试并将

7、测试结果输出到文件。22.2 软 件 判 错 、 抗 压 及 优 化 需 求 分 析作为一款交互界面软件，软件的判错能力是评判一款软件成功与否的重要标志，本软件使用全程输入数据分析，弹窗错误警告的判错处理机制，在不影响用户操作体验的前提下，尽可能的提高操作的灵活性及准确性，使得用户在输入错误数据的情况下，软件大概率不会奔溃，判错率高达 90%。在软件抗压方面，因为界面输出方面的限制，数据量在演示的情况下，正常输出最高可达 16 链表数据。在性能测试抗压方面，使用大数据测试，创建速度略显缓慢，但其他功能操作体验良好，数据输出正常，速度明显快于普通有序链表。在界面优化上，使用简约风格创作，并加入灰

8、色磨砂背景图片，高亮显示操作提示，操作成功或失败有相应颜色显示，一目了然，后期美化弹窗警告，并加入系统提示音。使得用户体验得到进一步提升。2.3 软 件 开 发 环 境 需 求 分 析2.3.1 系 统 环 境本次课程设计软件开发全程使用 Deban 的 kali Rolling 系统创作，选择此系统的原因有以下几点，一是因为在 windows 和 linux 上搭建 GTK 环境，linux 更为容易，而且开源的 linux 环境操作更为灵活，二是在 windows 下操作的界面优化无法和 linux 媲美。第三点是因为 linux 系统在电脑上的配置完善，想进一步熟悉 linux 下的编程

9、操作，gdb 调试， vim 操作等技术。综上所述，最终选择 linux 作为本次课设的操作系统。2.3.2 编 程 语 言本次软件设计语言使用 C 语言编程，在其他语言不够熟悉的情况下，使用 C 语言减少了课设的复杂度，并且使用了 C 语言之后，与所选 GTK 库完美兼容，使得学习和使用 GTK 事半功倍。C语言是一种计算机程序设计语言，它既具有高级语言的特点，又具有汇编语言的特点，C 语言应用范围广泛，具备很强的数据处理能力，它具有简洁紧凑、灵活方便、运算符丰富、数据类型丰富等优点。C 语言有一个突出的优点就是适合于多种操作系统，可移植性好，并具备很强的数据处理能力，因此适于编写系统软件。

10、综上，本次课程软件设计使用 C 语言编写。2.3.3 附 加 库 需 求由于课程软件设计对于 UI 界面的要求，本次课程设计选择使用 C 语言下的图形化界面库 GTK进行创作，选择 GTK 库有以下原因， GTK 库是使用 C 语言写的，与 C 语言不会有任何兼容性的问题，它简单易用，对开发人员和用户来说都是这样而且它设计良好、灵活而可扩展，是一款自由软件而且有一个自由的开放源码许可，并且它和 C 语言一样是可移植的，诸多原因就选择了它。3GTK(GIMP Toolkit)是一套跨多种平台的图形工具包。虽然最初是为 GIMP 写的，但早已发展为一个功能强大、设计灵活的通用图形库，在被 GNOM

11、E 选中之后使得 GTK+广为流传，成为 Linux 下开发图形界面的应用程序的主流开发工具之一。2.4 软 件 运 行 环 境 需 求 分 析需求选项 要求CPU Intel Core i3 及以上处理器或具有相同性能其他厂家的 cpu内存 推荐 2 G 或以上硬盘空间 至少 50 M 空间操作系统 Windows2000 以上或 linux 系统均可附加库 GTK 图形化界面库其他 无 表 2-13.设 计 思 想 与 实 现3.1 软 件 系 统 全 局 分 析本次软件全局使用一个功能包含一模板一处理函数的构思方式，在数据处理上多次使用全局变量，如全局变量保存 Top 头指针，指针数组全

12、局变量动态刷新界面，全局变量标志 flag 等。在界面代码中的回调函数操作数据，又在数据函数中动态的在界面上显示结果。使用.h 文件封装了结构体指针数组和散列表结构体。在界面刷新上使用全局变量保存数组指针，动态的隐藏取消映射构件，使得在刷新上有了很大的机动性，可以避免将菜单刷走，使得动态更新页面简单高效。在数据处理方面，全局使用 Top 指针保存头指针。3.2 软 件 流 程 图NULL开始主界面初始化Top随机创建 按值创建4图 3-1 哦哦哦、3.3 程 序 功 能 流 程 图数据界面输出错误正确Top 各界面操作结束随机创建产生随机数据个数创建主函数Top按值创建用户输入删除插入查找输出

13、用户输入数据相应处理函数判断输入输入Mai gtk_main();警告53.3 核 心 代 码 分 析1、 界 面A基本构建语句GtkWidget *main_window;/窗体GtkWidget *MenuBar;/菜单条GtkWidget *box;/定义组合框GtkWidget *Menu;/*定义子菜单*/GtkWidget *toolbar;/*定义工具条*/GtkWidget *image;/*定义图片构件*/gtk_box_pack_start(GTK_BOX(box),MenuBar,FALSE,FALSE,2);/菜单条加入vboxgtk_container_add(GTK

14、_CONTAINER(main_window),box);gtk_widget_show_all(main_window);所有的界面构建使用标签，组合框，文本框，下拉式菜单构成，在外面附加弹窗警告函数，使得整体功能全面，图片构件的使用加入了背景图片。B 一般性模板函数GtkWidget *moudle_lable(GtkWidget *widget,char *text,int i)/标签/输入参数：标签加入的构建，标签显示的内容GtkWidget *label1 = gtk_label_new(text);wm-componentwm-com_num+=label1;gtk_box_pac

15、k_start(GTK_BOX(widget),label1,FALSE,FALSE,5);if(i=1)gtk_widget_show(label1);return label1;这是标签的一般性模板函数，输入参数为：GtkWidget *widget：需要加入的父构件指针char *text：标签内容int i：是否现在就显示标签（0为否，1为是）返回值为此lable标签的指针。此函数的作用是简化代码量，使得重复的代码封装调用，提高效率，由于按钮，组合框等参数过于杂乱，无法构造出一般性模板函数，且其使用量没有标签庞大，所以对程序简化帮助不大，故只构造标签的模板函数C弹窗警告函数void f

16、ailed_p(char *text)/数据错误弹窗6/输入：char *text：所显示的弹窗警告信息GtkWidget *dialog = gtk_message_dialog_new (GTK_WINDOW (wm-component1),GTK_DIALOG_MODAL, GTK_MESSAGE_INFO, GTK_BUTTONS_CLOSE,text);gtk_window_set_position (GTK_WINDOW (dialog), GTK_WIN_POS_CENTER);/设置窗口的位置 gtk_dialog_run (GTK_DIALOG (dialog);/运行上面创

17、建的窗口 gtk_widget_destroy (dialog);/释放窗口的界面内存 此函数使用弹窗的方式告知相应的警告，重复利用率高。D初始化窗口函数Void initialise()/初始化窗口int i=2;for(;icom_num;i+)gtk_widget_hide(wm-componenti);gtk_widget_destroyed(wm-componenti,NULL);wm-com_num=2;此函数作用为将除菜单、组合框、主窗口以外的所有组件取消映射并撤销，是界面代码的核心，动态刷新2、 数 据 处 理A升级版随机数生成器void Stoch_plus(int n,int num,int* num_list,int *n_list)int i,j=0,w;Phashtable phd;phd=create_empty(n,n_list);for(i=0;im;i+)/获取随机数if(phd-elementi.key!=0j+;free(phd);参数介绍：