《跳跃链表的设计与实现-数据结构与算法综合设计报告书》由会员分享，可在线阅读，更多相关《跳跃链表的设计与实现-数据结构与算法综合设计报告书（19页珍藏版）》请在金锄头文库上搜索。
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软件判错、抗压及优化需求分析22.3 软件开发环境需求分析22.3.1 系统环境22.3.2 编程语言22.3.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. 参考文献151.前言在确定了本次课设的题目后，在本着提高专业技能，巩固基础知识的前提下，通过查阅资料，最终选择了使用C语言+GTK图形化界面库来完成本次课设，在确定了之后，便去图书馆找了相关书籍，在简单了解了面向对象的思想之后，将本次程序设计分为了四部分：全局界面布局及核心思想分析，代码实
4、现，程序调试及优化，课程设计报告书书写。在界面布局上，使用菜单栏，功能之间相互切换，每个功能有相应的界面的布局方式，界面使用简约风格设计，在算法刷新界面上有所创新，使用全局变量保存界面相应构件的指针数据，动态刷新界面。然后开始书写代码，由于首次接触GTK及面向对象的思想，在书写代码时遇到了N多问题，但在查阅相关书籍和网上搜索的帮助下，写出了较为满意的界面，然而在跳跃链表地核心算法上相比较界面花的时间却较少，但相应的功能是比较全面的，性能测试的大数据测试并输出文件，还有各种数据检查，弹窗警告，高效算法等无一不是程序亮点。在完成了基本功能之后，进入后期优化，通过网上学习，对界面加入了背景图片，并仔
5、细调试试用了多种界面风格之后，选用灰色磨砂背景，高亮显示数据提示等，使得界面进一步优化，提高了用户体验。对代码进行了添加注释，多次使用的代码段封装函数等操作。因为本次课设开发环境为linux，且在运行时需要GTK库支持，所以在查阅网上资料后，对程序进行了软件封装打包，使得其可在windows下安装并运行。2.需求分析2.1软件功能需求分析问题描述：链表存在的一个缺陷是：在有序链表中查找一个元素是否存在，需要从头开始，依 次顺序查找。跳跃链表是有序链表的一个变种，可以进行非顺序查找。 该题目要求实现一个跳 跃链表，并对其与一般链表进行比较测试。 基本要求：（1）设计实现跳跃链表，用于高效地访问链
6、表中的元素。 （2）包括的基本操作：建立、查找、插入、删除等操作。 （3）将其效率和链表、有序链表的效率进行比较。 （4）输入：数据是随机产生；非随机产生两种情况 更高要求（5）将跳跃链表的操作封装为 DLL。 （6）UI 设计与实现。据题目要求，本次课设有如下基本功能：随机创建，按值创建，查找，插入，按值删除，按序删除，性能测试，全层输出，定层输出。在性能测试上使用大数据测试并将测试结果输出到文件。2.2软件判错、抗压及优化需求分析作为一款交互界面软件，软件的判错能力是评判一款软件成功与否的重要标志，本软件使用全程输入数据分析，弹窗错误警告的判错处理机制，在不影响用户操作体验的前提下，尽可能
7、的提高操作的灵活性及准确性，使得用户在输入错误数据的情况下，软件大概率不会奔溃，判错率高达90%。在软件抗压方面，因为界面输出方面的限制，数据量在演示的情况下，正常输出最高可达16链表数据。在性能测试抗压方面，使用大数据测试，创建速度略显缓慢，但其他功能操作体验良好，数据输出正常，速度明显快于普通有序链表。在界面优化上，使用简约风格创作，并加入灰色磨砂背景图片，高亮显示操作提示，操作成功或失败有相应颜色显示，一目了然，后期美化弹窗警告，并加入系统提示音。使得用户体验得到进一步提升。2.3 软件开发环境需求分析2.3.1 系统环境本次课程设计软件开发全程使用Deban的kali Rolling系
8、统创作，选择此系统的原因有以下几点，一是因为在windows和linux上搭建GTK环境，linux更为容易，而且开源的linux环境操作更为灵活，二是在windows下操作的界面优化无法和linux媲美。第三点是因为linux系统在电脑上的配置完善，想进一步熟悉linux下的编程操作，gdb调试，vim操作等技术。综上所述，最终选择linux作为本次课设的操作系统。2.3.2 编程语言本次软件设计语言使用C语言编程，在其他语言不够熟悉的情况下，使用C语言减少了课设的复杂度，并且使用了C语言之后，与所选GTK库完美兼容，使得学习和使用GTK事半功倍。C语言是一种计算机程序设计语言，它既具有高级
9、语言的特点，又具有汇编语言的特点，C语言应用范围广泛，具备很强的数据处理能力，它具有简洁紧凑、灵活方便、运算符丰富、数据类型丰富等优点。C语言有一个突出的优点就是适合于多种操作系统，可移植性好，并具备很强的数据处理能力，因此适于编写系统软件。综上，本次课程软件设计使用C语言编写。2.3.3 附加库需求由于课程软件设计对于UI界面的要求，本次课程设计选择使用C语言下的图形化界面库GTK进行创作，选择GTK库有以下原因， GTK库是使用C语言写的，与C语言不会有任何兼容性的问题，它简单易用，对开发人员和用户来说都是这样而且它设计良好、灵活而可扩展，是一款自由软件而且有一个自由的开放源码许可，并且它
10、和C语言一样是可移植的，诸多原因就选择了它。GTK(GIMP Toolkit)是一套跨多种平台的图形工具包。虽然最初是为GIMP写的，但早已发展为一个功能强大、设计灵活的通用图形库，在被GNOME选中之后使得GTK+广为流传，成为Linux下开发图形界面的应用程序的主流开发工具之一。2.4软件运行环境需求分析需求选项要求CPUIntel Core i3 及以上处理器或具有相同性能其他厂家的cpu内存推荐2 G 或以上硬盘空间至少50 M 空间操作系统Windows2000以上或linux系统均可附加库GTK图形化界面库其他无 表2-13.设计思想与实现3.1 软件系统全局分析本次软件全局使用一
11、个功能包含一模板一处理函数的构思方式，在数据处理上多次使用全局变量，如全局变量保存Top头指针，指针数组全局变量动态刷新界面，全局变量标志flag等。在界面代码中的回调函数操作数据，又在数据函数中动态的在界面上显示结果。使用.h文件封装了结构体指针数组和散列表结构体。在界面刷新上使用全局变量保存数组指针，动态的隐藏取消映射构件，使得在刷新上有了很大的机动性，可以避免将菜单刷走，使得动态更新页面简单高效。在数据处理方面，全局使用Top指针保存头指针。开始3.2 软件流程图Top主界面初始化NULL按值创建随机创建Top各界面操作结束图3-1 哦哦哦、3.3程序功能流程图按值创建随机创建用户输入产
12、生随机数据个数创建主函数输出Top数据界面输出查找用户输入数据警告判断输入输入插入错误Mai gtk_main();相应处理函数删除 正确3.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);/菜单条加
13、入vboxgtk_container_add(GTK_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-c
14、om_num+=label1;gtk_box_pack_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 failed_p(char *text)/数据错误弹窗/输入：char *text：所显示的弹窗警告信息GtkWidget *dialog = gtk_message_dialog_new
