数据结构实验报告

1、报告编号：第十二组“数据结构”课程设计报告排序算法性能比较软件学生姓名： 指导教师： 陈少军 所 在 系： 电子工程系 所学专业： 计算机科学与技术 年 级： 11级计算机(2)班 2013 年 6 月 12 日目录第一章 需求分析31.1 设计目的31.2 设计目标31.3 设计理念3第二章 概要分析42.1 排序算法性能比较软件42.2 排序算法性能比较软件工作原理5第三章 详细设计63.1 各种排序思想63.2 各种排序函数实现7第四章 系统测试134.1 系统主界面显示134.2 产生随机数据排序界面144.3 自行输入数据排序界面154.4 随机产生逆序数据排序界面16第五章 性能分

2、析17第六章 使用说明17第七章 项目总结18参考文献：19第一章 需求分析1.1 设计目的设计排序算法性能比较软件，方便用户选择最快捷、方便的算法，已达到对数据的快速处理。1.2 设计目标（1）该排序算法性能比较软件实现了总共八种排序，分别是：冒泡排序、直接插入排序、希尔排序、简单选择排序、快速选择排序、归并排序、堆排序、基数排序。程序首先实现对输入的数据进行正排序，然后再分别实现八种排序的排序比较次数与交换次数。（2）该排序算法性能比较软件还实现了对八种排序的最优比较，从比较次数和交换次数两个方面进行对这些排序算法的评估，从而实现用户对最优排序算法的快速选择。1.3 设计理念排序是计算机程

3、序设计中的一种重要的操作，它的功能是将一组无序的数列重新排列成一个有序的数列，排序算法性能比较软件的设计与实现就是方便用户的需求，大大满足用户在进行数据排列时需要。排序的方法有很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。此软件通过对冒泡排序、直接插入排序、希尔排序、简单选择排序、快速选择排序、归并排序、堆排序、基数排序这几种排序进行比较。能使我们更好的掌握这些排序的基本思想及排序算法。通过该课题的设计过程,可以加深理解各种数据结构的逻辑结构、存储结构及相应运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到

4、的知识用于解决实际问题，培养我们的动手能力。第二章 概要分析2.1 排序算法性能比较软件排序算法性能比较设计主程序包括：冒泡排序、直接插入排序、希尔排序、简单选择排序、快速选择排序、归并排序、堆排序、基数排序。如图2.1所示：主程序冒泡排序堆排序基数排序归并排序希尔排序直接插入排序简单选择排序快速选择排序图2.1 排序算法性能比较软件2.2 排序算法性能比较软件工作原理排序算法性能比较软件输入无序数列，然后使用八种排序进行比较次数和交换次数的计算，从而得出用户理想下的最优排序算法。如图2.2所示：输入杂乱数组主程序冒泡排序直接插入排序希尔排序快速选择排序简单选择排序归并排序堆排序输出有序数组每

5、一个排序都给出排序的比较次数和交换次数基数排序随机无序数组随机有序数组图2.2 排序算法性能比较软件工作原理第三章 详细设计3.1 各种排序思想冒泡排序：这种排序的比较基本思想就是两两比较待排序的数据元素的大小，发现两个数据元素的次序相反时候，就进行交换，直到没有反序的数据为止。冒泡排序是一次的比较找出最小、最大值，然后将其放置序列的最后一个位置，再将剩下的从第一个位置开始至n-i的位置进行重复的操作。直接插入排序：该排序是以第n个数（需排序的数）直接与数组里已经排序的数做比较。将其插入比它大的数之前，比他小的数之后。希尔排序：先把数组分成等长的两个数组，用ri与rn/2+i做比较，小的在前、

