数据结构课程设计报告9

《数据结构课程设计报告9》由会员分享，可在线阅读，更多相关《数据结构课程设计报告9（21页珍藏版）》请在装配图网上搜索。

1、-大 连 科 技 学 院数据构造课程设计题 目 排序综合 学生专业班级指导教师职 称 副教授 所在单位 信息科学系软件教研室 教学部主任完成日期 2013年1月11日. z.-课程设计报告单*1106090119王复之专业班级网络工程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日. z.-目 录排序综合11.需求分析11.1任务描述11.2功能分析12.概要设计12

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

5、，则要进展n-1趟比拟，在将整个待排记录序列分割成为假设干子序列分别进展直接插入排序，待整个排序中的记录“根本有序时，在对全体记录进展一次直接插入排序；直接插入排序，是将一个记录插入到以排序好的有序表中，从而得到一个新的记录数增1的有序表。设整个排序有n个数，则进展n-1趟排序，即:先将序列中的第一个记录看成一个有序的子序列，然后第2个记录起逐个进展插入，直接整个序列变成按关键字非递减有序列为止；快速排序，是通过一趟排序将要排序的数据分割成独立的两局部，其中一局部的所有数据都比另外一局部的所有数据都要小，然后再按此方法对这两局部数据分别进展快速排序，整个排序过程可以递归进展，以此到达整个数据变

6、成有序序列；堆排序，主要由建立初始堆和反复重建堆这两局部的时间开销构成，它们均是通过调用Heapify实现的。2.概要设计2.1主要全程变量和数据构造(1) 数据构造：#include stdlib.h#include #define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file()(2) 算法的入口及其说明 #include #define s 100 /宏定义命令 typedef struct record /记录声明的构造体int key;

7、/定义变量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); printf( * *5. 简单项选择择排序 * n); printf( * *6. 堆排序 * n); printf( * *7. 总结 * n); printf( * *0. 退出 * n

8、); printf( * n); 以上printf( * n);为系统主菜单输出2.2程序模块构造程序划分为以下几个模块即实现程序功能所需的函数主控菜单项选择函数:menu_select() 插入排序函数:InsertSort 选择排序函数：StlectSort() 起泡排序函数：BubbleSort() 堆排序函数：heapsort 快速排序函数：Quicksort 希尔排序：Shell Sort3.详细设计3.1程序的主要构造如下列图所示。图3-1函数调用关系图其中main()是主函数，它进展菜单驱动，根据选择项10调用相应的函数3.2数据构造定义图3-2课程设计流程图3.3显示各排序算法

9、排序后的的数据。图3-3程序工作流程图3.4函数实现例如直接插入排序#include stdlib.h#include #define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file() printf( * n);printf( * *1. 直接插入排序 * n);printf( * *0. 退出 * n);printf( * n); void Straight_insert_sort(r,n) /*直接插入*/struct record r;in

10、t n; int i,j; a1=0;b1=0; for(i=1;i=n;i+) printf(%4d,ri.key); printf(n); for(i=2;i=0) & (r0.keyrj.key) b1+; rj+1=rj-; rj+1=r0; a1=a1+2; printf(*直接插入*n); for(i=1;i=n;i+) printf(%4d,ri); printf(n); printf(move:%d time, pete:%d time,a1,b1); printf(n); 4.调试分析4.1 直接插入排序将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表

11、4.2 起泡排序首先将第一个记录的关键字和第二个记录的关键字进展比拟，假设为逆序，则将两个记录交换，然后比拟第二个记录和第三个记录的关键字。依此类推，知道第N-1个和第N个记录的关键字进展过比拟为止。上述为第一趟排序。其结果使得关键字的最大被安排到最后一个记录的位置上。然后进展第二趟起泡排序，对前N-1个记录进展同样操作。一共要进展N-1趟起泡排序。4.3 直接选择排序每一趟从待排序的记录中选出关键字最小的，顺序放在以排好序的子文件的最后，知道全部记录排序完毕。4.4 希尔排序先取一个小于n的整数d，作为第一个增量，把文件全部记录全局部成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在

12、个组中进展直接插入排序：然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1dtdt-1d2d1,即所有记录放在同一组中进展直接插入排序为止。4.5 快速排序设置两个变量i、j，排序开场的时候：i=0，j=N-1； 以第一个数组元素作为关键数据，赋值给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

13、， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环完毕。4.6 堆排序堆排序的时间，主要由建立初始堆和反复重建堆这两局部的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比拟次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1。排序算法时间复杂度空间复杂度是否稳定直接插入排序OnO(1)稳定起泡排序OnO(1)稳定直接选择排序OnO(1)不稳定希尔排序On1.5O(1)不稳定快速排序O(nlog2n)O(nlog2n)不稳定堆排序O(nlog2n)

