数据结构课程设计(各种排序算法的实现)

1、数据结构课程设计报告题目：专业：班级：学号：姓名：指导老师：时 间：一、课程设计题目及所涉及知识点设计题目：排序算法实现知识点：malloc申请连续存储空间、冒泡排序、快速排序、直接插入排序的算法实现、结构体的宦义与调用、函数的递归调用二、课程设计思路及算法描述设计思路：1、确泄程序要实现的功能即(1)允许用户输入一组数据，任意多个。(2)由用户选择对该组数据进行排序的方法：直接插入排序、冒泡排序.快速排序。并可 以查看每趟排序的结果。2、确左程序所需要的功能块，存储结构-结构体，malloc申请存储空间，各功能函数一冒泡 排序功能块maopao():、直接插入排序功能块insertsort

2、0 :、快速排序q_sort 0：、数据访问功 能块traveres ():、数据输岀功能块liststring 0 ;主函数部分mainO :。3、编写代码具体实现各项功能，并进行调试。算法描述：冒泡排序(Bubble Sorting)的基本思想：设待排序n个元素存放在数组an中，无序区范围初始为(a(0), a(l), a(2),., an-l), 冒泡排序方法是在当前无序区内，从最上而的元素a0开始,对每两个相邻的元素ai+l和 ai(i=0, 1,., n-l)进行比较,且使值较小的元素换至值较大的元素之上(若ai>ai+l, 则ai和ai+l的值互换)，这样经过一趟冒泡排序后，

3、假设最后下移的元素为ald,则无序 区中值较大的几个元素到达下端并从小到大依次存放在ak+l,ak+2,. an-1中,这样 无序区范围变为(a0,al,a2,.,ak)°在当前无序区内进行下一趟冒泡排序。这个 过程一直到某一趟排序中不出现元素交换的动作，排序结束。整个排序过程最多执行n-1遍。 算法实现：void BubbleSort(SeqList R) /R <l.n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i» j；Boolean exchange： /交换标志for(i=l;i<n;i+) /最多做 n-1 趟排序exchange二F

4、ALSE： /本趟排序开始前，交换标志应为假 for(j=n-l;j>=i； j-) /对当前无序区Rin自下向上扫描 if (Rj+1. key<Rj. key) /交换记录RO=Rj+l：/R0不是哨兵，仅做暂存单元Rj+l=Rj： Rj=RO： exchange二TRUE； /发生了交换，故将交换标志置为真if(!exchange) /本趟排序未发生交换，提前终止算法return： /endfor (外循环) /BubbleSort直接插入排序(Straight Insertion Sorting)的基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包

5、含一个元素， 无序表中包含有n-l个元素，排序过程中每次从无序表中取岀第一个元素，将它插入到有序 表中的适当位置，使之成为新的有序表，重复n-l次可完成排序过程。把ai插入到a0, al,之中的具体实施过程为:先把ai赋值给变量t,然后将t依次与ai-l,ai-2,.进行比较，将比t大的元素右移一个位置,直到发现某个 j (0<=j<=i-l)，使得 aj<=t 或 j 为(-D,把 t 赋值给 aj+1.算法实现：void insert_sort(ElemType a,int n)/待排朿元素用一个数组a表示，数组有n个元素 int i, j；ElemType t;for

6、( i=l; i<n; i+) /i表示插入次数，共进行n-l次插入把待排序元素赋给tj 二 iT；while (j>=0)&& (t<aj) aj+l=aj; j_; /顺序比较和移动 aj+l=t; 快速排序算法.在Rlow.high中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、 右两个较小的子区间Rlow. . pivotpos-1)和REpivotpos+1. . highl 1并使左边子区间中所有 记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot, key,右边的子区间中 所有记录的关键字均大于等于pivo

7、t, key,而基准记录pivot则位于正确的位置(pivotpos) 上，它无须参加后续的排序。算法实现，void Quicksort(SeqList R, int low, int high) /对RElow. high快速排序int pivotpos： /划分后的基准记录的位置 if(low<high) /仅当区间长度大于1时才须排序pivotpos=Partition(R» low, high):/对 RLlow. high做划分Quicksort (R> low, pivotpos-1):/对左区间递归排序Quicksort (R» pivotpos+

8、1, high):/对右区间递归排序 /Quicksort三、课程设计中遇到的难点及解决办法问题：如何实现对每趟排序结果的存储、访问？解决方法：设计一个并行的存储空间(结构体数组)，存储每趟排序的结果，通过指针型参数 传递存储空间的地址实现数据的实时存储。问题：如何实现结构体数组作为参数传递数据，并使数组中的数据可以真实的改变，实现类似于“&”(引用)应用的功能？解决方法：运用指针即将结构体数组的首地址作为一个结构体指针进行参数的传递，由于指 针的特性从而实现数据的实时传递！四、总结课程设计是巩固所学知识理论，提髙程序设计的重要环节，通过课程设计的训练，使我们能够综 合应用数据结构的基

