排序综合数据结构课程设计

1、大连科技学院数据结构课程设计题目排序综合学生姓名 专业班级指导教师 职 称 副教授所在单位信息科学系软件教研室教学部主任完成日期 2013年1月11日课程设计报告单学号姓名专业班级网络工程考核项目评分备注1平时工作态度及遵守纪律情况（10 分）2掌握基本理论、关键知识、基本技能的程度和 阅读参考资料的水平（10 分）3独立工作能力、综合运用所学知识分析和解决 问题能力及实际工作能力提高的程度（20 分）4完成课程设计说明书及软件的情况与水平（小 组分工情况、规范性、整洁清楚、叙述完整性、 思路清晰程度、工作量及实际运行情况和创新 性）（60 分）总评成绩（优、良、中、及格、不及格）指导教师签字

2、:综合评定:2013年1月11日指导教师签字：2012年12月24日数据结构课程设计任务书一、任务及要求：1 .设计(研究)任务和要求研究内容：排序综合任务和要求：(1)学习数据结构基础知识，掌握数据结构典型的算法的使用。(2)对指导教师下达的题目进行系统分析。(3)根据分析结果完成系统设计。(4)编程：在计算机上实现题目的代码实现。(5)完成对该系统的测试和调试。(6)提交课程设计报告。要求完成课程设计报告 3000字以上(约二十页)。完成若干综合性程序设计题目，综合设计题目的语句行数的和在100行语句以上。2 .原始依据结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理

3、地选择相应的 存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证 自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3 .参考题目：二、工作量2周(10个工作日)时间三、计划安排第1个工作日：查找相关资料、书籍，阅读示例文档，选择题目。第2个工作日第3个工作日：设计程序结构、模块图。第4个工作日第9个工作日：完成程序的编码，并且自己调试、测试。穿插进行课程设计报 告的撰写。第10个工作日：上交课程设计报告，由教师检查软件测试效果、检查课程设计报告，给出学生 成绩。排序综合11 .需求分析11.1 任务描述11.2 功能分析1

4、2 .概要设计12.1 主要全程变量和数据结构12.2 程序模块结构23 .详细设计33.1 程序的主要结构如下图所示。 33.3 显示各排序算法排序后的的数据。 43.4 函数实现（例如直接插入排序） 44 .调试分析55 .测试结果及运行效果7参考文献 11附录全部代码 11数据结构课程设计总结 23排序综合1 .需求分析1.1 任务描述至少采用3种方法实现上述问题求解，并把排序后的结果保存在不同的文件中。1.2 功能分析显示随机数,是调用rand()函数输出数组a口。数组a口中保存有随机产生的随机数；直 接选择排序，是通过n-1次关键字之间的比较，从n-i+1个记录中选出关键字最小的记

5、录，并和第i个记录交换之；起泡排序,是如果有n个数，则要进行n-1趟比较，在 将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个排序中的记录基本有序”时，在对全体记录进行一次直接插入排序；直接插入排序，是将一个记录插入到以排序好的有序表中，从而得到一个新的记录数增1的有序表。设整个排序有n个 数，则 进行n-1趟排序，即：先将序列中的第一个记录看成一个有序的子序列，然后第 2个记录起逐个进行插入，直接整个序列变成按关键字非递减有序列为止；快速排序，是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进

6、行快速排序，整个排 序过程可以递归进行，以此达到整个数据变成有序序列；堆排序，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。2 .概要设计2.1 主要全程变量和数据结构(1)数据结构：#include "stdlib.h"#include <stdio.h> #define s 100 typedef struct record int key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec; int a7,b7;file()(2)算法的入口及其说明#include&l

7、t;stdio.h>#define s 100/宏定义命令typedef struct record /记录声明的结构体int key;/定义变量static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;/记录静态变量结构体file() /系统定义printf("* n");printf("*1.直接插入排序* n"printf("*2.希尔排序* n"printf("*3.起泡排序* n"printf("*4.快速排序* n"p