14、O(l)不稳定图4-1时间复杂度分析5.测试结果及运行效果1 运行程序进入程序开场菜单图5-1开场菜单2开场菜单中会出现四个选项：完全有序的情况；逆序的情况；随机排序的情况；退出。运行时选择了随机排序的情况，得到100个随机数的随机排序，如下列图。图5-2随机排序（3） 得出随机数字后，程序列出七个选项：冒泡排序；直接插入排序；简单项选择择排序；快速排序；希尔排序；堆排序；退出。选择冒泡排序，对100个随机数进展冒泡排序，得到结果如下列图。图5-3起泡排序（4） 为了测试该程序，下面继续尝试进展了其他几种排序方式，结果如下列图所示。图5-4直接插入排序图5-5简单项选择择排序简单项选择择排序结

15、果如上图图5-6快速排序快速排序结果如上图图5-7希尔排序希尔排序结果如上图图5-8堆排序堆排序结果如上图以上图片为各种排序的结果，排序结果后显示出各种方式排序所用移动次数和比拟次数，以方便比拟使用。参考文献1 严蔚敏 吴伟民著.?数据构造(C语言版).清华大学出版.1999年第一版2 一华等编.数据构造-使用C 语言.电子科技大学.1998年第一版3 谭浩强.C语言程序设计第二版.高等教育.2002附录 全部代码#include stdlib.h#include #define s 100typedef struct recordint key;static struct record a1

16、s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file() printf( * n); printf( * *1. 直接插入排序 * n); printf( * *2. 希尔排序 * n); printf( * *3. 冒泡排序 * n); printf( * *4. 快速排序 * n); printf( * *5. 简单项选择择排序 * n); printf( * *6. 堆排序 * n); printf( * *7. 总结 * n); printf( * *0. 退出 * n); printf( * n); void Straight_insert_sort(r,

17、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); for(i=2;i=0) & (r0.keyrj.key) b1+; rj+1=rj-; rj+1=r0; a1=a1+2; printf(*直接插入*n); for(i=1;i=n;i+) printf(%4d,ri); printf(n); printf(move:%d time, pete:%d time,a1,b1); printf(n); void Shell_sort(r,n) /*

18、 希 尔 排 序 */struct record r;int n; struct record rec,temp; int i,j,t,h; a2=0;b2=0; for(i=1;i=1) h=t; for(j=h;j=0) & (ri.keyrec.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;in;i+) printf(%4d,ri); printf(n); printf(move:%d time, pete:%d time,a3,b3); pri

19、ntf(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(%4d,ri.key); printf(n); m=n; flag=1; for(i=1;i=m-1;i+) flag=0; for(j=0;jrj+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

20、) break; printf(*冒 泡 排 序*n); for(i=0;in;i+) printf(%4d,ri.key); printf(n); printf(move: %d time, pete: %d time,a3,b3); printf(n); int 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

21、r;int i,j; rec=ri; while(ij) while(irec.key) j-; b4+; if(ij) ri+=rj; a4+; while(ij)&(ri.key=rec.key) i+; b4+; if(ij) 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(n); i=l; j=h; top=

22、-1; do while(i1) top=push(ss,top,k+1,j); j=k-1; if(top0) top=pop(ss,top,&j,&i); while(top=0)|(ij); printf(*快 速 排 序*n); for(i=1;i=s;i+) printf(%4d,ri.key); printf(n); printf(move: %d time, pete: %d time,a4,b4); void Simple_select_sort(r,n) /* 简 单 选 择 排 序 */struct record r;int n; int i,j,m; a5=0;b5=0;

23、 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.keyrm.key) m=j; b5+; if(i!=m) rec=ri; ri=rm; rm=rec; a5=a5+3; printf(*简 单 选 择*n); for(i=1;i=s;i+) printf(%4d,ri.key); printf(n); printf(move:%d time, pete:%d time,a5,b5); printf(n); void p(r,n) /* 次数排列 */i