9、础知识，加深了对于所学知识的理解，也更加懂得了实践的重要性，也明白了各 种算法重要的是理解苴原理，而不是死记硬背！同时让我们更加了解自身不足和知识学习缺陷，从而 不断完善自我，提高自己的学习水平。在设计过程中我们真正实现了把所学知识运用于实践，逐渐培 养自己的思维和逻辑能力以及实践能力，做到学以致用。五、附录一主要源程序代码及运行结果#include "stdio. h"#include z/malloc h" typedef int elemtype;typedef struct /存储排序数据elemtype *data;int length;Jlist;ty

10、pedef struct /存储每趟排序数据elemtype *sqdata;sqlist, *linklist;/*设置一个标志位flag,将其初始值设置为非0,表示被排序的表是一个*无序的表，在进行数据交换时，修改flag为0。在新一轮排序开始时，检査 *此标志，若此标志为1，表示上一次没有做过交换数据，则结束排序；否则 *继续排序：*/int maopao(list & 1, linklist sql, int x) /冒泡排序int flag;for (int i=l;i<=x;i+) flag=l;/标记是否有数据交换for(int j=l;j<=x-i;j+)i

11、f (1. dataj>l. dataj+l) 1 data0 =1 datalj;1 datajj =1. datalj+1;1 dataj+1二1. data0;flag=0;for (int m=l ;m<=x;m+)/每趟排序结果的存储sqlsqdatam =1. datam;if(l=flag) break;return i-1;/返回排序趟数/直接插入排序int Insertsort(list &1,1 inklist sql,int x)for (int i=2;i<=x;i+)if (1. datai< 1. datai-l) 1. data0二

12、1 data.i:for (int j二i一1;1 data0<l dataEjl;j)1. dataj+1=1. dataj;1. dataj+l=l. data0;for (int m=l;m<=x;m+)/每趟排序结果的存储sql Li-2 sqdatam二1 datam;return i一2;/返回排序趟数void q_sort (list & 1, int low, int high) /快速排序(递归) int pivot;int left, right;1 data0二 1. dataElow-;left=low;:right二high;if(low二high

13、) while(low<high)while(low<high) && (1. datahigh>=1. data0) high;if(low!二high) 1 data low二1 datathigh; low+;while(low<high) && (1. datalow<=1. data0) low+;if(low!二high)1. data high = 1 data low; high;1 data low二1 data0;pivot=low;if(left<pivot)q_sort (1, left, high-1

14、) ;/递归调用if(right>pivot)q_sort (1, high+1, right);elseprintf 未输入数据! “);/访问一遍数据并输出最终排序结果 void traveres(list L, int x)printf (z，最终排序结果:z，); for(int i=l;i<=x;i+)printf (z/%3dz，, L. datai);printfCn3;void liststring(list 1,linklist sql,int num, int x)/输出每趟排序结果int z;printf (?，共记录有%d趟排序结果，n", num

15、);traveres(l, x);printf (-要查看第几趟排序结果？9 ;scanf &z); printfCn3;printf ("第d趟排序结果为：",z);for (int a=l:a<=x;a+)printf (，z%5d/z, sqlz-1 sqdataEa);printfCW);void mainO /主函数部分list 1;int x;int y;int num;linklist sql;printf(请输入要排序的数拯的个数：“); scanf (/z%d/z, &x);if (x=0)printf("数据个数不能为0

16、! n3 ; else1. data=(elemtype *)malloc (x * sizeof (elemtype) ;/申诘存储空间sql=(linklist )malloc(x * sizeof(linklist);for(int q=0;qx;q+)sqlq. sqdata= (elemtype *)malloc(x * sizeof (elemtype);/申请存储空间 printf(-请输入要排序的数据：)； for (int i=l;i<=x;i+)/接收数据printf (/z请输入第%d个数据i);scanf&1 dataTi)；printf C请输入要使用的

17、排序方法：1、冒泡2、直接插入排序、3、快速排序rT);printf ("您的选择为：”);scanf (“d", &y);switch(y)case 1:printfr您选择了 “冒泡排序” n");nummaopaod, sql, x);liststring(l, sql, num, x);printf Cz*n"); break:case 2:printf C您选择了 “直接插入排序” )；num=Insertsort(1, sql,x);liststring(l, sql, num, x);printf (/z*n") ； br

18、eak: case 3:printf(您选择了 “快速排序” )；q_sort (1, 1, x);traveres(l,x);break;default：printf(，?输入错误! ”)；printf C按任意键结束！ nnn");请请请请请请捉序盹翌f居的个数4 数据= tit：:tf入第4木数据：1靠賢读用的排序方法丄、冒泡冬 直接插入排序、书先ft 71；1uA uA® yA®iVA«23*快速排序gg|O»最终排序结果，12 3 4X X X X X X X X X X X X X X XX X X X X X X XXX X X XX X X X X X X x X要查看第几趟排序结果？2X X X X X X X X X X X X X X X X X X X *M-M-> X X X >C > X X X X X XX X X第2趟排序结果为:2 13 4M M M M M M JC M M M M