资源描述
数据结构与算法课程设计说明书题 目： 跳跃表的实现与应用 学 院： 计算机与信息安全学院 专 业： 姓 名： 学 号： 指导教师： 2017年3月15日成绩评定标准及成绩1、 能按照格式进行写作，无抄袭现象（10分）2、 报告内容行文通畅，有条理性，无错别字，结构严谨。（10分）3、 能够按照数据结构课设的格式要求、排版要求和字数要求等，有需求分析，系统分析，详细设计，关键技术的介绍和参考文献。（10分）4、 在验收过程中，能合理的回答问题（20分）5、 软件能正常运行，实现所提出的功能（40分）6、 软件代码规范性较好（5分）7、 具有自己的创新或特色（5分） 总成绩： 摘 要 本次课程设计的内容是跳跃链表，跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树。本篇文档共由七大部分构成，分别是前言、需求分析、设计思想与流程、软件运行演示，问题与解决、结语和参考文献。本系统共实现了跳跃链表地创建，插入，删除，查找，输出等基本功能，还实现了性能测试并将测试数据输出到文件。在界面制作上使用C语言+GTK图形化库制作，并加入了后期界面优化，使其具有了更好的用户体验。关键词：界面，GTK，跳表，简约风格目录1.前言12.需求分析12.1软件功能需求分析12.2软件判错、抗压及优化需求分析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. 参考文献151.前言在确定了本次课设的题目后，在本着提高专业技能，巩固基础知识的前提下，通过查阅资料，最终选择了使用C语言+GTK图形化界面库来完成本次课设，在确定了之后，便去图书馆找了相关书籍，在简单了解了面向对象的思想之后，将本次程序设计分为了四部分：全局界面布局及核心思想分析，代码实现，程序调试及优化，课程设计报告书书写。在界面布局上，使用菜单栏，功能之间相互切换，每个功能有相应的界面的布局方式，界面使用简约风格设计，在算法刷新界面上有所创新，使用全局变量保存界面相应构件的指针数据，动态刷新界面。然后开始书写代码，由于首次接触GTK及面向对象的思想，在书写代码时遇到了N多问题，但在查阅相关书籍和网上搜索的帮助下，写出了较为满意的界面，然而在跳跃链表地核心算法上相比较界面花的时间却较少，但相应的功能是比较全面的，性能测试的大数据测试并输出文件，还有各种数据检查，弹窗警告，高效算法等无一不是程序亮点。在完成了基本功能之后，进入后期优化，通过网上学习，对界面加入了背景图片，并仔细调试试用了多种界面风格之后，选用灰色磨砂背景，高亮显示数据提示等，使得界面进一步优化，提高了用户体验。对代码进行了添加注释，多次使用的代码段封装函数等操作。因为本次课设开发环境为linux，且在运行时需要GTK库支持，所以在查阅网上资料后，对程序进行了软件封装打包，使得其可在windows下安装并运行。2.需求分析2.1软件功能需求分析问题描述：链表存在的一个缺陷是：在有序链表中查找一个元素是否存在，需要从头开始，依 次顺序查找。跳跃链表是有序链表的一个变种，可以进行非顺序查找。 该题目要求实现一个跳 跃链表，并对其与一般链表进行比较测试。 基本要求：（1）设计实现跳跃链表，用于高效地访问链表中的元素。 （2）包括的基本操作：建立、查找、插入、删除等操作。 （3）将其效率和链表、有序链表的效率进行比较。 （4）输入：数据是随机产生；非随机产生两种情况 更高要求（5）将跳跃链表的操作封装为 DLL。 （6）UI 设计与实现。据题目要求，本次课设有如下基本功能：随机创建，按值创建，查找，插入，按值删除，按序删除，性能测试，全层输出，定层输出。在性能测试上使用大数据测试并将测试结果输出到文件。2.2软件判错、抗压及优化需求分析作为一款交互界面软件，软件的判错能力是评判一款软件成功与否的重要标志，本软件使用全程输入数据分析，弹窗错误警告的判错处理机制，在不影响用户操作体验的前提下，尽可能的提高操作的灵活性及准确性，使得用户在输入错误数据的情况下，软件大概率不会奔溃，判错率高达90%。在软件抗压方面，因为界面输出方面的限制，数据量在演示的情况下，正常输出最高可达16链表数据。在性能测试抗压方面，使用大数据测试，创建速度略显缓慢，但其他功能操作体验良好，数据输出正常，速度明显快于普通有序链表。在界面优化上，使用简约风格创作，并加入灰色磨砂背景图片，高亮显示操作提示，操作成功或失败有相应颜色显示，一目了然，后期美化弹窗警告，并加入系统提示音。使得用户体验得到进一步提升。2.3 软件开发环境需求分析2.3.1 系统环境本次课程设计软件开发全程使用Deban的kali Rolling系统创作，选择此系统的原因有以下几点，一是因为在windows和linux上搭建GTK环境，linux更为容易，而且开源的linux环境操作更为灵活，二是在windows下操作的界面优化无法和linux媲美。第三点是因为linux系统在电脑上的配置完善，想进一步熟悉linux下的编程操作，gdb调试，vim操作等技术。综上所述，最终选择linux作为本次课设的操作系统。2.3.2 编程语言本次软件设计语言使用C语言编程，在其他语言不够熟悉的情况下，使用C语言减少了课设的复杂度，并且使用了C语言之后，与所选GTK库完美兼容，使得学习和使用GTK事半功倍。C语言是一种计算机程序设计语言，它既具有高级语言的特点，又具有汇编语言的特点，C语言应用范围广泛，具备很强的数据处理能力，它具有简洁紧凑、灵活方便、运算符丰富、数据类型丰富等优点。C语言有一个突出的优点就是适合于多种操作系统，可移植性好，并具备很强的数据处理能力，因此适于编写系统软件。综上，本次课程软件设计使用C语言编写。2.3.3 附加库需求由于课程软件设计对于UI界面的要求，本次课程设计选择使用C语言下的图形化界面库GTK进行创作，选择GTK库有以下原因， GTK库是使用C语言写的，与C语言不会有任何兼容性的问题，它简单易用，对开发人员和用户来说都是这样而且它设计良好、灵活而可扩展，是一款自由软件而且有一个自由的开放源码许可，并且它和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 软件系统全局分析本次软件全局使用一个功能包含一模板一处理函数的构思方式，在数据处理上多次使用全局变量，如全局变量保存Top头指针，指针数组全局变量动态刷新界面，全局变量标志flag等。在界面代码中的回调函数操作数据，又在数据函数中动态的在界面上显示结果。使用.h文件封装了结构体指针数组和散列表结构体。在界面刷新上使用全局变量保存数组指针，动态的隐藏取消映射构件，使得在刷新上有了很大的机动性，可以避免将菜单刷走，使得动态更新页面简单高效。在数据处理方面，全局使用Top指针保存头指针。开始3.2 软件流程图Top主界面初始化NULL按值创建随机创建Top各界面操作结束图3-1 哦哦哦、3.3程序功能流程图按值创建随机创建用户输入产生随机数据个数创建主函数输出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);/菜单条加入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-com_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 (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);/运行上面创建的窗口 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;inum;i+)w=Search_inseart(phd,num_listi);for(i=0;im;i+)/获取随机数if(phd-elementi.key!=0&phd-elementi.key!=-1)num_listj=i;j+;free(phd);参数介绍：int n：申请散列表节点总数 int num：需要数据个数。int* num_list:用来存储所选出来的数据int *n_list：用来传进去选择数据的所有数据功能：实现传入一些数据，去掉最大最小并随机选取一些数据，然后输出选取出来的数据的功能。本函数使用双散列表选取随机数据的方式很大程度上提高了创建的效率和产生随机数的随机性。B提取数据a = gtk_entry_get_text(GTK_ENTRY(ws-component2);len = strlen(a);/*-提取数据-*/for(i=0; i= 0 & ai 0;j-) listn+=list1w*pow(10,j-1); w+; w=0;n+; int ex_data(char *a)int data1,w=0,list17,i;int len = strlen(a);for(i=0; i0;i-)/提取数据data1+=list1w*pow(10,i-1);w+;return data1;本程序段通过gtk_entry_get_text()函数获取传入文本框的字符串a，然后进行字符提取数据，并输入相关数组中保存，在程序中起到了将用户输入杂乱的字符转换为电脑可以识别和操作的数字的作用。后面的数据提取函数是对前一程序段的简化，在文中作用是将用户输入文本框中的单一操作数据转换为数字并返回，利用效率较高。C查找创新NodeStr Search(int data)/查找，输入：值，输出：对应前指针P;int i=0;NodeStr p=Top-head;while (1) while (p-next0-valuenext0;if(p-next0-value=data&i=0)flag=p;i=1;if (p-next1 = NULL)return p; p = p-next1;实现功能是输入数据，输出对应等于或比此数据次小的前数据的底层指针。选择这种返回方式的好处有以下几点，首先是返回此指针方便比较数据，返回前指针是因为方便删除，插入，不用重新定位前指针，高效简洁。此数据中的全局变量flag是用来存储所查找数据的最高层指针的，用处是使得删除高效。Dkey值更新while(pd)/更新pd-key+;pd=pd-next0;贯穿程序始终的key值更新程序段，保证了后期处理的正确性E错误警告弹窗if(pd-next0-value=data1)gtk_widget_hide(wm-component6);failed_p(nn数据在链表中已存在！nn);return;if(W=0)failed_p(nn连续插入失败nn请“输出”以刷新程序！nn);return;程序中的错误判断处理机制，弹窗警告，使得程序具有了更强的生命力，提高了用户的操作体验。F按值删除head=p=flag;/所删数据最高层前指针while(head)q=p;q=q-next0;pd=q;q=q-next0;p-next0=q;pd-next0=NULL;pd-next1=NULL;free(pd);/数据删除成功while(q)/更新keyq-key-;q=q-next0;p=p-next1;head=p;if(p)while(p-next0-value!=data1)p=p-next0;前期查找保存的flag指针在此处有了很大的用处，通过直接访问指针，直接定位到了此数据的顶层指针，然后通过p，q指针动态的移动，便可以很高效的删除所选数据，在删除时释放存储空间，后期再更新key值，使用while语句，直到head指针为空，即所要删除的数据为空时，结束删除操作。G全局变量细节1、if(S=1)Num_max=crate_ran_num;S=0;2、if(W=0)failed_p(nn连续删除失败！请稍后操作！nn);return;W=0;1中的全局变量S保存的信息是当S=1时，本次数据是由随机创建产生，便可以不用遍历就知道此次链表数据的最大长度。节省了遍历的时间消耗，当S=0时为按值创建，此时就需要遍历查找。2中的全局变量用来提醒用户的错误操作，由于程序本身的限制，使得在连续插入，连续删除上会出现由于数据未刷新而导致的程序崩溃问题，所以加入操作错误的提醒机制，可以有效的避免此类错误的发生。H输出while(p!=NULL)if(i=p-key)text=zhuanhuan(p-value);label1 = gtk_label_new(text);wm-componentwm-com_num+=label1;gtk_label_set_selectable (GTK_LABEL(label1), TRUE);gtk_box_pack_start(GTK_BOX(box2),label1,TRUE,FALSE,0);gtk_widget_show(label1);p=p-next0;elselabel1 = gtk_label_new(-);wm-componentwm-com_num+=label1;gtk_label_set_selectable (GTK_LABEL(label1), TRUE);gtk_box_pack_start(GTK_BOX(box2),label1,TRUE,FALSE,0);gtk_widget_show(label1);i+;在输出时，将输出结果放在了界面上，具体操作方法是建立每个数据相对应的标签，每行建立一个hbox组合框，然后将每一行的数据标签放在组合框上，然后将其打印在界面上，由于组合框组件所能容纳的构件数有一定的限制，所以在数据量大于16的情况下，输出选项容易出错，但在数据量小的情况下，不影响演示。在大数据测试时，不采用输出等操作，防止出错。I、转换函数char *zhuanhuan(int num)char *ws;int j=0,i=0,len; char temp7=0,str7=0;/若不初始化则，需要加tempj=0和stri=0 while(num) tempj=num%10+0; j+; num/=10; j-; while(j=0) stri=tempj; j-; i+; stri=0;ws=str; return ws;此转换函数的作用与提取数据函数的作用正好相反，此函数将输入的数据转换为字符串形式返回，其作用是在输出到界面的时候，将数据转换为标签可以识别的字符串形式，便于进行界面打印操作。其意义在于沟通了数据和界面，使其可以相互转换，使得程序更加的完整。3.4创新思想利用全局指针变量刷新界面，制作“全局菜单”typedef struct win_menu/用于更新保留菜单，整合指针信息int com_num;GtkWidget *component100;*Pwin;此结构体由两部分组成，com_num用来保存当前头指针所在的后一位下标，GtkWidget *component100;用来存储构件的指针。在本软件中，“0”用来存储底层组合框指针，“1”用来存储main_window的指针，动态的更新除0,1,还有菜单以外的组件。4.软件运行测试与界面展示图4-1 主界面图4-2 按值创建图4-3 输出全层图4-4 输出定层图4-5 弹窗警告5.问题与解决5.1 界面更新问题在软件前期规划时，将界面切换更新考虑在内，由于第一次接触GTK，对其了解不是很深，导致在界面制作时，界面更新成为一大难点，GTK+在全局菜单方面有很大缺陷，多方查阅资料仍无果，网络上的方法与自己的实际需要相差很大，更新构件时不是全部更新，就是更新不全，无法用在软件上，在研究了几天之后，结合网上的资料和请教学长，终于找到了一个简单有效的方法，全局变量保存各构件指针，每加入一个构件，保存其指针，在不需要时便可以调用函数void initialise()；进行初始化界面操作，只保留main_window,菜单还有组合框三个构件。在后期需要更新界面的一部分时，也可以使用这种思想，比如在输出定层中有如下代码段：for(;wm-com_num7;)gtk_widget_hide(wm-component-wm-com_num);gtk_widget_destroyed(wm-componentwm-com_num,NULL);在这里这个for循环实现的功能是将除前七个构件之外的构件初始化并释放掉，保证了在不切换功能时，用户重复的操作的正确完整性。5.2 输出操作难点在进行界面输出时，由于对GTK理解不深，对于界面打印，如果使用标准的文本框的话，数据显示不好控制，界面略显臃肿，不美观，所以在再三斟酌之后选择了使用添加标签的方法进行数据打印，在确定了方法之后，又碰到了难题，由于数据和字符串相互转化的乱码问题，在实现上耗费了很大精力，最终，实现了两个相互转化的函数，比较完美的解决了问题，然后进行了布局规划，输出时采用添加横向组合框，然后在组合框上添加数据标签的方式，在界面上显示了数据，再经过后期的优化，使得输出在界面的数据立体，比较好的展示了跳跃链表地特性。6. 结语本次课程设计通过GTK的学习，掌握了C语言下的面向对象编程，进一步提高了自己的编程能力，学习运用了GTK这个面向对象的图形化界面库。在后期调试阶段大量使用linxu下的调试工具gdb调试程序，对于linux下的开发过程有了初步的了解，并进一步熟悉了linux下的基础操作，为以后做linux运维打下了基础。辛苦的付出总是值得的，虽然在课程设计制作阶段遇见了一个又一个的难题，但通过查找资料，然后解决了问题的那种喜悦令人陶醉，这次课设虽然历时周期短，但我获得的东西却是很多的，有压力才有动力，学习最快的方法就是有一个目标并且为之奋斗，我相信在以后的学习中，我会做很多的东西，然后像这次可是一样收获很多的乐趣。7. 参考文献算法与数据结构C语言描述（第三版） 编著：张乃孝、陈光、孙猛GTK+程序设计（C语言版） Syd Logan著 战晓苏、王宁等译15
展开阅读全文