数据结构各种排序算法的课程设计实验报告(c语言版)

《数据结构各种排序算法的课程设计实验报告(c语言版)》由会员分享，可在线阅读，更多相关《数据结构各种排序算法的课程设计实验报告(c语言版)（31页珍藏版）》请在装配图网上搜索。

1、滁州学院课程设计报告课程名称：数据结构设计题目排序算法实现及比较系别：计算机信息工程学院专业：计算机科学与技术组别：第*组起止日期： 12年5月1日 12年6月1日指导教师： *计算机与信息工程学院二C一二年制课程设计题目排序算法实现将比较组长*学号20*班级*系别计算机与信息工程学院专业计算机科学与技术组员*指导教师*课程设计目的加深对常见排序算法理解通过程序比较常见算法优越性 熟悉加深对数据结构的了解及认识课程设计所需环境Windows xp； VC+6.0课程设计任务要求实现常见排序算法程序化测试程序比较算法优越性了解常见算法的实际应用课程设计工作进度计划序号起止日期工作内容分工情况1分

2、析实验类容2分工3算法改编成程序4将子程序合并及调试 数据测试及记录5编写报告课程设计任务书系（教研室）审核意见：系（教研室）主任签字：年月日指导教师签字:日年 月目录1. 引言42. 需求分析 43. 详细设计43.1 直接插入排序43.2 折半排序53.3 希尔排序63.4 简单选择排序 63.5 堆排序63.6 归并排序73.7 冒泡排序94. 调试105. 调试及检验 115.1 直接插入排序 115.2 折半插入排序 115.3 希尔排序125.4 简单选择排序125.5 堆排序135.6 归并排序145.7 冒泡排序146. 测试与比较156.1 调试步骤 156.2 结论167.

3、 实验心得与分析168. 附录178.1 直接插入排序178.2 折半插入排序188.3 希尔排序208.4 简单选择排序228.5 堆排序238.6 归并排序268.7 冒泡排序298.8 主程序301.引言伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方 便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。经常查找资料的朋友都会知道，面对海量的资料，如果其查找的资料没有进行排序，那么其查找 资料将会是一件非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。理论上排序算法有很多种，不过本课程设计只涉及到七种算法。这七种算法共

4、包括：直接插入排 序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。本课程设计通过对这七种算法的运行情况进行对比，选择最优秀的算法来提供给用户。希望通过 我们的努力能给用户解决一些问题，带来一些方便。2.需求分析本课程题目是排序算法的实现，由于各方面的原因，本课程设计一共要设计七种排序算法。这七 种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒 泡排序。七种排序各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。为了小组分工的方便，我们特意把子函数写成Header File文件。这样操作不仅可以使小组分工更 加简洁明了，还可以方便

5、子函数的调用，更可以使写主函数时一目了然。为了运行时的方便，我们将七种排序方法进行编号，其中1 为直接插入排序， 2 为折半插入排序， 3 为希尔排序， 4 为简单选择排序， 5 为堆排序， 6 为归并排序， 7 为冒泡排序。通过这七种选项， 可以让用户简单明了的去选择使用哪一种排序方法。本课程就是通过对5 组占用内存大小不同的数据调试来测试这七种算法运行的时间长短，从中选 择面对不同大小的文件时，哪一种算法更为快捷。软件环境本课程设计所用操作系统为Windows-XP操作系统，所使用的软件为Microsoft Visual C+6.0；3.详细设计3.1 直接插入排序算法思想：直接插入排序是

6、一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排 好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同 时后移记录。整个排序过程为进行 n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子 序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。程序实现及核心代码的注释：for (i = 1 ; i r.length ;+i )for(j=0;j i;+j) if(r.basei j; -i ) r.basei = r.basei-1;r.basej = temp; r.baser.length =0;3.2

7、折半排序/保存待插入记录/记录后移/插入到正确的为位置(1)算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间 和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动 次数 不变。因此，这般插入排序的时间复杂度仍为O (n2)。程序实现及核心代码的注释：void zb(FILE *fp)for ( i = 1; i r.length ; i+ )temp=r.basei;low=0;high=i-1;while( low = high )m

