排序综合-课程设计报告(共22页).doc

《排序综合-课程设计报告(共22页).doc》由会员分享，可在线阅读，更多相关《排序综合-课程设计报告(共22页).doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上课 程 设 计课程设计名称： 排序综合 专 业 班 级 ： 00 学 生 姓 名 ： 00 学 号 ： 000 指 导 教 师 ： 000 课程设计时间： 2010.6.21-2010.6.25 计算机科学与技术 专业课程设计任务书学生姓名专业班级学号题 目排序综合课题性质A工程设计课题来源D自拟课题指导教师同组姓名无主要内容综合应用所学知识，设计完成一个排序综合系统。本系统拟实现以下功能：1. 直接插入排序2. 希尔排序3. 快速排序4. 堆排序5. 结果保存6. 计算排序时间系统要求采用VC6.0工具进行开发实现。任务要求 综合运用和融化所学理论知识，提高分析和解

2、决实际问题的能力，使用c语言设计一个排序综合系统。完成课程设计报告，报告中对关键部分给出图表说明。要求格式规范，工作量饱满。参考文献1 . ， 编著. . 2007年03月2 . （美）（,S.） 著， 等译. .2005年03月审查意见指导教师签字：教研室主任签字： 2010 年 6 月24 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页信息科学与工程 学院课程设计成绩评价表课程名称：数据结构课程设计设计题目：排序序号评审项目分 数满分标准说明1内 容思路清晰；语言表达准确，概念清楚，论点正确；实验方法科学，分析归纳合理；结论严谨，设计有应用价值。任务

3、饱满，做了大量的工作。2创 新内容新颖，题目能反映新技术，对前人工作有改进或突破，或有独特见解3完整性、实用性整体构思合理，理论依据充分，设计完整，实用性强4数据准确、可靠数据准确，公式推导正确5规 范 性设计格式、绘图、图纸、实验数据、标准的运用等符合有关标准和规定6纪 律 性能很好的遵守各项纪律，设计过程认真；7答 辩准备工作充分，回答问题有理论依据，基本概念清楚。主要问题回答简明准确。在规定的时间内作完报告。总 分综合意见 指导教师 年 月 日 1、 需求分析 1.1、直接插入排序思路:设有一组关键字K1,K2,.,Kn,排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列

4、,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.1.2、希尔排序思路：先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,.,di=11.3、快速排序:（递归和非递归）思路:以第一个关键字K1为控制字，将K1、K2、.Kn分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中

5、间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。重复第（1）、（2）步，直到左区处理完毕。然后退栈对一个个子区进行相类似的处理，直到栈空分区处理函数hoare思路：首先用两个指针i、j分别指向首、尾两个关键字，i=1，j=8。如对(46、56、14、43、95、10、19、72)。第一个关键字46作为控制字，该关键字所属的记录另存储在一个x变量中。从文件右端元素rj.key开始与控制字x.key相比较，当rj.key大于等于x.key时，rj不移动，修改指针j，j-，直到rj.keyx.key，把记录

