《数据结构总和排序.docx》由会员分享，可在线阅读，更多相关《数据结构总和排序.docx（14页珍藏版）》请在三一办公上搜索。
1、课程设计学生姓名：梁钰 学 号：130702216专业班级：计算机科学与技术132班课程名称：数据结构学年学期：20152016学年第2学期指导教师：白云飞2016年6月学生姓名梁钰学号130702216 成绩专业班级计算机132起止时间2016-6-202016-6-24设计题目排序综合指 导 教 师 评 语学习态度出勤情况：好口较好口一般口较差口课题工作量：饱满口较大口合理口较小口综合运用知识能力：好口较好口一般口较差口方案设计情况： 合理口 较合理口基本合理口 不合理口 课题结果分析能力：强口较强口一般口较差口设计实现情况：全部口大部分口部分口未实现口设计报告内容：详细口完整口较完整口不
2、完整口设计报告文档格式： 规范口 较规范口基本规范口 不规范口 独立动手能力：强口较强口一般口较差口指导教师：年 月 日1. 需求分析说明-12. 概要设计说明-23. 详细设计说明-34 .调试分析-65. 用户使用说明-66. 课程设计总结-97. 测试结果-98. 参考书目-101需求分析说明内部排序教学软件的总体功能要求:排序综合的总体目标：在Visual C+6.0的开发环境下，利用所学C语言或C+和数 据结构的相关知识，设计一个利用随机函数生成N个的随机整数（2000以上），对这些 数进行综合排序的程序，进行七种排序算法，并计算时间复杂度，选出两种较快的方法。基本功能如下：（1）至
3、少采用七种方法实现上述问题要求（可采用的方法有：插入排序、希尔排序、 起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同文 件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找 出其中两种较快的方法。以下是各功能模块的功能描述：1 .主函数模块本模块的主要功能是初始化图形界面，调用各模块，实现软件功能。2 .菜单界面子模块本模块的主要功能是根据用户的选择，引导用户使用软件所提供的各种功能。并在用 户提供必要数据，转入到存储文件子模块或者排序功能及输出子模块。3. 排序功能及输出子模块本模块的主要功能是根据用户的选择排序功能后，进行数组的创
4、建，随机函数产生随 机数据并且显示，随后转入排序方法选择界面进行选择。4. 时间效率比较子模块本模块的主要功能是以计算花费的时间为准进行对比，选出两种较快的排序算法。以此 分析在每种存储结构的下九种排序算法的优劣，输出每种算法的所用时间。并且每种排 序算法所用的时间结果都能保存到指定文件中。5. 读取文件子模块本模块的主要功能是通过存储文件名读取已储存的文件，并进入排序界面。6. 退出系统子模块本模块的主要功能是退出排序综合系统或者回到主模块菜单选项界面。7. 存储文件子模块本模块的主要功能是根据用户的选择，并在用户输入文件名后存储随机生成数。测试数据:1：随机数若干组2：希尔排序(1) 自定
5、义随机取一组数据(9,3,5,1,6,2,8,4,7)(2) 取增量为5,得到：(2, 3, 43：直接插入排序(1) 自定义随机取一组数据(2) 得到(15,21,28,434：直接插入排序(1) 自定义随机取一组数据(4343(7,(2) 得到(1,2,3,4,5,6,7,8)5：选择排序(1) 自定义随机取一组数据(7,(2) 得到(1,2,3,4,5,6,7,8)模块调用图:1, 6, 8, 5, 7, 9)21,89)2,5,2,5,89,151,9,61,9,6438,8,28)3)3)2概要设计说明图一操作函数说明：creat()：定义随机函数，产生随机数据save(int f1
6、)：保存文件read():读取文件DirectInsertSort(int p, int len): 直接插入排序ShellSort(int a,int n):希尔排序BinSort(int r,int length):折半插入排序void void void void void void voidsort(int aN,int n):冒泡排序 int my_quick(int a,int low,int high):定义快速排序函数void buuble(int a,int n):简单选择排序 void merge(int aN,int l_start,int l_end,int r_end
7、):归并排序 1 int msort(int aN,int start,int end):归并排序 2 void end():定义结束函数 void menu():函数声明/控制输出格式void display(int a,int n): 菜单函数void menu():菜单函数3详细设计说明1. 主函数模块首先定义creat()函数用来生成不同的随机数。该函数是用两个函数来生成随机数:rand()和srand(),前者是生成随机数，后者是获取随机种子，使随机数不断变化。2. 菜单界面子模块菜单函数voidmenu()显示了系统操作的整个界面，包括第一个界面“选择存储生成 的随机数还是读取文件
8、”和第二个界面“进行综合排序”。在选择排序的函数时，同时计 算其运行时间。在综合排序界面可以选择退出程序或进入第一个界面或打开已有文件进 行排序。3. 存储界面子模块保存文件函数void save ()中，FILE为系统结构体，定义指向文件的指针*fp，输 入存储的文件名，打开文件(若文件存在，则删除文件中的原有元素；若文件不存在， 则新建一个文件)，并将参数数组中的元素存储到文件中4. 读取文件面子模块读取文件函数void read ()中，定义*fp指向文件的指针，提示输入要读取文件的 文件名，读取文件中的元素，输出到数组中，并打印出来。且跳转至排序综合界面，提 供用户选择排序方法。5.
9、直接插入排序第1遍，将初始文件中的记录K1看作有序子文件，将K2插入这个子文件中。若R2 的关键字小于K1的关键字，则R2插在K1的前面，否则K2插在K1的后面。第2遍，将 K3插入前面的两个记录的有序子文件中，得到3个记录的有序子文件。依此类推，继续 进行下去，直到将Kn插入到前面的n-1个记录的有序子文件中，最后得到n个记录的有 序文件。6. 希尔排序先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然 后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-l d2v或jt，
10、转，其中一个子表已合并完，比较选取结束 选取ri和rj关键码较小的存入辅助数组rf如果 ri.keyrj.key，rfk=ri ； i+； k+；转否则，rfk=rj； j+； k+；转 将尚未处理完的子表中元素存入rf如果iv，将riv-1存入rfkt /前一子表非空如果j 冒:包书 ，序XXXXXXXNNXXXXXmOtN S 气快j束寸非，序JCXXXXXXNNJCJCXXXXXNN 6、 j 司 _ j 先 j 牟寸非，序 XNNNJCJCXXXXXNNNJCJCXXXNNNJCJCXXXXXNNNJCJCXXXJCXXXXXXNNJCJCXXXXXNN 8 气 日寸间 ?；7 率匕匕
11、转JCXXXXXXNNJCJCXXXXXNN 9 .、 才丁 ：； ,件弁 j井 / 书 f ,序-界X X X X X M： M： X X X林叟狗拼音输入法半请选择菜单:图6选择1执行直接插入排序后，排序的结果如图7所示F:课文、模电lzonghepaixiADebiigY130702216.exe9029039039039049059059069069069069069089089099099109109129129139149149159159159169169169179189189189209209209209219219219219219229239249259269279279
12、279279279299299299309319329329329329329339339339339349359359359369369369389389389389399409419419419429429439439439459459469479479489499499499509519519519529539549549559559559569569569569579579589589599599609609609619619619619619629639649659659659659659669669669679679689699699699729739739739749759759
13、75976976976976977977978978978978978979980980981982982982982983984984984985985985985986986986987987987987988988988988989989991991992992993994994994994995996996996996997997997998998999时间为：4.000000搜狗拼音输入法半：、士:KNXJCXXXXX 耳】育选择项6课程设计总结通过这次课程设计的学习让我学会了许多。让我对我们的专业知识有了很大理解！ 我对专业的课程有了初步的认识。首先学会了随机数的产生。熟练的撑握了
14、 C和C+的文件读写操作。撑握了每种排 序算法的基本思想，并学会编写代码的基本思路，写出解决方案，完成代码，调试程 序。条理清晰的书写代码，使编写过程变得简单，修改时也清楚易查。但我还是认为自己有很多的不足，课程设计作品并不完善，以后我会更努力的学习 相关知识，多亲手编写代码，勤学多练，希望以后能弥补这些不足。7测试结果希尔排序:堆排序:这次的课程设计我学会了很多，不光让我认识了本专业知识，还让我锻炼了独立思 考，不轻言放弃的精神。从刚开始的无从下手，到查阅资料后的编写，再到后期修改， 才有了如今的模样。期间做了许多调整和修改，所以说一切美好的事物都离不开认真 和努力！通过这次数据结构课程设计，使我对软件的界面设计有了一个比较深刻的了 解，对各种内部排序方法的性能有了清晰的认识，使我感觉到到，一个优秀的软件， 不仅仅是可以运行的，更应该具有人性化的界面，协调的布局，合理的结构，良好的 性能和一定的容错性。最快的两种排序:1. 希尔排序2. 堆排序8参考书目1 数据结构（C语言版），严蔚敏，吴伟民，清华大学出版社2 C语言课程设计案例精编，郭翠英，中国水利出版社