6、大的在后，然后再把两两一组的两组做比较。就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。快速选择排序：该排序是在现有的无序数组中找最值，然后作为第一个元素，之后就是每次找最值，作为下一个元素，直至最后一个元素，排序完成。快速排序：定义两个指针，分别指向第一个与最后一个元素，这两个元素做比较，大的放前、小的放后，然后移动指针，进行下一个比较。两次这样比较排序以后，数组变成了有序数列，该算法采用为递归算法。归并排序：该排序，也是需要调用递归。先把数组对半分多次，直到每组只有两个数据时。进行对比、排序。然后再两两合并，最后做到整个数组的排序完成。堆排序：先是对堆做比较，左子树

7、小于本树，右子树大于本树，然后不停比较、交换，最后达到整个数组的排序。基数排序： 基数排序法又称“桶子法”，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序。3.2 各种排序函数实现简单选择排序：void SelectSort(Sqlist &L)/顺序表的简单选择排序操作int i,j,temp;for(i=1;iL.length;+i)compare0+;/记录的是i与length的比较j = SelectMinKey(L,i);compare0+;if(i!=j)temp=L.ri.key;L.ri.key=L.rj.k

8、ey;L.rj.key=temp;change0+=3;/交换次数加3直接插入排序：void inserSort(Sqlist &L)/直接插入排序int j;for(int i = 2 ; i=L.length; +i) compare1+;/i与lengthcompare1+;/记录的是下面选择语句的比较if(L.ri.key0;j-)compare1+;/for循环中的比较compare1+;/记录的是下面括号中要进行的比较if(L.r0.key=L.rj.key) break;L.rj+1 = L.rj;/记录后移change1+;/位置后移，交换次数加1L.rj+1 = L.r0;/

9、插入到正确位置change1+;冒泡排序：void BubbleSort(Sqlist &L)/冒泡排序int i,j,temp;for(i=1;i=L.length;i+)compare2+;/记录上面的for循环for(j=1;jL.rj+1.key)temp = L.rj.key;L.rj.key=L.rj+1.key;L.rj+1.key = temp;change2+=3;希尔排序：void ShellInsert(Sqlist &L, int dk)/以增量dk做一次希尔插入排序/前后记录的增量式dk，r0作为的是一个暂存单元，而不是哨兵，当j=0时候，表示插入位置找到int i,

10、j;for(i = dk+1; i=L.length; +i)compare3+;/上面的for循环条件比较compare3+;/下面的选择比较if(L.ri.key0; j-=dk)compare3+;/for循环compare3+;/下面的比较if(L.r0.keyL.rj.key) break;L.rj+dk = L.rj;/记录后移，查找插入位置change3+;L.rj+dk = L.r0;/插入change3+;void ShellSort(Sqlist &L)/按增量序列对书序表L做希尔排序int k;int dlta = 5,3,2,1;int t = 4;for(k=0;kt

11、;+k)compare3+;/for循环ShellInsert(L,dltak);快速排序：void Qsort(Sqlist &L,int low, int high)/对顺序表L中的子序列做快速排序int pivotloc;if(lowhigh)pivotloc = Partition(L,low,high);Qsort(L,low,pivotloc-1);Qsort(L,pivotloc+1,high);void QuickSort(Sqlist &L)/对顺序表做快速排序Qsort(L,1,L.length);堆排序：void HeadAdjust(HeadType &H , int

12、s, int m )RedType rc;int j;rc = H.rs;for(j = 2*s; j=m; j*=2)compare5+;/for循环的调教判断if(jm&(compare5+)&(H.rj.key H.rj.key ) compare5+;break;H.rs = H.rj; s = j;change5+;H.rs = rc;change5+;/插入void HeadSort(HeadType &H)/对顺序表进行堆排序RedType temp;/中间变量用于保存数值，for(int i = H.length/2 ; i0; -i)compare5+;HeadAdjust(

13、H,i,H.length);/后续的调整for(i=H.length;i1;-i)compare5+;temp=H.r1; H.r1=H.ri; H.ri=temp;/最后的一次记录相互交换change5+=3;HeadAdjust(H,1,i-1);/第一次的调整归并排序：void Merge(RedType SR,RedType TR,int i,int m,int n)int j,k;for(j=m+1,k=i;i=m&j=n;k+)compare6+=2;/for循环中的两个条件判断if(SRi.keySRj.key) change6+;TRk = SRi+;else change6+

14、;TRk =SRj+;while(i=m) compare6+;TRk+ = SRi+;change6+;while(j=n) compare6+;TRk+ = SRj+;change6+;void MSort(RedType SR,RedType TR1,int s,int t)int m;RedType TR2MAXSIZE+1;if(s=t) compare6+;/条件的判断TR1s=SRs;change6+;elsecompare6+;m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);void Me

