数据结构课程设计57651

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

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

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

4、功能分析12. 概要设计1主要全程变量和数据结构 1程序模块结构 23. 详细设计3程序的主要结构如下图所示。 3数据结构定义 3显示各排序算法排序后的的数据。 4函数实现（例如直接插入排序） 44. 调试分析5直接插入排序5起泡排序5直接选择排序5希尔排序6快速排序6堆排序65. 测试结果及运行效果7参考文献11附录全部代码12数据结构课程设计总结24v1.0可编辑可修改排序综合1. 需求分析任务描述至少采用3种方法实现上述问题求解，并把排序后的结果保存在不同的文件中。功能分析显示随机数，是调用rand()函数输出数组a。数组a中保存有随机产生的随机数； 直接选择排序，是通过n-1次关键字之

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

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

7、n clude<>#defi ne s100直接插入排序* n");printf("*2.希尔排序* n");printf("*3.起泡排序* n");printf("*4.快速排序* n");printf("*5.简单选择排序* nprintf("*6.堆排序* n");printf("*7.总结* n");printf(” *0.退出*n");printf("* n")以上 printf("* n")系统主菜单

8、输出程序模块结构程序划分为以下几个模块（即实现程序功能所需的函数）主控菜单项选择函数:menu_select（）插入排序函数:InsertSort（）选择排序函数：StlectSort（） 起泡排序函数：BubbleSort（） 堆排序函数：heapsort （） 快速排序函数：Quicksort （） 希尔排序：Shell Sort （）3. 详细设计程序的主要结构如下图所示图3-1函数调用关系图其中main()是主函数，它进行菜单驱动，根据选择项10调用相应的函数数据结构定义图3-2课程设计流程图28显示各排序算法排序后的的数据。图3-3程序工作流程图函数实现（例如直接插入排序）#i nc

9、lude ""#in elude <>#defi ne s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec; int a7,b7;file()printf("printf("printf("printf("*0.* n");直接插入排序 * n");n");* *1退出void Straightnsert_sort(r, n) /*struct record r;int n;* n

10、"); 直接插入*/ int i,j;a1=0;b1=0;for(i=1;i<=n ;i+)prin tf("%4d",ri.key);prin tf("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+) prin tf("%4d",ri); prin

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

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

13、即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-完成的最后令循环结束。)堆排序堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为0(nlogn)。堆序的平均性能

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

15、，得到100个随机数的随机排序，如下图。施到丹获得观个随机数二A8467 6334265001916-S15724114782935826962244&4 570528145232811827 9961 491 2995 11942 4«27 54363239114604 3902 153 29212382174211871619718198 95 5447217261-1771 11S38?2629917035 98942870323811313223033317673 46G415141 77112S253Gfl68255472764432623

16、27572003712859 8723 974127529 77812316 303&22190 1842 2B830106 9040 S942192642264fi2744t2380E1589H t7292437M1535H150063110124393 354819629L2E2324084199541875611840 4966 7376139312630816944324392462611323 5537215381£11820822292916541 4阴3请选J睪排序算迭图5-2随机排序(3) 得出随机数字后，程序列出七个选项：冒泡排序；直接插入排序；简单选择排序

17、；快速排序；希尔排序；堆排序；退出。选择冒泡排序，对100个随机数进行冒泡排序，得到结果如下图。3 216 327 641 9431S5T19301954196550833051355441334243469S4B334918496655175E37 58ia63S6&7296B6S&8687376?118723B9429S4097419894103211323115381184011965120251 31612382126231285?13931146?1147?11500615141153581589016118165411682216?1916?4417 0351742

18、11?6731«471187161«756192641962?1971»1?85519121?5200372153821726221?022 &482292923805238112408424370243932446524626255472S667262?9263B826504265632744627 S2276442814fc282E3287032,93593010fc30333311013132232391324393266232757move: 641 tine , compete = 2554 t ine 囁曆算法 j-24-5图5-3起泡排序(4

19、) 为了测试该程序，下面继续尝试进行了其他几种排序方式，结果如下图所示直30move:Z c H II图5-4直接插入排序可 甲 | 先 扌-于 xxjtxxxxjcxxiaxxxxNxxxxxxxx02817 225 331 94418581?311?&2206430523&4142434S954B334?184»6fc55175537 5S10630&6?2¥6»686868737&77118723«?429040?41999410325113251153811843119681202513 3L6123821Z6Z3

