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

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

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

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

4、+1； /R0不是哨兵，仅做暂存单元 Rj+1=Rj； Rj=R0； exchange=TRUE； /发生了交换，故将交换标志置为真 if(!exchange) /本趟排序未发生交换，提前终止算法 return； /endfor(外循环) /BubbleSort直接插入排序（Straight Insertion Sorting）的基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。把ai插入到a0，a1，.,ai-

5、1之中的具体实施过程为:先把ai赋值给变量t,然后将t依次与ai-1,ai-2,.进行比较,将比t大的元素右移一个位置,直到发现某个j(0=j=i-1),使得aj=t或j为(-1),把t赋值给aj+1.算法实现：void insert_sort(ElemType a,int n)/待排序元素用一个数组a表示，数组有n个元素 int i,j;ElemType t;for ( i=1; i=0)& (taj) aj+1=aj; j-; / 顺序比较和移动aj+1=t;快速排序算法：在Rlow.high中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间Rlow.p

6、ivotpos-1)和Rpivotpos+1.high，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。算法实现： void QuickSort(SeqList R，int low，int high) /对Rlow.high快速排序 int pivotpos； /划分后的基准记录的位置 if(lowhigh)/仅当区间长度大于1时才须排序 pivotpos=Partition(R，low，high)；

7、/对Rlow.high做划分 QuickSort(R，low，pivotpos-1)； /对左区间递归排序 QuickSort(R，pivotpos+1，high)； /对右区间递归排序 /QuickSort三、课程设计中遇到的难点及解决办法问题：如何实现对每趟排序结果的存储、访问？解决方法：设计一个并行的存储空间（结构体数组），存储每趟排序的结果，通过指针型参数传递存储空间的地址实现数据的实时存储。问题：如何实现结构体数组作为参数传递数据，并使数组中的数据可以真实的改变，实现类似于“&”(引用)应用的功能？解决方法：运用指针即将结构体数组的首地址作为一个结构体指针进行参数的传递，由于指针的特

8、性从而实现数据的实时传递!四、总结课程设计是巩固所学知识理论，提高程序设计的重要环节，通过课程设计的训练，使我们能够综合应用数据结构的基础知识，加深了对于所学知识的理解，也更加懂得了实践的重要性，也明白了各种算法重要的是理解其原理，而不是死记硬背！同时让我们更加了解自身不足和知识学习缺陷，从而不断完善自我，提高自己的学习水平。在设计过程中我们真正实现了把所学知识运用于实践，逐渐培养自己的思维和逻辑能力以及实践能力，做到学以致用。五、附录主要源程序代码及运行结果#include stdio.h#include malloc.htypedef int elemtype;typedef struct

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

10、r(int j=1;jl.dataj+1)l.data0=l.dataj;l.dataj=l.dataj+1;l.dataj+1=l.data0;flag=0;for(int m=1;m=x;m+)/每趟排序结果的存储sqli-1.sqdatam=l.datam;if(1=flag) break;return i-1;/返回排序趟数/直接插入排序int Insertsort(list &l,linklist sql,int x)for(int i=2;i=x;i+)if(l.datail.datai-1)l.data0=l.datai;for(int j=i-1;l.data0l.dataj;

11、j-)l.dataj+1=l.dataj;l.dataj+1=l.data0;for(int m=1;m=x;m+)/每趟排序结果的存储sqli-2.sqdatam=l.datam;return i-2;/返回排序趟数void q_sort(list &l,int low,int high)/快速排序（递归）int pivot;int left,right;l.data0=l.datalow;left=low;right=high;if(low=high)while(lowhigh)while(low=l.data0)high-;if(low!=high)l.datalow=l.datahig

12、h;low+;while(lowhigh) & (l.datalow=l.data0)low+;if(low!=high)l.datahigh=l.datalow;high-;l.datalow=l.data0;pivot=low;if(leftpivot)q_sort(l,high+1,right);elseprintf(未输入数据！);/访问一遍数据并输出最终排序结果void traveres(list L,int x)printf(最终排序结果：);for(int i=1;i=x;i+)printf(%3d,L.datai);printf(n);printf(*nn);void list

13、string(list l,linklist sql,int num,int x)/输出每趟排序结果int z;printf(共记录有%d趟排序结果,n,num);traveres(l,x); printf(要查看第几趟排序结果？ );scanf(%d,&z);printf(n);printf(*nn);printf(第%d趟排序结果为：,z);for(int a=1;a=x;a+)printf(%5d,sqlz-1.sqdataa);printf(nn);void main()/主函数部分list l;int x;int y;int num;linklist sql;printf(请输入要排

14、序的数据的个数：);scanf(%d,&x);if(x=0)printf(数据个数不能为0 ！n);elsel.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(请输入要排序的数据：n);for(int i=1;i=x;i+)/接收数据printf(请输入第%d个数据：,i);scanf(%d,&l.datai);printf(请输入要使用的排序方法：1、冒泡 2、直接插入排序、3、快速排序n);printf(您的选择为：);scanf(%d,&y);printf(*n);switch(y)case 1:printf(您选择了“冒泡排序”n);num=maopao(l,sql,x);liststring(l,sql,num,x)