15、rgeSort(Sqlist &L)MSort(L.r,L.r,1,L.length);基数排序：void CreatSLList(SLList &LK,Sqlist &L)int i,j; for(i=1;i=L.length;i+)compare7+;Ri.key=L.ri.key;LK.recnum = L.length;LK.keynum = 3;/设置为三位数的比较for(i=1;i=LK.recnum;i+) /将给定的数字按照三位数的格式进行拆分。百位、十位、个位 compare7+; j=LK.keynum-1;change7+=3;/下面的三个式子LK.rli.keysj-=

16、Ri.key/100;/获取的是最高位的，本示例中的是百位上的数字LK.rli.keysj-=(Ri.key%100)/10;/获取的是十位上的数字LK.rli.keysj=Ri.key%10;/获取的是个位上的数值 for(i=0;iLK.recnum;+i) /将所有的链表用链表连接起来，构成二维的链表 LK.rli.next=i+1; LK.rlLK.recnum.next=0;/链表循环 change7+;void Distribute(SLCell (&r)MAX_SPACE,int i,ArrType &f,ArrType &e) /第i趟分配int j,p;for(j=0;jRA

17、DIX;j+) compare7+;fj =0;/各子表初始化为空表for(p=r0.next; p; p=rp.next)j = rp.keysi;change7+;if(!fj) fj=p;change7+;else rej.next = p;change7+;ej =p;change7+;void Collect(SLCell (&r)MAX_SPACE,int i,ArrType f,ArrType e) /基数排序 int j,t; for(j=0;!fj;j+);/找第一个非空的子表r0.next=fj;/r0的next指向第一个非空子表的第一个结点 t=ej;change7+=2

18、; while (jRADIX-1) compare7+; for(j+;jRADIX-1&!fj;j+); compare7+; if (fj) rt.next=fj; t=ej; change7+=2; rt.next=0; change7+; void RadixSort(SLList &L)ArrType f,e; for(int i=0;iL.recnum;+i) compare7+;L.rli.next = i+1;change7+;L.rlL.recnum.next = 0;/将L改造为一个静态的链表change7+;for(i=0;i=0;j-) /控制输出一个数据compar

19、e7+; printf(%d,L.rli.keysj); printf( ); printf(n); 第四章 系统测试4.1 系统主界面显示进入该排序算法性能比较软件，系统主界面如图4.1所示：图4.1 系统主界面4.2 产生随机数据排序界面根据系统提示完成操作1，运行结果显示如图4.2所示：图4.2随机数据排序界面4.3 自行输入数据排序界面根据系统提示完成操作2，运行结果显示如图4.3所示：图4.3自行输入数据排序界面4.4 随机产生逆序数据排序界面根据系统提示完成操作3，运行结果显示如图4.4所示：图4.4随机产生逆序数据排序界面第五章 性能分析该排序算法性能比较软件实现了总共八种排序，