6、rj移动到文件左边i所指向的位置;然后在文件左边修改i指针,i+，让ri.key与x.key相比较，当ri.key小于等于x.key时，ri不移动，修改指针i，i-，直到ri.keyx.key, 把记录ri移动到文件右边j所指向的位置;然后在文件右边修改j指针j-。重复上面的步骤.1.4、堆排序思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。、2/n时应满足ki=k2i和ki=k2i+1.所以先取i=n/2(它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不

7、结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。2、 概要设计 2.1、头文件 #include#include#include#include2.2 、ADT struct element int key;list20;struct rnodeint key;int point;2.3、各种操作函数：（1）创建一个数组函数：int creat()；（2）输

8、出数组函数：void print(struct element a20,int n)；（3）保存函数：void save(struct element aSIZE,int n, char fileName ) （4）直接插入排序函数：void insert_sort(element a, int n)（5）希尔排序函数：void shell(struct element a20,int n)；（6）快速排序函数（分区处理函数）：int hoare(struct element a20,int l,int h)；（7）非递归的快速排序函数：void quick1(struct element a

9、20,int n)；（8）递归的快速排序函数：void quick2(struct element a20,int l,int h)；（9）堆排序（调整堆的函数）：void heap(struct element a20,int i,int m)；（10）堆排序（主体函数）：void heapsort(struct element a20,int n)；（11）时间函数：start = clock();end = clock();2.4、主函数Void main()接受命令（选择要执行的操作）；处理命令；输出结果；3、 详细设计 3.1、程序源代码：#include#include#inclu

10、de#include#define SIZE struct element int key;listSIZE;/创建一个数组/int creat() int i,n; int num;n=0;printf(请输入元素个数:);scanf(%d,&num);for( i = 0;i num; i+ )listn.key = rand() % 10000;n+;return(n);/输出数组/void print(struct element aSIZE,int n) int i;for(i=0;in;i+) printf(%5d,ai .key); printf(n);/保存到文件/void s

11、ave(struct element aSIZE,int n, char fileName ) int m_wr=0; / 写入TXT文件变量 FILE *fp;if ( ( fp = fopen ( fileName, w ) ) = NULL ) printf(File writer errorn); for (int m=0; mn; m+ )m_wr = am.key; fprintf ( fp, %d , m_wr ); / 写入TXT中 fclose ( fp );/ 直接插入排序/void insert_sort(element a, int n)int i, j;element

12、 next;for(i=1; i=0 & next.key =1;i-)ai.key=ai-1.key;k=n/2;while(k=1)for(i=k+1;ia0.key)&(j=0)aj+k.key=aj.key;j=j-k;aj+k=a0;k=k/2;for(i=0;in;i+) ai.key=ai+1.key;printf(输出希尔排序的结果:n);/快速排序/int hoare(struct element aSIZE,int l,int h)/分区处理函数int i,j;struct element x;i=l;j=h;x.key=ai.key;dowhile(i=x.key)j-;

13、if(ij)ai.key=aj.key;i+;while(ij)&(ai.key=x.key)i+;if(ij)aj.key=ai.key;j-;while(ij);ai.key=x.key;return(i);void quick1(struct element aSIZE,int n) /非递归的快速排序int i,l,h,tag,top;int s202;l=0;h=n-1;tag=1;top=0;dowhile(lh)i=hoare(a,l,h);top+;stop0=i+1;stop1=h;h=h-1;if(top=0)tag=0;elsel=stop0;h=stop1;top-;w

14、hile(tag=1);void quick2(struct element aSIZE,int l,int h)/递归的快速排序int i;if(lh)i=hoare(a,l,h); /划为两个区quick2(a,l,i-1); /对左分区快速排序quick2(a,i+1,h); /对右分区快速排序/堆排序函数/调整堆的函数void heap(struct element aSIZE,int i,int m)/*i是根结点编号,m是以i为根的子树的最后一个结点编号*/struct element x;int j;x.key=ai.key; /保存记录内容j=2*i; /j 为左孩子编号whi

15、le(j=m)if(jaj+1.key) /当结点i有左,右两个孩子时,j取关键较小的孩子编号j+;if(aj.keym,以便结束循环ai.key=x.key;/堆排序的主体函数void heapsort(struct element aSIZE,int n)int i,v;struct element x;for(i=n;i0;i-)ai.key=ai-1.key;for(i=n/2;i=1;i-)heap(a,i,n); for(v=n;v=2;v-)x.key=a1.key; /堆顶堆尾元素交换a1.key=av.key;av.key=x.key;heap(a,1,v-1); /这次比上

16、次少处理一个记录for(i=0;in;i+)ai.key=ai+1.key;for(i=0;in/2;i+)int k;k=ai.key;ai.key=an-i-1.key;an-i-1.key=k;void main()int num,l,h,c;clock_t start, end;c=1;char file150 = 直接插入排序.txt;char file250 = 希尔排序.txt;char file350 = 非递归的快速排序.txt;char file450 = 递归的快速排序.txt;char file550 = 堆排序.txt;printf(*欢迎使用本系统学习各种排序*n)

17、;printf(*温馨提示：首先请生成用于排序的元素，以便进行排序*n);printf(*主菜单*n);printf(* 1 生成随机排序元素 *n);printf(* 2 直接插入排序 *n);printf(* 3 希尔排序 *n);printf(* 4 非递归的快速排序 *n);printf(* 5 递归的快速排序 *n);printf(* 6 堆排序 *n);printf(* 0 退出 *n);printf(*n);while(c!=0) printf(*请输入0-6进行操作 n);scanf(%d,&c);switch(c)case 1:num=creat();print(list,n

18、um);break;case 2:start = clock();insert_sort(list,num);end = clock(); print(list,num); save(list,num, file1) ;printf(The time : %d msn, end - start );break;case 3:start = clock();shell(list,num);end = clock(); print(list,num); save(list,num,file2) ;printf(The time : %d msn, end - start );break;case

19、4:start = clock();quick1(list,num);end = clock(); print(list,num); save(list,num,file3) ;printf(The time : %d msn, end - start );break;case 5:l=0;h=num-1;start = clock();quick2(list,l,h);end = clock();printf(输出递归快速排序结果:n); print(list,num);save(list,num,file4);printf(The time : %d msn, end - start );

20、break;case 6:start = clock();heapsort(list,num);end = clock();print(list,num); save(list,num,file5);printf(The time : %d msn, end - start );break;/main end4、 调试分析 4.1、insertion_sort排序算法分析： 该算法的时间复杂度为O(n*n).直接插入排序是稳定的排序方法。当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。4.2、shell排序算法分析： Shell排序

21、算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。由于Shell排序算法是按增量分组进行的排序，所以Shell排序算法是一种不稳定的排序算法。4.3、quick排序算法分析： 快速排序主体算法时间运算约为O(log2n),划分子区函数运算量约为O(n)，所总时复杂度为O(nlog2n). 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。4.4、heapsort排序算法分析： 堆排序中heap算法的时间复杂度与堆所对应的完全二

22、叉树的深度log2n+1相关，而heapsort中对heap的调用数量级为n，所以整个堆排序的时间复杂度为O(nlog2n)。堆排序是不稳定的。5、 调试结果 5.1系统操作5.1.1、主菜单界面5.1.2、生成排序元素5.1.3直接插入排序5.1.4、希尔排序5.1.5非递归的快速排序5.1.6递归的快速排序5.1.7堆排序5.2、测试数据5.2.1、 100个数据元素5.2.2、 1000个数据元素5.2.3、10000个数据元素5.2.4、个数据元素 课程设计总结 通过这次课程设计的学习让我学会了许多。让我对我们的专业知识有了很大 理解！我对专业的课程有了初步的认识。 在这次课程设计中，

23、独立完成了在两种存储结构下的每种排序算法。排序算法共有七个：插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。同时也实现了随机数的生成。并把排序后的结果保存在不同的文件中。虽然在算法完成的过程中也在网上查阅了一些资料，但对这次课程设计的成果还是非常满意的。 这次的课程设计还有很多不足之处，如链表存储结构中的堆排序算法，当排序个数过多时，就会等待很长时间。可能时调用的函数过多的原因造成的，但排序是正确的。用指针代替函数的调用。还有就是随机数不能随时更改，只能设定一次。链表归并算法不是对链表直接操作，而是将链表中的元素放入数组中进行排序，我想了很多方法都没有想出对链表的直接操作的

24、算法。由于时间限制，只在课程设计快结束时完成了产生随机文件这部分，我想以后有时间再来完成它。同时在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的文件读写操作。撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。但我还是认为自己有些不足，希望以后能弥补这些不足。 所以，这次的课程设计我学会了很多，不光让我认识了本专业知识，还让我学了一定的心境！那就是做事情的时候即使不会做也不能慌张，要慢慢放下心来，不要光想自己怎么、怎么不会了！不要去想不会，而是冷下心来慢慢思考、思考。这样你就会有了思虑的。专心-专注-专业