8、rintf("*5.简单选择排序* n"printf("*6.堆排序* n"printf("*7.总结* n"printf(" * printf("*0.退出* n");* n");)；)；)；)；)；)；)；以上 printf("出* n");为系统主菜单输2.2 程序模块结构程序划分为以下几个模块(即实现程序功能所需的函数) 主控菜单项选择函数：menu_select() 插入排序函数:InsertSort ()选择排序函数：StlectSort() 起泡排序函数：Bub

9、bleSort() 堆排序函数：heapsort () 快速排序函数：Quicksort () 希尔排序：Shell Sort ()3 .详细设计3.1 程序的主要结构如下图所示图3-1函数调用关系图其中main()是主函数，它进行菜单驱动，根据选择项10调用相应的函数3.2 数据结构定义定义增构体库亚膜、海运叙述衽种排序函数，并相应荐出各种排 序的眸法及过程，定义数组的值.并瑜出所纪录的值请接5数字槐选择函数,可言找出各种排序结果Z输出所镀排序的结果.请盖NUMOia出.图3-2课程设计流程图3.3 显示各排序算法排序后的的数据。图3-3程序工作流程图3.4函数实现(例如直接插入排序)#in

10、clude "stdlib.h"#include <stdio.h>#define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7； file()printf("printf("printf(" printf("*0.退出*1.直接插入排序n");* n");* n");*n");void Straight_insert_sort(r ,n) /*

11、 直接插入 */struct record r口;int n; int i,j;a1=0;b1=0;for(i=1;i<=n;i+)printf("%4d",ri.key);printf("n");for(i=2;i<=n;i+) r0=ri；j=i-1;while(j>=0) && (r0.key<rj.key) b1+；rj+1=rj-；rj+1=r0；a1=a1+2;printf("* 直接插入 *n")；for(i=1;i<=n;i+)printf("%4d",

12、ri);printf("n");printf("move:%d time, compete:%d time",a1,b1);printf("n");4 .调试分析4.1 直接插入排序将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表4.2 起泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，知道第 N-1个和第 N个记录的关键字进行过比较为止。上述为第一趟排序。其结果使得关键字的最大被安 排到最后一个记录的位置上。然后进行第二

