《数据结构中归并排序的设计与实现.doc》由会员分享，可在线阅读，更多相关《数据结构中归并排序的设计与实现.doc（19页珍藏版）》请在三一办公上搜索。
1、课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位：题 目: 归并排序的设计与实现初始条件：理论：学习了数据结构课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）输入一组数,用递归和非递归程序实现归并排序（2）分析归并排序的复杂度（3）将归并排序的思想用于外部排序中2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设
2、计、算法设计、程序实现及测试、设计体会等；（4）结束语；（5）参考文献。时间安排： 2010年元月10日14日 （第19周） 元月10日 查阅资料元月11日 系统设计，数据结构设计，算法设计元月12日-13日 编程并上机调试元月14日 撰写报告元月15日 验收程序，提交设计报告书。指导教师签名： 2010年元月10日 系主任（或责任教师）签名： 2010年元月10日 归并排序的设计和实现摘要:该程序主要由五个部分组成：把一组待排的数据信息放在结构体里，2路归并排序，对数组作一趟归并排序，对数组作归并排序，主函数 。Abstract: The program mainly consists of
3、 five parts: the a row of data to be placed on structure, the 2 - way merge sort, for a trip to the arrayMerge sort, merge sort on the array as the main function.关键字:模型化, 2路归并, 一趟归并, 归并Keywords: modeling, 2 - way merge, a trip to merge, merge 0.引言归并排序是一种稳定的内部排序，“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。无论是顺序存储
4、结构还是链表存储结构，都可在O（m+n）的时间量级上实现。利用归并的思想容易实现排序。2路归并排序：假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到不小于n/2整数个长度为2或1的有序子序列；再两两归并,如此重复，直至得到一个长度为n的有序序列为止。1.算法把握 1.1归并排序算法的具体分析咋一看，归并排序时一种“费力不讨好”的排序方法，因为最后一趟始终要对整个序列进行排序，这会使的前几趟的排序似乎是在做无用功，其实不然。对初始关键字两两分组并进行组内排序后，在下一次处理中，并不是简单地在组容量扩大一倍的基础上重新排序，而是把上一趟已经排好序的两组
5、数组重新合并成一个新的有序组。这个把两个有序组合并到一个新的有序组的过程要比单独排序快得多。归并排序的核心操作时合并有序组。对于最开始的两两分组，也可以看成是两个只含有1个关键字的组进行合并。1.2 除了核心的合并操作外，需要先把序列进行分组，每次组容量减半，直到组内只有一个关键字为止，再对组进行合并，直到所有关键字都属于一组为止。实际上，分组采用递归的方法更加方便。2.需求分析(1)通过建立一个结构体，用来存放数据信息，包括数据的个数，本身记录。(2)2路归并排序的算法，实现两两归并。(3)主函数初始化数据，选择归并排序的方法及打印数据结果。3.数据结构设计用结构体存储待排的数据。#incl
6、ude#define MAX 100 /*定义MAX是最大的允许输入数字个数*/typedef struct int n; /* n为文件中的记录个数，nMAXNUM */ int dataMAX;lqlist;4.算法设计4.1 2-路归并排序的非递归算法 /将有序的SRi.m和SRm+1.n归并为有序的TRi.n void merge(RcdType SR,RcdType&TR,int i,int m,int n) for(j=m+1,k=I;i=m&j=n;k+) /将SR中记录由小到大的并入TR if(LQ(SRi.key,SRj.key) TRk=SRi+; else TRk=SRj
7、+; if(i=m) TRk.n=SRi.m; /将剩余的SRi.m复制到TR if(j=n) TRk.n=SRj.n; /将剩余的SRi.m复制到TR/merge4.2 2-路归并排序的递归形式 void Msort(RcdType SR,RcdType&TR1,int s,int t) /将SR归并排序为TR if(s=t) TR1s=SRs;else m=(s+t)/2; /将平分为SRs.t和SRm+1.t Msort(SR,TR2,s,m); / 递归的将SRs.m归并为有序的TR2s.m Msort(SR,TR2,m+1,t); /递归地将SRm+1.t归并为有序的TRm+1.tM
8、erge(TR2,TR1,s,m,t); / 将TR2s.m和TR2m+1.t归并到TR1s.t/mergesort4.3 对顺序表L作归并排序Void mergesort(SqList &L) Msort(L.r,L.r,1,L.length);/mergesort4.4 非递归形式归并算法void merge(int r, int r1, int low, int m, int high) /* rlow到rm和rm+1到rright是两个有序段 */ int i = low, j = m + 1, k = low; while ( i = m & j = high ) /* 反复复制两个
9、段的第一个记录中较小的 */ if (ri = rj ) r1k+ = ri+; else r1k+ = rj+; while (i = m) r1k+ = ri+; /* 复制第一个段的剩余记录 */ while (j = high) r1k+ = rj+;/* 复制第二个段的剩余记录 */4.5 对 r 做一趟归并的算法 void mergePass(int r, int r1, int n, int length) int i = 0, j; /* length为本趟归并的有序子段的长度 */while(i + 2*length - 1 n) /* 归并长length的两个子段*/mer
10、ge(r, r1, i, i+length-1, i + 2*length - 1); i += 2*length; if(i + length - 1 n - 1) /* 剩下两段，后一段长度小于 length */ merge(r, r1, i, i+length-1, n-1); else /* 将剩下的一段复制到数组r1 */ for(j = i; j n; j+) r1j = rj;4.6 对整个数据进行归并的算法void mergeSort(SortObject * p ) int dataMAXNUM; int length = 1; while (length n) /* 一趟
11、归并，结果存放在数组record中*/ mergePass(p-record, record, p-n, length); length *= 2; /* 一趟归并，结果存回 */ mergePass(record, p-record, p-n, length); length *= 2; 4.7 主程序main()cout*endl;cout 归并排序的递归和非递归实现 endl;cout*endl;lqlist p;int i=0,z,m,k;cout 请输入所要比较的数字组，以10000结束： z;while(z!=10000&iz;p.n =i;cout排序前的数组是：endl;for
12、(i=0;ip.n ;i+)coutp.data i ;cout请选择需要归并排序的方法endl1.选择递归方法。endl;cout2.选择非递归方法。m;if(m=1)M(&p);else if(m=2) mergesort2(&p);else cout输入有误。endl; coutendl排序后的数组：endl;for(i=0;ip.n ;i+) /*输出排序前的数组*/coutp.datai ;coutendl;cout请选择服务:endl; if(m=1) cout1.选择非递归方法。endl; elsecout1.选择递归方法。endl;cout2.退出。k;if(m=1&k=1)M
13、(&p); /*选择递归方法进行归并排序*/else if(m=2&k=1) mergesort2(&p); /*选择非递归方法进行归并排序*/else if (k=2)return 0; coutendl排序后的数组：endl;for(i=0;ip.n ;i+) /*输出递归排序后的数组*/coutp.datai ;coutendl;return 0;5.程序的实现5.1 完整程序#include#define MAX 100typedef structint n;int dataMAX;lqlist;void merge(int a,int s1,int e1,int s2,int e2,
14、int b)int k=s1;int i=s1;while(s1=e1)&(s2=e2)if(as1=as2) /*将数组as1和数组as2中小的数据暂存到数组b中*/bk=as1;k+;s1+;else /*将数组as1和数组as2中小的数据暂存到数组b中*/ bk=as2;k+;s2+;while(s1=e1) /*将第一个数组中剩余的数据暂存到数组b中*/bk=as1; k+; s1+;while(s2=i) /*将暂存数组b中的数据村回到a中*/ak=bk;k-;void mergesort(int a,int i,int j,int b)int k;if(idata,0,q-n-1,
15、c);void merge2 (int r,int r1,int low,int m,int high)/*rlow到rm和rm+1到rright是两个有序段*/int i=low,j=m+1,k=low;while (i=m&j=high) /*反复复制两个段的第一个记录中的较小的*/if(ri=rj) r1k=ri; k+;i+;else r1k=rj;k+;j+;while(i=m) /*复制第一个段的剩余记录*/r1k=ri;k+;i+;while(j=high) /*复制第二个段的剩余记录*/r1k=rj;k+;j+;/*对r做一趟归并，结果放在r1中*/void mergepass
16、2(int r,int r1,int n,int length) /*length为本趟归并的有序子段的长度*/int i=0,j; while(i=n-2*length+1) /*剩下两段，后一段长度小于length*/merge2(r,r1,i,i+length-1,i+2*length-1);/*归并长length的两个子段*/i+=2*length;if(in-length+1) /*剩下两段，后一段长度小于length */merge2(r,r1,i,i+length-1,n-1); else /*将剩下的一段复制到数组r1 */for(j=i;j=n;j+) r1j=rj;void
17、 mergesort2(lqlist *p)int dataMAX;int length=1;int i;while(lengthn)/*一趟归并，结果存在数组record中*/mergepass2(p-data,data,p-n,length);length*=2;/*一趟归并，结果存回*/mergepass2(data,p-data,p-n,length);length*=2;main()cout*endl;cout 归并排序的递归和非递归实现 endl;cout*endl;lqlist p;int i=0,z,m,k;cout 请输入所要比较的数字组，以10000结束： z;while(
18、z!=10000&iz;p.n =i;cout排序前的数组是：endl;for(i=0;ip.n ;i+)coutp.data i ;cout请选择需要归并排序的方法endl1.选择递归方法。endl;cout2.选择非递归方法。m;if(m=1)M(&p);else if(m=2) mergesort2(&p);else cout输入有误。endl; coutendl排序后的数组：endl;for(i=0;ip.n ;i+) /*输出归并前的数组*/coutp.datai ;coutendl;cout请选择服务:endl; if(m=1) cout1.选择非递归方法。endl; elseco
19、ut1.选择递归方法。endl;cout2.退出。k; /*再次进行选择服务（另一种排序方法还是退出）*/if(m=1&k=1)M(&p); /*将用递归方法进行归并排序*/else if(m=2&k=1) mergesort2(&p); /*将用非递归方法进行归并*/else if (k=2)return 0; coutendl排序后的数组：endl;for(i=0;ip.n ;i+)coutp.datai ;coutendl;return 0;5.2 程序运行过程说明该程序的功能是实现归并排序，程序的运行过程中需要实验者输入所要进行归并排序的数字组（最多不能超过MAX个），并且以10000
20、结束，输入数字组后，程序会输出实验者输入的数字组（不包括最后实验者输入的10000），并需要实验者自己选择需要归并的方法（递归方法或非递归方法），当实验者输入一种归并排序的方法后程序会运用该方法进行归并排序，并输出该方法排序的结果，并继续需要实验者选择进行另一种排序方法还是需要退出，当实验者选择另一种方法时，程序会进行另一种归并排序的方法，并输出排序后的结果，然后程序自动结束。如果实验者在第二次选择时直接选择退出，程序不会进行另一种归并排序方法，直接结束程序。5.3 程序运行结果6.归并排序的复杂度分析递归排序所消耗的时间有两部分组成：分组时间和合并时间。给定序列中有n个元素，同时为了方便计算
21、，假设n为2的幂，这样的每次分组，会分成偶数的两部分。用于合并的时间随着元素数量的增加时线性增长的，这个时间不超过cn(c为某个常数)，所以归并算法所消耗的时间为T（n）=2T(n/2)+cn.最后化简得：T（n）=n+cnlogn.所以最后得出归并排序的时间复杂度是O（nlogn）。归并排序的最大不足在于它需要与原序列大小相同的辅助空间，而且分组合并后还需要把辅助空间的数据复制回原序列，这会进一步降低算法的速度。7.设计体会通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。做程序是一个比较累的工作，特别是当遇到困难时，程序通不过时，真的很令人沮丧。但是改正一个错误时，那种喜悦
22、心情也很令人期盼，这种心情堪比久旱见甘霖的喜悦。就是因为有这种令人身心愉悦的可能，我才得以能够整晚不睡来改程序中的不足之处。编程中有苦有乐，其中的苦乐只有亲身经历才能体会到。要想做出好的程序，必须做好忍受其间痛苦的准备。虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。我感受最深的一点是：以前用C、c+编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是
23、图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键，在每次编程之前也要根据程序的要求来选择合适的数据存储结构，例如线性表的顺序存储还是链式存储，是运用图还是运用树比较好，这些都要在设计程序之前进行认真的思索和权衡。这次实验中我也出
24、现过一些比较困难的地方。在对数据进行模型化的时候，只用数组不能足以获取数据的信息，必须建立一个结构体 。 后来在同学的指点下，意识到自己的错误。这次实验的另一个感悟就是平时生活和学习中一定要多多动手实践，只有在实践过程中才会发现自己的不足之处，发现问题的所在，并一步步寻求解决问题的方法，正是在发现问题到解决问题的这一过程，解决问题的思路就会慢慢的打开，也正是这一过程使自己慢慢的得到锻炼和发展，知识在这一过程中也得到积蓄。 总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。8.结束语本程序运用递归和非递归两种方法实现了数据的归并排序，主要是2路归并排序的过程，
25、程序运行简单易行，可操作性可靠，结果明了。参考文献1 周桂红，王超，常淑慧数.数据结构，北京邮电大学出版社2010年9月2 严蔚敏，吴伟名.据结构， 清华大学出版社 ，2001年1月3赵仲孟，张蓓.数据结构，西北工业大学出版社，2001年9月 4 郑莉，董渊，张瑞丰.C+语言程序设计。清华大学出版社，2003年1月本科生课程设计成绩评定表班级： 姓名： 学号： 序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：年 月 日