20、分别是：冒泡排序、直接插入排序、希尔排序、简单选择排序、快速选择排序、归并排序、堆排序、基数排序。进入界面后有三个选择，可以让计算机随机产生数，然后对其进行正序排序，并且将分别显示八种不同排序的比较次数和交换次数。也可以手动输入数据，然后进行和上述一样的操作，还可以机选出一组数据，然后按照逆序输出，最后按照上述操作输出每种排序方法的比较次数和交换次数。当然，我们所做的软件虽然存在着一定的优点，但是不免还是会有许多的缺点和不足，这些还是需要我们在以后改进，比如说，我们的程序只能显示出每种算法的比较次数和交换次数，我们只能在这方面对每组数据数据进行比较，通过这种方法来实现那种方法更适合该组数据的比

21、较，其他方面就无法比较。在这方面我们仍需改进。 第六章 使用说明该排序算法性能比较软件，可以实现八种排序算法，分别是冒泡排序、直接插入排序、希尔排序、简单选择排序、快速选择排序、归并排序、堆排序、基数排序，使用说明如下：首先启动C+6.0，运行该程序，进行程序代码的调试，你就进入了使用排序系统的欢迎界面，你会看到系统的提示符，有三种选择机选随机数据，手动输入，机选逆序随机数据，选择你所要运行的程序，进入界面然后进行相应的操作。最后按0退出程序。至此完成了此排序算法软件的使用。第七章 项目总结本次数据结构课程设计我们组选择了排序算法性能比较软件的设计与实现，在如今电脑已成为主流，成为我们生活、工

22、作的必需品。大到国家，企业，小到家庭、个人，电脑无处不体现出其优势所在。从而出现一些软件解决了当下人们许多的问题，而我们组设计的排序算法性能比较软件就是为了排序算法的优劣选择而设计的一款实用软件。排序算法是计算机程序设计数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。我们组设计的排序算法性能比较软件实现了排序算法在时间复杂度这一方面的优劣选择，本软件实现了八种常见的排序算法（冒泡排序、直接插入排序、希尔排序、简单选择排序、快速选择排序、归并排序、堆排序、基数排序）的比较次数和交换次数的比较，供用

23、户选择自己需要使用的方式。当然，我们所做的软件虽然存在着一定的优点，但是不免还是会有许多的缺点和不足，本软件虽然实现了八种排序算法的比较次数和交换次数的比较，但是这样的比较片面，只是在比较次数和交换次数这一单一的方面去衡量这些排序算法的优劣，也许在比较次数和交换次数方面这种算法够好，但是在其他方面的比较，这种排序算法也不能称其是最优的，这样就需要我们在以后的设计中再进行改进，方面用户的使用。通过本次数据结构排序算法性能比较的课程设计，我知道了，若输入的数据是无序的，使用快速排序比较快，要是输入的数据是有序的，使用插入排序排序比较快。当输入的数据量不断增加时，各种算法之间的差别是很大的。我觉得算

24、法是一门理论和实践都很强的课程，从算法和对算法的分析，几乎都是对具体问题的抽象。因而，我们需要更多地时间来理解、掌握相关的知识，还需要上级敲打代码来进行巩固。最后，对传授我们数据结构知识的陈老师说一声谢谢！参考文献：1数据结构（C语言版） 严蔚敏、吴伟民著 清华大学出版社20092数据结构题集（C语言版） 严蔚敏、吴伟民著 清华大学出版社20093C语言程序设计 刘振安著 机械工业出版社20074数据结构（C语言版） 严蔚敏著 清华大学出版社20055数据结构（C语言版） 张群哲著 西安电子科技大学出版社2008附录：源代码#include#include#include#define MAX

25、SIZE 50typedef int KeyType;#define MAXNUM 100typedef structKeyType key;RedType;RedType RMAXNUM;/定义结构体数组typedef structRedType rMAXSIZE+1;/r0闲置、或者用作哨兵单元int length;Sqlist;/顺序表的类型Sqlist L,L0,L1,L2,L3,L4,L5,L6,L7;typedef Sqlist HeadType;#define RADIX 10/关键字的基数#define MAX 8/关键字项数的最大值#define MAX_SPACE 1000