13、趟起泡排序，对前N-1个记录进行同样操作。 一共要进行N-1趟起泡排序。4.3 直接选择排序每一趟从待排序的记录中选出关键字最小的，顺序放在以排好序的子文件的最后， 知道全部记录排序完毕。4.4 希尔排序先取一个小于n的整数d,作为第一个增量，把文件全部记录全部分成di个组。所有距离为di的倍数的记录放在同一个组中。先在个组中进行直接插入排序：然后， 取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1 (dtvdt-1v<d2<d1 即所有记录放在同一组中进行直接插入排序为止。4.5 快速排序设置两个变量i、j,排序开始的时候：i=0, j=N-1 ;以第一个

14、数组元素作为 关键数据，赋值给key,即key=A0;从j开始向前搜索，即由后开始向前搜索(j -),找到第一个小于 key的值Aj , Ai与Aj交换；从i开始向后搜索，即由前开始向后搜索(i + ),找到第一个大于key的Ai , Ai与Aj交换；重复第3、4、5步，直到I=J; (3,4步是在程序中没找到时候j=j-1 , i=i+1 ,直至找到为止。找到并交换的时候i, j指针位置不变。另外当 i=j这过程一定正好是i+或j-完成的最后令循环结束。)4.6 堆排序堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它 们均是通过调用 Heapify实现的。堆排序的最坏时间

15、复杂度为 O(nlogn)。堆序的 平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不 适宜于记录数较少的文件。堆排序是就地排序，辅助空间为0(1)。排序算法时间复杂度空间复杂度是否稳定直接插入排序0 (n2)0(1)稳定起泡排序0 (n2)0(1)稳定直接选择排序0 (n2)0(1)不稳定希尔排序0 (n1.5)0(1)不稳定快速排序O(nlog 2n)0(nlog 2n)不稳定堆排序0(nlog 2n)0(l)不稳定5 .测试结果及运行效果(1)运行程序进入程序开始菜单请二全序机出序顺一图5-1开始菜单(2)开始菜单中会出现四个选项：完全有序的情况；逆序的情况；随机排序

16、的 情况；退出。运行时选择了随机排序的情况，得到100个随机数的随机排序，如下图。队睢恒获得1蒯个随机数二184&7 6334265001916,?15724114782935826962244t4 570528145232811827 9961 491 2995 11942 4«27 54363239114604 3902 153 29212382174211871619718198 95 5447217261-4771 11S387262991703E 98942670323811313223033317673 466415141 77112S2

17、53686825547276443262327572003712859 8723 974127529 77812316 393&22190 1842 2Bfl 30106 904Q S942192642264fi274462380E15890 fc7292437M1535H150063110124393 354819629 12623240841995 41875 611840 4966 73761393126308169443243924626113 23 55372153816118 20822292916541 48m3请诩举排序算法图5-2随机排序(3)得出随机数字后，程序列出

18、七个选项：冒泡排序；直接插入排序；简单选择排序；快速排序；希尔排序；堆排序；退出。选择冒泡排序，对100个随机数进行冒泡排序，得到结果如下图。图5-3起泡排序(4)为了测试该程序，下面继续尝试进行了其他几种排序方式，结果如下图所示图5-4直接插入排序图5-6快速排序图5-5简单选择排序简单选择排序结果如上图KJCMJCXJ<KJ«MJ«J<XXM.MXXNK XMM JC JC XM'块j 非J< M KJCXJCXMMJ<M.J<JCXKMXKXXMXMMK028 306 225 331 9441B581?311?6220643244

19、3641124346?548334?184?66551755J7 581O63e66?296S686868737677118723874Z9B4B97419894LB32511323115381184ail7681Z82512 316123821Z623L285913731146711477115006151411535015890161181654il68221&?1916?4417 0351742117673184711871fcl875fel926419629197181989519912199S42003721538217262219022 6482292923SOE23811

20、248842437B243?3S446E24&26255472E&£?262992630826504269632744627 5292744281462825328703293592010&2033331101313223239132439326&232757t ine rio ue - 306compete： 324,4 time请选择排序算法-3 4E6-6快速排序结果如上图M JCX JCMM MIC JCJCM JCK JCX JCXMMJCM JCM书 j，JXJCXMMJO<JCKJCK>CX*XJCMJCKJCKJCK>

21、CX00 1598 225 307 331 ?451«5819322(17132361-1243%?548334?1«6655175537581063066727686868687376771187238?427040?741S87410325113231153«1184011?68120 2512316123821262312S 5913931146 7L14771150K151411535B15S90161181654116S2216 919169 441703517421176731847118716187561926419629197181989S1991

22、2199542003721S3821726221 9O22G48229292380523eil240842437a24393244&524£2C25547256G72G2992G39fi2G&Q42C9G3274 4t2752927t442814G2S25328703292S93ai0t3033331iai31322323913242932&t2tIne r compete-2871 tineI幕外瞬二二二二 枷二二二二二二 堆排/6痕由0图5-7希尔排序希尔排序结果如上图a 15 9 8 225 0 331 9451881932207132443641 04

23、69S4633418496655175537 EBld63O66?2768686e6«?3767?LlS72389429948?7419S?410325113231153811S4011?6S12O2512 3161238Z126231285?13931t6?ll?1150B615i4115350158901611816511&823161?16?417 B35174211?673104711B716187561726419629177181¥S951?71217554200372153821726221?022 64»22?2?2380523811240

24、842437BZ43?32446524626Z554725667262972630826504263632744627 522784428146282532S7032?3593010630333311013132232391324393266232757XK 扰舞：M鬓 * 网堆苗 f .序一' X N M：/餐MM X H AM KK0 1 0 14 IS 44 22G 371 94&185ei9322071329S3te44fc9S4fi3349184966G517&53 £819£30£&729£983£9

25、4473037710983390489889974198941032&1132311391184011991202g12 516i23821262312S5i3931i4671i4771iE0B615i41i53S8i602i±6±2516547i6S2816925169E017 03517439i78S71S487187161S7561926dl?6291971819a9519912195542003721538217262219022 ?0922?29238052381124084243?0244602456624626255472566726299263692

26、&564271452749327 S8127S4428151282532870329359301063036031121313223243?32447326773Z75?move ： 31121 time, compete： 27S81 time图5-8堆排序堆排序结果如上图以上图片为各种排序的结果，排序结果后显示出各种方式排序所用移动次数和比较 次数，以方便比较使用。参考文献1严蔚敏 吴伟民著.数据结构（C语言版）.清华大学出版.1999年第一版2陈一华等编.数据结构使用C语言.电子科技大学出版社.1998年第一版3谭浩强.C语言程序设计（第二版）.北京.高等教育出版社.2002附录

27、全部代码#include "stdlib.h" #include <stdio.h> #define s 100 typedef struct record int key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7; file()printf("*1.直接插入排序*n"printf("*2.希尔排序*n"printf("*3.冒泡排序*n"printf("*4.快速排序*n"printf("*5.简

28、单选择排序*n"printf("*6.堆排序*n"printf("*7.总结*n"printf(" *0.退出* n");printf("*n");printf("*n");void Straight_insert_sort(r ,n) /* 直接插入 */ struct record r口;int n; int i,j;a1=0;b1=0;for(i=1;i<=n;i+)printf("%4d",ri.key);printf("n");f

29、or(i=2;i<=n;i+) r0=ri;j=i-1;while(j>=0) && (r0.key<rj.key) b1+;rj+1=rj-;rj+1=r0;a1=a1+2;printf("I*直接插入*n");for(i=1;i<=n;i+)printf('%4d”,ri);printf("n");printf("move:%d time, compete:%d time",a1,b1);printf("n");void Shell_sort(r ,n)/* 希尔

30、排序 */struct record r口;int n; struct record rec,temp;int i,j,t,h;a2=0;b2=0;for(i=1;i<=n;i+)printf("%4d",ri.key);printf("n");t=n/2;while(t>=1) h=t;for(j=h;j<n;j+) rec=rj;i=j-h;while(i>=0) && (ri.key>rec.key) b3+;temp=ri+h;ri+h=ri;ri=temp;i=i-h;a2=a2+3;t=t/2;b

31、2+；printf("I*希尔排序*n");for(i=0;i<n;i+) printf('%4d”,ri); printf("n");compete:%d time",a3,b3);冒泡排序 */printf("move:%d time, printf("n");void Bubblle_sort(r ,n) /* struct record r口;int n; struct record rec;int i,j,m,flag;a3=0;b3=0;for(i=1;i<=n;i+) printf

32、("%4d",ri.key); printf("n");m=n;flag=1;for(i=1;i<=m-1;i+) flag=0;for(j=0;j<=m-i-1;j+) if(rj.key>rj+1.key) b3+;rec.key=rj.key;rj.key=rj+1.key;rj+1.key=rec.key; a3=a3+3;flag=1;if(flag=0) break;printf("* 冒泡排序 *n")；for(i=0;i<n;i+)printf("%4d",ri.key);p

33、rintf("n");compete: %d time",a3,b3);printf("move: %d time, printf("n"); int push(h,top,m,n)inth口；int top ,m,n; h+top=m; h+top=n; return(top); int pop(h,top,m,n)int h, top,*m,*n; *m=htop-;*n=htop-;return(top);int quick(r ,i,j)struct record r口;int i,j;rec=ri;while(i<j)

34、 while(i<j)&&(rj.key>rec.key)j-;b4+;if(i<j)ri+=rj;a4+;while(i<j)&&(ri.key<=rec.key)i+；b4+;if(i<j)rj-=ri；a4+;ri=rec;a4+;return(i);快速排序 */void Quick_sort(r ,l,h)/*struct record r口;int l,h; int sss;int top,i,j,k;for(i=1;i<=s;i+)printf("%4d",ri.key); printf

35、("n");i=l；j=h；top=-1;do while(i<j) k=quick(r ,i,j);if(j-k>1)top=push(ss,top,k+1,j);j=k-1；if(top>0)top=pop(ss,top,&j,&i);while(top>=0)|(i<j);printf("I*快速排序*n");for(i=1;i<=s;i+)printf("%4d",ri.key);printf("n");compete: %d time",a4,

36、b4);printf("move: %d time, void Simple_select_sort(r ,n)/* 简单选择排序 */struct record r口;int n;int i,j,m;a5=0;b5=0;for(i=1;i<=n;i+) printf("%4d",ri.key); printf("n");for(i=1;i<=n-1;i+) m=i;for(j=i+1;j<=n;j+)if(rj.key<rm.key)m=j;b5+;if(i!=m) rec=ri; ri=rm;rm=rec; a5=a

37、5+3;printf("I*n");for(i=1;i<=s;i+)printf("%4d",ri.key);printf("move:%d time,printf("n");compete:%d time",a5,b5);printf("n");void p(r ,n)/*次数排列*/intr口；int n;int rec;int i,j；for(i=1;i<=n;i+) rec=ri;j=i-1;while(j>0) && (rec<rj) rj+1=

38、jj=j-1；rj+1=rec;if(r=a)printf("关键字移动次数排列:n");elseprintf("关键字比较次数排列:n"); for(i=1;i<=n;i+) printf("%8d",ri);printf("n");void heap(r,l,m)/* 堆的子函数 */struct record r口;int l,m; int i,j;i=l;j=2*i;rec=ri;while(j<=m) if(j<m)&&(rj.key>rj+1.key)j+;b6+

39、;if(rec.key>rj.key) b6+；ri=rj；i=j；j=2*i;a6+;else j=m+1;ri=rec;void Heap_sort(r ,n)/* 堆排序 */struct record r口； int n; int l;a6=0;b6=0;for(l=1;l<=n;l+)printf("%4d",rl.key); printf("n");for(l=n/2;l>=1;l-)heap(r,l,n);for(l=n;l>=2;l-) rec=r1;r1=rl;rl=rec;a6=a6+3;heap(r,1,l-

40、1);printf("* 堆 排 序*n");for(l=n;l>=1;l-) printf("%4d",rl.key); printf("n");compete: %d time ",a6,b6);printf("move: %d time, printf("n");compete。printf("*内部排序结果汇总*nprintf("n");printf("移动次数比较次数printf("n");printf("直接

41、插入%6d%8dn ",a1,b1)printf("希尔排序%6d%8dn ",a2,b2);printf("冒泡排序%4d%8dn ",a3,b3);printf("快速排序%4d%8dn ",a4,b4);printf("简单选择%4d%8dn ",a5,b5);printf("堆的排序%4d%8dn ",a6,b6);printf("n");n")；")；main()char ch; int i,j,t,k;printf("I*n

42、 ");printf（"请选择初始时数的顺序n"）;printf（"1-完全有序的情况n"）;printf（"2-逆序的情况 n"）;printf（"3-随机排序的情况n"）;printf（"0-退出 n"）;printf("I*n");ch=getch();switch(ch)case '1': rand();for(i=0;i<s;i+)printf("%5d",ai=rand(5);for(i=0;i<s-1;i

43、+)for(j=i+1;j<s;j+)if(ai>aj)t=ai；ai=aj；aj=t；printf("完全有序的数列为：n");for(i=0;i<s;i+) printf("%5d",ai);printf("n");for(i=1;i<7;i+)printf("请选择排序算法n");printf("冒泡排序1n");printf("直接插入排序2n");printf("简单选择排序3n");printf("快速排序4n

44、");printf("希尔排序5n");printf("堆排序6n");printf("退出0n");ch=getch();switch(ch)case '0':exit(0);case'1': Bubblle_sort(a,s);break;case'2': Straight_insert_sort(a,s);break;case'3': Simple_select_sort(a,s);break;case'4': Quick_sort(a,0

45、,s-1);break;case'5': Shell_sort(a,s);break;case'6': Heap_sort(a,s);break;default:exit(0);break;case '2': rand();for(i=0;i<s;i+)printf("%5d",ai=rand(5);for(i=0;i<s-1;i+)for(j=i+1;j<s;j+) if(ai<aj) t=ai； ai=aj； aj=t；printf("逆序的数列为：n");for(i=0;i<s;i+) printf("%5d",ai);printf("n");for(i=0;i<7;i+)printf("请选择排序算法n");printf("冒泡排序1n");printf("直接插入排序2n");printf("简单选择排序3n");printf("快速排序4n");printf("希尔排序5n");pr