8、= (low+high)/2; if ( temp =high+1; -j ) r.basej+1= r.basej;r.basehigh+1=temp;/对顺序表作折半插入排序将r.basei寄存在temp中在 baselow到 keyhigh中折 半查找有序插入的位置/折半/插入低半区/插入高半区/记录后移/插入3.3 希尔排序(1)算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的 记录“基本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成不是简单的“逐段分 割”，而是将分隔某个“增量”的记录组成一个子序列。程序实现及核心代码的注释：for

9、(k = 0; k 10 ; k+)m = 10 - k;for( i = m ; i r.length; i + )if(r.basei = 0 & temp r.basej; j -= m)r.base j + m = r.basej;/记录后移，查找插入位置r.base j + m = temp;/插入3.4 简单选择排序/i 为排好序的数的下标，依次往后存放排/好序的数/将待放入排好序的数的下标的数保存/找出未排序的数中最小的数的循环；1算法思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当 中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一

10、个数比较为止。 程序实现及核心代码的注释： for ( i = 0 ; i r.length ; i+ ) temp=r.basei;for( j = i,m = j +1 ; m r.basem)把下标为j的数与i数互换;j = m;r.basei = r.basej;r.basej = temp;3.5 堆排序1算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将 序列所存储的元素AN看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于（或不小于）其左右孩子（若存在）结点的元素。算法的平均时间复杂度为O(N l

11、og N)。程序实现及核心代码的注释：void dp(FILE *fp)for(i = r.length / 2;i = 1 ; -i)HeapAdjust(r.base,i,r.length);for(i = r.length ;i = 2 ; -i)temp = r.base1;r.base1 = r.basei;r.basei = temp;HeapAdjust(r.base,1,i-1);void HeapAdjust(char *r,int k,int m)i=k; x=ri; j=2*i;while(j=m)if( (jrj+1) )j+;if(xrj)ri =rj;i = j;j

12、 *= 2;elsej = m + 1;ri = x;3.6 归并排序把 r.basel.r.length健成大顶堆将r.base1.i-1重新调整为大顶堆/沿 key 较大的孩子节点向下筛选 /j 为 key 较大的记录的下标/插入字符比当前的大，交换/否则比较停止。/把字符 x 插入到该位置，元素插入实现算法思想：先将相邻的个数为1的每两组数据进行排序合并；然后对上次归并所得到的大小为2即排好序的一组数据。/对相邻两组数据进行组合排序；/j 为合并的第二组元素的第一个数位置/ k 为存入 t 中的数的位置；/依次排列两组数据/将第一组数据与第二组数据分别比较；/第一组数据先排完的情况对数据

