《数据结构排序综合设计报告（含代码）.doc》由会员分享，可在线阅读，更多相关《数据结构排序综合设计报告（含代码）.doc（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目录1需求分析22概要设计33 详细设计64调试分析115调试结果116课程设计总结13参考书目141需求分析1.1 任务与分析任务：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1) 至少采用五种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。分析：本系统实现了几种常用的排序方法，包括：插入排序、希尔排序、快速排序（递归、非递归）、堆排序。1.2 功能模块的划
2、分1.2.1 输入模块利用随机函数产生N个随机整数（20000以上），个数由用户自己输入。1.2.2选择模块在菜单中选择相应的编号来选择采用何种排序算法，算法包括：插入排序、希尔排序、快速排序（递归、非递归）、堆排序。1.2.3输出模块输出排序前或排序后的数据元素到屏幕显示，并且输出按照选择的算法排序后的数据元素到文件中保存。1.2.3排序模块插入排序思路:设有一组关键字K1,K2,.,Kn,排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-
3、1的有序序列,得到一个表长为n的有序序列.希尔排序思路：先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,.,di=1快速排序:（递归和非递归）思路:以第一个关键字K1为控制字，将K1、K2、.Kn分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。重复第（1）
4、、（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，把记录rj移动到文件左边i所指向的位置;然后在文件左边修改i指针,i+，让ri.key与x.key相比较，当ri.key小于等于x.key时，ri不移动，修改指
5、针i，i-，直到ri.keyx.key, 把记录ri移动到文件右边j所指向的位置;然后在文件右边修改j指针j-。重复上面的步骤.堆排序思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。、2/n时应满足ki=k2i和ki=k2i+1.所以先取i=n/2(它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后
6、恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。2概要设计2.1程序结构框图综合排序系统堆排序递归排序非递归排序希尔排序插入排序退出产生随机函数2.2程序流程图开始调用欢迎界面函数startface()Startface()选择操作项产生随机函数插入排序希尔排序递归排序退出堆排序非递归排序保存后的文件结束2.3头文件 #include#include#include#include2.4 ADT struct element int key;list20;struct rnodeint key;int point;2
7、.5各种操作函数：（1）创建一个数组函数：int creat()；（2）输出数组函数：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）非递
8、归的快速排序函数：void quick1(struct element a20,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.6主函数Void main()接受命令（选择要执行的操作）；处理命令；输出结果；3 详细
9、设计3.1数据类型定义#define SIZE struct element int key;listSIZE;3.2主要模块设计插入排序模块void insert_sort(element a, int n)int i, j;element 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;快速排序模块int hoare(stru
10、ct 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-;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;t
11、op=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-;while(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
12、 i,int m)/i是根结点编号,m是以i为根的子树的最后一个结点编号struct element x;int j;x.key=ai.key; /保存记录内容j=2*i; /j 为左孩子编号while(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-
13、)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); /这次比上次少处理一个记录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;4调试分析 4.1insertion_sort排序算法分析： 该算法的时间复杂度为O(n*n).直接插入排序是稳定的排序方法。当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和
14、最坏时间复杂度0(n2)差别不大。4.2shell排序算法分析： Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增量的取值。当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。由于Shell排序算法是按增量分组进行的排序，所以Shell排序算法是一种不稳定的排序算法。4.3quick排序算法分析： 快速排序主体算法时间运算约为O(log2n),划分子区函数运算量约为O(n)，所总时复杂度为O(nlog2n). 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。4.4hea
15、psort排序算法分析： 堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的深度log2n+1相关，而heapsort中对heap的调用数量级为n，所以整个堆排序的时间复杂度为O(nlog2n)。堆排序是不稳定的。5调试结果 数据由系统随机产生，不需要输入测试数据，产生数据元素的个数由用户输入。5.1欢迎界面5.2产生随机函数5.3插入排序5.4希尔排序5.5快速排序（递归、非递归）5.6堆排序6课程设计总结通过这次课程设计的学习让我学会了许多，加深了对数据结构排序算法的认识。在这次课程设计中，独立完成了每种排序算法。排序算法选了五个，包括：插入排序、希尔排序快速排序（递归、非递归）、堆
16、排序。同时也实现了随机数的生成。并把排序后的结果保存在不同的文件中。虽然在算法完成的过程中从网上参考了一些资料，但对这次课程设计的成果还是非常满意的。 这次的课程设计还有很多不足之处，如链表存储结构中的堆排序算法，当排序个数过多时，就会等待很长时间。可能时调用的函数过多的原因造成的，但排序是正确的。用指针代替函数的调用。还有就是随机数不能随时更改，只能设定一次。链表归并算法不是对链表直接操作，而是将链表中的元素放入数组中进行排序，我想了很多方法都没有想出对链表的直接操作的算法。由于时间限制，只在课程设计快结束时完成了产生随机文件这部分，我想以后有时间再来完成它。 同时在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的文件读写操作。撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。当然，还包括如何写出操作简便，感觉友好的界面。但我还是认为自己还有很多不足，希望以后能弥补。参考书目1数据结构（C语言版）。严蔚敏，清华大学出版社2数据结构习题集（C语言版）。严蔚敏，清华大学出版社3C语言课程设计案例精编。郭翠英，中国水利出版社