20、12«5?13931146?114771LS00615141.15350158?01611»16541168221&9191694417 03517421176731847118716L8756192&419&29197181989519912199S4200372153S217262219022 6482292923805238112404243?024393244652462625&4725&&72629?2&308265042&9632744&2?&442 圧丄字仝 5 今 30:L0&#

21、163;MM2 仝 3丄丄0丄 31322323913243?326&2327S7tzine图5-5简单选择排序简单选择排序结果如上图图5-6快速排序快速排序结果如上图0 0 15 9 8 225 30? 331 ?4518581?322ff?l32136-114243%754833471®49665517 5537581063066727686868687376771187238?42?0409741787410325113231153«1184011?68120 25123161238212623128591393114671147711500615141153

22、50158901611«165411682216?1919 441703517421176731847118716187S6192641929197181989519912199542003721S3821726221 9022£4822929239052381124084247024293244&46 27529276 442S1462S2S32S： 7032935939106303333119131322323913243932&62tine图5-7希尔排序希尔排序结果如上图O 15 V 8 225 Q 331 94518S819322071324436

23、41U469S483341849665517553 5810630667256868686873767711872389429040974198941032511323115381184011568120251231612382126231285139311467114771150B615141153501589016118165411&82Z1631J1694417 035174211?673184711»71618756192641962919718198951?9121995-4200372153821726221902264822929238053381d24H842

24、43?0243932446524626255472566726299263082&50426963274-16275227644281462825328703293593010636333311013132232391324393266232757018141544 22S 371 94518581932207132953684469S4893491849Gt5517S537E8ia63066?296883694473837?188833904090S9?741989410325113231153811840119681202512 31612382126231285139311467

25、1147711500615141153881602116125165471&8281652516?5017 0351743917a97184871871GlS75G192fi4196291971819S951991219954200372153S2172G2219022 ?Q922929238052811240e4243?e24460245O&2462G255472566726299263892&564271452749327 F；812764428151282532870329359301063036031121313223243?32447326773275?mov

26、e : 31121 time, compete: 27581 time图5-8堆排序堆排序结果如上图以上图片为各种排序的结果，排序结果后显示出各种方式排序所用移动次数和比较 次数，以方便比较使用。参考文献1 严蔚敏 吴伟民著数据结构（C语言版）.清华大学出版.1999年第一版2 陈一华等编.数据结构-使用C语言.电子科技大学出版社.1998年第一版3 谭浩强.C语言程序设计（第二版）.北京.高等教育出版社.2002附录全部代码#i nclude ""#in elude <> #defi ne s 100 typedef struct recordint key;