13、进行每组s个数的归并排序；/i 为要合并两组元素的第一个数位置/i+s-1 为要合并的第一组元素的最后一数位置、i+2*s-l为要合并的两组元素/最后一个数位置；考虑n不能被s整除，如果余下的数少于2*s但大于s,也就是余下的数不能凑成/两组，凑一组有余,则把余下的数进行组的组进行相邻归并；如此反复，直到最后并成一组程序实现及核心代码的注释：void merge(SqList6 r,int h ,int m ,int w ,SqList6 t)int i,j,k;i = h ;j = m + 1;k =h-1；while(i = m)&(j = w)k+;if(r.basei m)while(

14、j = w) t.base+k=r.basej+;elsewhile(i = m) t.base+k=r.basei+;void tgb(int s,int n,SqList6 r,SqList6 t)int i=1;while(i=(n-2*s+1)merge(r,i,i+s-1,i+2*s-1,t);i=i+2*s;if(i(n-s+1)merge(r,i,i+s-1,n,t);elsewhile(i=n)t.basei=r.basei+;void gb(FILE *fp)n = r.length;SqList6 t;t.base=(char *) malloc(r.stacksize*s

15、izeof(char);while(sn)tgb(s,n,r,t);s*=2;if(sn) tgb(s,n,t,r); s *= 2; elsei=0;/合，并对其进行排序；如果余下的数少于S,则余下的数进行组合,并进行排序；/ 归并主函数；给待排序的数组t申请内存；/每组元素不断增加循环进行合并排序；/ s为每组元素的个数、n为元素总个数、r 为原数组，t为待排序的数组，进行归并排 /序；把元素个数相同的两组合并 并进行重新 /定义成新的一组，此组元素个数为 2*s；当元素个数小于n时，对其进行合并排序； 当元素个数大于n时，对剩下的数排序；while(i=n)r.basei=t.basei

16、+1;i+;3.7 冒泡排序算法思想：1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即 可得到第一个数是所有数中最小的数；2、然后再将数组的最后一个数与倒数第二个数进行比较，并 将较小的数放于两个数中较前的位置，依次比较到第二个数，3、如此循环到只剩最后两个比较，即得到排好序的一组数。程序实现及核心代码的注释:for( i=0; i = i;j -) if(r.basej+l r.basej)temp = r.basej+1; r.basej+1 = r.basej; r.base

17、j = temp;/ i为排好序的数的下标，依次往后存放排好序的数；从后往前依次两两比较，较小的被调换到前面；比较相邻两个数，如果后面的小于前面的，向下执行;将后面的较小的数保存起来；将前面的较大的数放在后面较小的数的位置；将较小的数放在前面的较大的数的位置；请选择:ainnexe检测主函数是否能够稳定运行（如图4-1）：1入入序择甯- j - jkhr - G - -辜尔聶幵泡岀请选择:请输入:序炜序尉幕- T-_.p - 捋半尔畀开泡出 育W归幕 12L3456:704.调试Pee生名 anJ1m1.5s0.2s6.0s0.1s3m5.5s1.1s23s0.1s0.1s24s200KB-2

18、0s3.8s-0.1s1m512KB-1m14s-3m1024KB3m1m0.2s0.3s10m-：表示时间过长6.2 结论通过实验结果的比较与分析我们发现：直接插入排序、冒泡排序、简单选择排序及折半插入排序 是低效率的排序方式；所以我们实际编程重要尽可能的避免他们的出现；我们应该用较先进的归并 排序及堆排序。7. 实验心得与分析通过本次课程设计，我们小组的每个成员都学到了很多东西。首先要说的是我们的编程能力，在 这一次的课程设计中我们的编程能力均得到了一定程度的提升。并且通过这次课程设计，我们更加 熟悉了如何使用Header File文件。本次课程设计，让我们对于直接插入排序，折半插入排序，

19、希尔 排序，简单选择排序，堆排序，归并排序，冒泡排序等七种排序算法的思想有了进一步的认识，同 时对七种算法的应用有了更进一步的掌握。通过这次课程设计，我们对于解决实际问题的能力有了 进一步提高。最重要的是，这次课程设计大大的训练了我们的小组团队协作能力。通过这次课程设 计我们小组各成员的团队协作能力都有了很大的提升。这种团队协作能力对于我们学编程的来说是 极其重要的，同时也是必不可少的。当然，我们写程序的时候遇到了很多困难。而且在程序调试过程中出现了很多错误与警告，不过 在队员及老师的帮助下均得到了解决。当程序可以运行后，程序的运行过程中同样也也出现了很多 错误，甚至出现了不兼容的情况。不过，

20、后来在队员及老师的帮助下也均得到了解决。然而，我们 的程序还有一点瑕疵让我们感到美中不足。那就是在归并算法运行过程中，当输入为9 个字符时， 排序结果会出现偶然误差。经过分析，我们认为这点是系统的问题。不过，这仍然是一点让我们感 到遗憾的地方。8.附录8.1 直接插入排序#include#include#define Q 1000typedef struct char *base ;int stacksize ;int length;SqList1;void zj(FILE *fp)SqList1 r;int i,j;char temp,*p;r.base=(char *) malloc(Q*

21、sizeof(char); r.stacksize = Q;r.length = 0; while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char); if(!r.base)printf(ERROR); return ;r.base = r.base + r.stacksize; r.stacksize += Q; r

22、.length -;r.base -;r.base= r.base - r.length;for (i = 1 ; i r.length ;+i ) for(j=0;j i;+j) if(r.basei j; -i ) r.basei = r.basei-1;r.basej = temp; r.baser.length =0; rewind(fp);fprintf(fp,%s,r.base); fclose(fp);free(r.base);8.2 折半插入排序 #include #include #define Q 1000 typedef struct char *base ;int st

23、acksize ;int length;SqList2;void zb(FILE *fp)SqList2 r;int i,j ,m, low, high;char temp;r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.length = 0;while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = r.stacksize ) r.base= r.base - r.length;r.base=(char *) realloc(r.base,(

24、r.stacksize + Q) * sizeof(char); if(!r.base)printf(ERROR);return ;r.base = r.base + r.stacksize;r.stacksize += Q;r.length -;r.base -;r.base= r.base - r.length;for ( i = 1 ; i r.length ; i+ )temp=r.basei;low=0;high=i-1;while( low = high )m = (low+high)/2;if ( temp =high+1; -j )r.basej+1= r.basej;r.ba

25、sehigh+1=temp;r.baser.length =0; rewind(fp);fprintf(fp,%s,r.base); fclose(fp);free(r.base);8.3 希尔排序 #include #include #define Q 1000 typedef struct char *base ;int stacksize ;int length;SqList3;void xe(FILE *fp)SqList3 r;int i,j,k,m;char temp;r.length = 0;r.base=(char *) malloc(1000*sizeof(char);r.s

26、tacksize = 1000;while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char); if(!r.base)printf(ERROR);return ;r.base = r.base + r.stacksize;r.stacksize += Q;r.length -;r.base -;r.base= r.ba

27、se - r.length;for(k = 0; k 10 ; k+)m = 10 - k;for( i = m ; i r.length; i + )if(r.basei = 0 & temp r.basej; j -= m) r.base j + m = r.basej;r.base j + m = temp;rewind(fp);fprintf(fp,%s,r.base); fclose(fp);free(r.base);8.4 简单选择排序#include #include #define Q 1000 typedef struct char *base ; int stacksize

28、 ; int length;SqList4;void jd(FILE *fp)SqList4 r;int i,j ,m;char temp;r.base=(char *) malloc(1000*sizeof(char); r.stacksize = 1000;r.length = 0; while(!feof(fp)fscanf(fp,%c,r.base); r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length; r.base=(char *) realloc(r.base,(r.stacksize +

29、Q) * sizeof(char); if(!r.base)printf(ERROR);return ;r.base = r.base + r.stacksize;r.stacksize += Q;r.length -;r.base -;r.base= r.base - r.length;for ( i = 0 ; i r.length ; i+ )temp=r.basei;for( j = i,m = j +1 ; m r.basem)j = m;r.basei = r.basej;r.basej = temp;r.baser.length =0; rewind(fp);fprintf(fp

30、,%s,r.base);fclose(fp);free(r.base);8.5 堆排序#include #include#define Q 1000typedef struct char *base ;int stacksize ;int length;SqList5;void HeapAdjust(char *r,int s,int m);void dp(FILE *fp)SqList5 r;int i,j;char temp,*k;r.length = 0;r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.base

31、+= 1; while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = (r.stacksize - 1) )r.base= r.base - r.length - 1;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char); if(!r.base)printf(ERROR);return ;r.base = r.base + r.stacksize;r.stacksize += Q;r.length -;r.base -;r.base= r.ba

32、se - r.length - 1;for(i = r.length / 2;i = 1 ; -i)HeapAdjust(r.base,i,r.length);for(i = r.length ;i = 2 ; -i)temp = r.base1;r.base1 = r.basei;r.basei = temp;HeapAdjust(r.base,1,i-1);k = (char *) malloc(r.length+1)*sizeof(char);for(i = r.length,j = 0; i = 1; i-,j+) kj = r.basei;kj=0;rewind(fp);fprint

33、f(fp,%s,k);fclose(fp);free(k);free(r.base);void HeapAdjust(char *r,int k,int m)int i,j;char x;i=k; x=ri; j=2*i;while(j=m)if( (jrj+1) )j+;if(xrj)ri =rj;i = j; j *= 2;elsej = m + 1;ri = x;8.6 归并排序#include #include#define Q 1000 typedef struct char *base ;int stacksize ;int length;SqList6;void merge(Sq

34、List6 r,int h,int m,int w,SqList6 t) int i,j,k;i = h; j = m + 1; k = h - 1; while(i = m)&(j = w)k+;if(r.basei m)while(j = w) t.base+k=r.basej+;elsewhile(i = m) t.base+k=r.basei+; void tgb(int s,int n,SqList6 r,SqList6 t)int i=1;while(i=(n-2*s+1)merge(r,i,i+s-1,i+2*s-1,t);i=i+2*s;if(i(n-s+1)merge(r,i

35、,i+s-1,n,t);elsewhile(i=n)t.basei=r.basei+;void gb(FILE *fp)SqList6 r;r.length = 0;r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.base += 1; while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = (r.stacksize - 1) )r.base= r.base - r.length - 1; r.base=(char *) realloc(r.

36、base,(r.stacksize + Q) * sizeof(char); if(!r.base)printf(ERROR);return ;r.base = r.base + r.stacksize;r.stacksize += Q;r.length -;r.base= r.base - r.length - 2;int i,j,n,s=1;n = r.length;SqList6 t;t.base=(char *) malloc(r.stacksize*sizeof(char);while(sn)tgb(s,n,r,t);s*=2;if(sn) tgb(s,n,t,r); s *= 2;

37、 elsei=0;while(i=n)r.basei=t.basei+1;i+;r.baser.length =0; rewind(fp);fprintf(fp,%s,r.base); fclose(fp); free(t.base); free(r.base);8.7 冒泡排序#include#include#define Q 1000typedef struct char *base ;int stacksize ;int length;SqList7;void mp(FILE *fp)SqList7 r;int i,j ,m;char temp;r.length = 0;r.base =

38、 (char *) malloc(1000*sizeof(char);r.stacksize = 1000;while(!feof(fp)fscanf(fp,%c,r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char); if(!r.base)printf(ERROR); return ;r.base = r.base + r.stacksize; r.stacksi

39、ze += Q;r.length -;r.base -;r.base= r.base - r.length;for( i=0; i = i;j - ) if(r.basej+1 r.basej) temp = r.basej+1; r.basej+1 = r.basej; r.basej = temp;m = 0;if( m ) break;r.baser.length =0; rewind(fp);fprintf(fp,%s,r.base);fclose(fp); free(r.base);8.8 主程序#include#includezj.h #includezb.h#includexe.

40、h#includejd.h#includemp.h#includedp.h#includegb.hvoid main（）FILE *fp;int sign;while（sign != 0）printf（请选择：n）;printf（” 6c 1直接插入排序 n,）; printf（ %6c 2折半插入排序n,）; printf（ %6c 3希尔排序 n,）;printf（” %6c 4简单选择排序 n,）; printf（ %6c堆排序n,）;printf（ %6c归并排序n,）;printf（” %6c 冒泡排序 n,）; printf（ %6c 0退出 n,）;printf（”请输入：”）； scanf（%d,&sign）;if（fp=fopen（kcsj.txt,r+）=NULL） printf（ File open error!n）； return；switch（sign）case 1:zj（fp）；break；case 2: zb(fp); break;case 3: xe(fp); break;case 4:jd(fp); break;case 5: dp(fp); break;case 6: gb(fp); break;case 7: mp(fp); break;case 0: break;printf(n n n);