24、nt r;int n; int rec; int i,j; for(i=1;i0) & (recrj) rj+1=rj; j=j-1; rj+1=rec; if(r=a) printf(关 键 字 移 动 次 数 排 列:n); else printf(关 键 字 比 较 次 数 排 列: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(jrj+1.key) j+

25、; b6+; if(rec.keyrj.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=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-) printf(%4d,rl.key); printf(n

26、); printf(move: %d time, pete: %d time ,a6,b6); printf(n); pete() printf( * 部 排 序 结 果 汇 总 * n); printf( - n); printf( 移动次数 比拟次数 n); printf( -n); printf( 直接插入 %6d %8d n ,a1,b1); printf( 希尔排序 %6d %8d n ,a2,b2); printf( 冒泡排序 %4d %8d n ,a3,b3); printf( 快速排序 %4d %8d n ,a4,b4); printf( 简单项选择择 %4d %8d n ,a

27、5,b5); printf( 堆的排序 %4d %8d n ,a6,b6); printf( - n);main()char ch;int i,j,t,k; printf(*n ); printf(请选择初始时数的顺序n); printf(1-完全有序的情况n); printf(2-逆序的情况n); printf(3-随机排序的情况n); printf(0-退出n); printf(*n); ch=getch(); switch(ch) case 1: rand(); for(i=0;is;i+) printf(%5d,ai=rand(5); for(i=0;is-1;i+) for(j=i+

28、1;jaj) t=ai; ai=aj; aj=t; printf(完全有序的数列为:n); for(i=0;is;i+) printf(%5d,ai); printf(n); for(i=1;i7;i+) printf(请选择排序算法n); printf( 冒泡排序-1n); printf( 直接插入排序-2n); printf( 简单项选择择排序-3n); printf( 快速排序-4n); printf( 希尔排序-5n); printf( 堆排序-6n); printf( 退出-0n); ch=getch(); switch(ch) case 0:e*it(0); case1: Bubb

29、lle_sort(a,s);break; case2: Straight_insert_sort(a,s);break; case3: Simple_select_sort(a,s);break; case4: Quick_sort(a,0,s-1);break; case5: Shell_sort(a,s);break; case6: Heap_sort(a,s);break; default:e*it(0); break; case 2: rand(); for(i=0;is;i+) printf(%5d,ai=rand(5); for(i=0;is-1;i+) for(j=i+1;js;

30、j+) if(aiaj) t=ai; ai=aj; aj=t; printf(逆序的数列为:n); for(i=0;is;i+) printf(%5d,ai); printf(n); for(i=0;i7;i+) printf(请选择排序算法n); printf( 冒泡排序-1n); printf( 直接插入排序-2n); printf( 简单项选择择排序-3n); printf( 快速排序-4n); printf( 希尔排序-5n); printf( 堆排序-6n); printf( 退出-0n); ch=getch(); switch(ch) case 0:e*it(0); case1:

31、Bubblle_sort(a,s);break; case2: Straight_insert_sort(a,s);break; case3: Simple_select_sort(a,s);break; case4: Quick_sort(a,0,s-1);break; case5: Shell_sort(a,s);break; case6: Heap_sort(a,s);break; default:e*it(0); break; case 3:printf(从0到%d获得%d个随机数:n,100-1,s);rand();/*while(k6)*/for(i=0;is;i+)printf(

32、%5d,ai=rand(5);for(i=0;i6;i+) printf(请选择排序算法n); printf( 冒泡排序-1n); printf( 直接插入排序-2n); printf( 简单项选择择排序-3n); printf( 快速排序-4n); printf( 希尔排序-5n); printf( 堆排序-6n); printf( 退出-0n); ch=getch(); switch(ch) case 0:e*it(0); case1: Bubblle_sort(a,s);break; case2: Straight_insert_sort(a,s);break; case3: Simpl

33、e_select_sort(a,s);break; case4: Quick_sort(a,0,s-1);break; case5: Shell_sort(a,s);break; case6: Heap_sort(a,s);break; default:e*it(0); break;case 0:e*it(0);default:e*it(0);数据构造课程设计总结 好的算法+编程技巧+高效率=好的程序。1. 做什么都需要耐心，做设计程序更需要耐心。一开场的时候，我写函数写得很快，可是等到最后调试的时候发现错误很隐蔽，就很浪费时间了。后来我在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比拟容易成功了。2. 做任何事情我觉得都应该有个总体规划。之后的工作按照规划逐步展开完成。对一个完整的程序设计，首先要总体规划写程序的步骤，分块写分函数写，然后写完一局部马上纠错调试，而不是一次一口气写完，然后在花几倍的时间调试。一步步来，走好一步在走下一步。写程序是这样，做工程也是这样，过我们得生活更是应该这样这样。3. 感觉一开场设计构造写函数表达的是数据构造的思想，后面的调试则更加表达了人得综合素质，专业知识，坚决耐心，锲而不舍，真的缺一不可啊。4. 通过这次课程设计，不仅仅复习了c语言相关知识，稳固了数据构造关于排序的算法等知识，更磨砺了我的意志。. z.