26、0typedef int KeysType;typedef structKeysType keysMAX;/关键字int next;SLCell;/静态链表的节点类型typedef struct SLCell rlMAX_SPACE; /静态链表的可利用空间 int keynum; /记录当前的关键字个数 int recnum; /静态链表的当前长度SLList;/静态链表的类型typedef int ArrTypeRADIX;int compare8;/用来记录比较的次数int change8;/用来比较交换的次数 void shuRu(Sqlist &L)/数据录入顺序表int i=1,n

27、;printf(请输入你输入的数据个数 : n);scanf(%d,&n);printf(请依次的输入各个数据值n);L.length = n;for(;i=L.length;i+)scanf(%d,&L.ri);void shuChu(Sqlist &L)/输出顺序表中的元素int i=1;printf(该顺序存储中的数据元素为：);for(;iL.length;i+)printf(%d ,L.ri);printf(%dnn,L.ri);/=简单选择排序=int SelectMinKey(Sqlist &L,int i)/在L.ri到length中找到最小值的记录int k;compare0

28、 += L.length-i;for(k=i;i=L.length;i+)compare0+;/记录的是i与length的比较compare0+;/下面的选择语句中的比较if(L.ri.keyL.rk.key)k=i;change0+;return k;void SelectSort(Sqlist &L)/顺序表的简单选择排序操作int i,j,temp;for(i=1;iL.length;+i)compare0+;/记录的是i与length的比较j = SelectMinKey(L,i);compare0+;if(i!=j)temp=L.ri.key;L.ri.key=L.rj.key;L.

29、rj.key=temp;change0+=3;/交换次数加3/=直接插入排序=void inserSort(Sqlist &L)/直接插入排序int j;for(int i = 2 ; i=L.length; +i) compare1+;/i与lengthcompare1+;/记录的是下面选择语句的比较if(L.ri.key0;j-)compare1+;/for循环中的比较compare1+;/记录的是下面括号中要进行的比较if(L.r0.key=L.rj.key) break;L.rj+1 = L.rj;/记录后移change1+;/位置后移，交换次数加1L.rj+1 = L.r0;/插入到

30、正确位置change1+;/=冒泡排序=void BubbleSort(Sqlist &L)/冒泡排序int i,j,temp;for(i=1;i=L.length;i+)compare2+;/记录上面的for循环for(j=1;jL.rj+1.key)temp = L.rj.key;L.rj.key=L.rj+1.key;L.rj+1.key = temp;change2+=3;/=希尔排序=void ShellInsert(Sqlist &L, int dk)/以增量dk做一次希尔插入排序/前后记录的增量式dk，r0作为的是一个暂存单元，而不是哨兵，当j=0时候，表示插入位置找到int i

31、,j;for(i = dk+1; i=L.length; +i)compare3+;/上面的for循环条件比较compare3+;/下面的选择比较if(L.ri.key0; j-=dk)compare3+;/for循环compare3+;/下面的比较if(L.r0.keyL.rj.key) break;L.rj+dk = L.rj;/记录后移，查找插入位置change3+;L.rj+dk = L.r0;/插入change3+;void ShellSort(Sqlist &L)/按增量序列对书序表L做希尔排序int k;int dlta = 5,3,2,1;int t = 4;for(k=0;k

32、t;+k)compare3+;/for循环ShellInsert(L,dltak);/=快速排序=int Partition(Sqlist &L,int low ,int high)/交换顺序表L中字表的rlow hingh的记录，是枢轴记录到位，并返回所在的位置，此时在它之前的记录均不大于它KeyType pivotkey;L.r0 = L.rlow;pivotkey = L.rlow.key;change4+;while(lowhigh)compare4+;/记录的是上面的while循环的条件判断compare4+;/记录下面的循环增加的终止while(low=pivotkey) -hig

