数据结构课程设计(各种排序算法的实现)(共8页).doc

《数据结构课程设计(各种排序算法的实现)(共8页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计(各种排序算法的实现)(共8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、序功能块maopao()；、直接插入排序功能块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+

3、1的值互换),这样经过一趟冒泡排序后,假设最后下移的元素为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.

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

5、序过程。把ai插入到a0，a1，.,ai-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)，以此基准将当前无序

6、区划分为左、右两个较小的子区间Rlow.pivotpos-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=Pa

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

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

9、emtype;typedef struct /存储排序数据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

10、+)flag=1;/标记是否有数据交换for(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

11、j=i-1;l.data0l.dataj;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!=hig

12、h)l.datalow=l.datahigh;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);

13、printf(*nn);void liststring(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;link

14、list sql;printf(请输入要排序的数据的个数：);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

15、(请输入第%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);printf(*n); break;case 2:printf(您选择了“直接插入排序”n);num=Insertsort(l,sql,x);liststring(l,sql,num,x);printf(*n); break;case 3:printf(您选择了“快速排序”n); q_sort(l,1,x); traveres(l,x); break;default:printf(输入错误！);printf(按任意键结束！nnn);六、指导老师评语及成绩