27、static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file()printf("* n")printf("*1.直接插入排序* nprintf("*2.希尔排序* n");printf("*3.冒泡排序* n");printf("*4.快速排序* n");printf("*5.简单选择排序* nprintf("*6.堆排序* n");printf("*7.总结* n");prin tf(&q

28、uot; *0.退出* n");prin tf("* n")");");void Straightnsert_sort(r,n) /*直接插入 */ struct record r; int n; int i,j;a1=0;b1=0;for(i=1;i<=n ;i+)prin tf("%4d",ri.key);prin tf("n");for(i=2;i<=n ;i+) r0=ri;j=i-1;while(j>=0) && (r0.key<rj.key) b1+;r

29、j+1=rj-;rj+1=r0;a1=a1+2;printf("*直接插入 *n");for(i=1;i<=n ;i+)prin tf("%4d",ri);prin tf("n");printf("move:%d time, compete:%d time",a1,b1);prin tf("n");希尔排序*/void Shell_sort(r, n) /* struct record r;int n; struct record rec,temp; int i,j,t,h;a2=0;b2

30、=0;for(i=1;i<=n ;i+)prin tf("%4d",ri.key); prin tf("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>) b3+;temp=ri+h;ri+h=ri;ri=temp;i=i-h;a2=a2+3;t=t/2;b2+;printf(" *n");for(i=0;i< n;i+)prin tf("%4d",ri

31、);prin tf("nH);printf("move:%d time, compete:%d time",a3,b3);prin tf("nH);冒泡排序*/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+) prin tf("%4d",ri.key); prin tf("nH);m=n;flag=1;for(i=1;i<=m-1;i+)

32、flag=0;for(j=0;jv=m-i-1;j+) if(rj.key>rj+1.key) b3+;=rj.key; rj.key=rj+1.key; rj+1.key=; a3=a3+3; flag=1;if(flag=0) break;printf("*冒泡排序*n");for(i=0;i< n;i+)prin tf("%4d",ri.key);prin tf("nH);compete: %d time",a3,b3);prin tf("move: %d time,prin tf("nH);in

33、t push(h,top, m,n) int h;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(ivj) while(i<j)&&( rj.key>) j-； b4+;if(i<j)ri+=rj;a4+;while(i<j)&&(ri.key<=)

34、 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+)prin tf("%4d",ri.key);prin tf("n");i=l;j=h;top=-1; do while(ivj) k=quick(r,i,j);if(j-k>1)top=push(ss,top,k+1,j); j=k-1;if(top>

35、;0)top=pop(ss,top,&j，&i);while(top>=0)|(i<j);printf("*n"); *for(i=1;i<=s;i+)prin tf("%4d",ri.key);prin tf("nH);prin tf("move: %d time, compete: %d time",a4,b4); 简单选择排序*/void Simple_select_sort(r, n) /* struct record r;int n;int i,j,m;a 5=0;b 5=0;fo

36、r(i=1;i<=n ;i+)prin tf("%4d",ri.key);prin tf("nH);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=a5+3;printf(" *单 选 择 *n");for(i=1;i<=s;i+)prin tf("%4d",ri.key);prin tf("nH);prin tf("

37、move:%d time, compete:%d time",a5,b5); prin tf("nH);void p(r, n) /*次数排列*/int r;int n; in t rec;int i,j;for(i=1;i<=n ;i+) rec=ri;j=i-1;while(j>0) && (rec<rj) rj+1=rj;j=j-1;rj+1=rec;if(r=a)printf(”关键字移动次数排列:n");elseprintf("关键字比较次数排列:n");for(i=1;i<=n ;i+)pri

38、n tf("%8d",ri);prin tf("nH);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+;if>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;a 6=0

39、;b6=0;for(l=1;l<=n;l+)prin tf("%4d",rl.key);prin tf("n");for(匸 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-1);printf(" *n");for(l=n;l>=1;l-)prin tf("%4d",rl.key);prin tf("nH);prin tf("move: %d time,

40、compete: %d time ",a6,b6);prin tf("nH);compete()printf("*内部排序结n");prin tf(" -printf("移动次数n");printf("-n");printf("直接插入%6d%8dnprintf("希尔排序%6d%8dn ",a2,b2);printf("冒泡排序%4d%8dn ",a3,b3);printf("快速排序%4d%8dn ",a4,b4);printf(&

41、quot;简单选择%4d%8dn ",a5,b5);printf("堆的排序%4d%8dn ",a6,b6);prin tf(" -n");n");比较次数",a1,b1);mai n() char ch; int i,j,t,k;prin tf("*n ")printf("请选择初始时数的顺序nprin tf("1-完全有序的情况n");prin tf("2-逆序的情况n");prin tf("3-随机排序的情况n");prin tf

42、("0-退出n");prin tf("*n")ch=getch();switch(ch)case '1': ran d();for(i=0;i<s;i+)prin tf("%5d",ai=ra nd(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+)prin tf("%5d",ai);prin tf(

43、"n");for(i=1;i<7;i+)printf("请选择排序算法n");printf("冒泡排序1n");printf("直接插入排序2n");printf("简单选择排序3n");printf(”快速排序4n");printf(”希尔排序5n");printf(”堆排序6n");prin tf("退出0n");ch=getch();switch(ch)case 'O':exit(O);case'1':

44、 Bubblle_sort(a,s);break;case'2': Straightnsert_sort(a,s);break;case'3': Simple_select_sort(a,s);break;case'4': Quick_sort(a,0,s-1);break;case'5': Shell_sort(a,s);break;case'6': Heap_sort(a,s);break; default:exit(O);break;case '2': ran d();for(i=0;i<

45、;s;i+)prin tf("%5d",ai=ra nd(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=O;i<s;i+)prin tf("%5d",ai);prin tf("n");for(i=0;i<7;i+)printf("请选择排序算法n");printf("冒泡排序1n");printf("直接插入排序2n");printf("简单选择排序3n");printf(”快速排序4n");printf(”希尔排序5n");p