33、h;compare4+;L.rlow = L.rhigh;change4+;compare4+;/记录下面的循环增加的终止while(lowhigh&L.rlow.key=pivotkey) +low;compare4+;L.rhigh = L.rlow;change4+;L.rlow = L.r0;change4+;return low;void Qsort(Sqlist &L,int low, int high)/对顺序表L中的子序列做快速排序int pivotloc;if(lowhigh)pivotloc = Partition(L,low,high);Qsort(L,low,pivot

34、loc-1);Qsort(L,pivotloc+1,high);void QuickSort(Sqlist &L)/对顺序表做快速排序Qsort(L,1,L.length);/=堆排序=void HeadAdjust(HeadType &H , int s, int m )RedType rc;int j;rc = H.rs;for(j = 2*s; j=m; j*=2)compare5+;/for循环的调教判断if(jm&(compare5+)&(H.rj.key H.rj.key ) compare5+;break;H.rs = H.rj; s = j;change5+;H.rs = rc

35、;change5+;/插入void HeadSort(HeadType &H)/对顺序表进行堆排序RedType temp;/中间变量用于保存数值，for(int i = H.length/2 ; i0; -i)compare5+;HeadAdjust(H,i,H.length);/后续的调整for(i=H.length;i1;-i)compare5+;temp=H.r1; H.r1=H.ri; H.ri=temp;/最后的一次记录相互交换change5+=3;HeadAdjust(H,1,i-1);/第一次的调整/=归并排序=void Merge(RedType SR,RedType TR,

36、int i,int m,int n)int j,k;for(j=m+1,k=i;i=m&j=n;k+)compare6+=2;/for循环中的两个条件判断if(SRi.keySRj.key) change6+;TRk = SRi+;else change6+;TRk =SRj+;while(i=m) compare6+;TRk+ = SRi+;change6+;while(j=n) compare6+;TRk+ = SRj+;change6+;void MSort(RedType SR,RedType TR1,int s,int t)int m;RedType TR2MAXSIZE+1;if(

37、s=t) compare6+;/条件的判断TR1s=SRs;change6+;elsecompare6+;m=(s+t)/2;MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);void MergeSort(Sqlist &L)MSort(L.r,L.r,1,L.length);/=基数排序=void CreatSLList(SLList &LK,Sqlist &L)int i,j; for(i=1;i=L.length;i+)compare7+;Ri.key=L.ri.key;LK.recnum = L.length;LK.k

38、eynum = 3;/设置为三位数的比较for(i=1;i=LK.recnum;i+) /将给定的数字按照三位数的格式进行拆分。百位、十位、个位 compare7+; j=LK.keynum-1;change7+=3;/下面的三个式子LK.rli.keysj-=Ri.key/100;/获取的是最高位的，本示例中的是百位上的数字LK.rli.keysj-=(Ri.key%100)/10;/获取的是十位上的数字LK.rli.keysj=Ri.key%10;/获取的是个位上的数值 for(i=0;iLK.recnum;+i) /将所有的链表用链表连接起来，构成二维的链表 LK.rli.next=i+

39、1; LK.rlLK.recnum.next=0;/链表循环 change7+;void Distribute(SLCell (&r)MAX_SPACE,int i,ArrType &f,ArrType &e) /第i趟分配int j,p;for(j=0;jRADIX;j+) compare7+;fj =0;/各子表初始化为空表for(p=r0.next; p; p=rp.next)j = rp.keysi;change7+;if(!fj) fj=p;change7+;else rej.next = p;change7+;ej =p;change7+;void Collect(SLCell (&r)MAX_SPACE,int i,ArrType f,ArrType e) /基数排序 int j,t; for(j=0;!fj;j+);/找第一个非空的子表r0.next=fj;/r0的next指向第一个非空子表的第一个结点 t=ej;change7+=2; while (jRADIX-1) compare7+; for(j+;jRADIX-1&!fj;j+); compare7+; if (fj) rt.next=fj; t=ej; change7+=2;