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

数据结构课程设计（各种排序算法的实现）#值给a[j+1].算法实现：voidinsert_sort(ElemTypea[],intn)〃待排序元素用一个数组a表示，数组有n个元素{inti,j;ElemTypet;for(i=1；i<n；i++)//i表示插入次数，共进行n-1次插入{t=a[i];//把待排序元素赋给tj=i-1;while((j>=0)&&(t<a[j])){a[j+1]=a[j];j--;}//顺序比较和移动a[j+1]=t;}}快速排序算法：在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。算法实现：voidQuickSort（SeqListR，intlow，inthigh）{〃对R[low..high]快速排序intpivotpos；//划分后的基准记录的位置if（low<high）{〃仅当区间长度大于1时才须排序pivotpos=Partition（R，low，high）；〃对R[low..high]做划分QuickSort（R，low，pivotpos-1）；//对左区间递归排序QuickSort（R，pivotpos+1，high）；//对右区间递归排序}}//QuickSort三、课程设计中遇到的难点及解决办法问题：如何实现对每趟排序结果的存储、访问？解决方法：设计一个并行的存储空间（结构体数组），存储每趟排序的结果，通过指针型参数传递存储空间的地址实现数据的实时存储。问题：如何实现结构体数组作为参数传递数据，并使数组中的数据可以真实的改变，实现类似于“&”（引用）应用的功能？解决方法：运用指针即将结构体数组的首地址作为一个结构体指针进行参数的传递，由于指针的特性从而实现数据的实时传递!四、总结课程设计是巩固所学知识理论，提高程序设计的重要环节，通过课程设计的训练，使我们能够综合应用数据结构的基础知识，加深了对于所学知识的理解，也更加懂得了实践的重要性，也明白了各种算法重要的是理解其原理，而不是死记硬背！同时让我们更加了解自身不足和知识学习缺陷，从而不断完善自我，提高自己的学习水平。在设计过程中我们真正实现了把所学知识运用于实践，逐渐培养自己的思维和逻辑能力以及实践能力，做到学以致用。五、附录—主要源程序代码及运行结果#include"stdio.h"#include"malloc.h"typedefintelemtype;typedefstruct{ //存储排序数据elemtype*data;intlength;}list;typedefstruct{ //存储每趟排序数据elemtype*sqdata;}sqlist,*linklist;/*设置一个标志位flag,将其初始值设置为非0,表示被排序的表是一个无序的表，在进行数据交换时，修改flag为0。在新一轮排序开始时，检查此标志，若此标志为1，表示上一次没有做过交换数据，则结束排序；否则继续排序；/intmaopao(list&l,linklistsql,intx){//冒泡排序intflag;for(inti=1;i<=x;i++){flag=1;//标记是否有数据交换for(intj=1;j<=x-i;j++){if(l.data[j]>l.data[j+1]){l.data[0]=l.data[j];l.data[j]=l.data[j+1];l.data[j+1]=l.data[0];flag=0;}}for(intm=1;m<=x;m++)//每趟排序结果的存储sql[i-1].sqdata[m]=l.data[m];if(1==flag)break;}returni-1; //返回排序趟数}//直接插入排序intInsertsort(list&l,linklistsql,intx){for(inti=2;i<=x;i++){if(l.data[i]<l.data[i-1]){l.data[0]=l.data[i];for(intj=i-1;l.data[0]<l.data[j];j--)l.data[j+1]=l.data[j];l.data[j+1]=l.data[0];}for(intm=1;m<=x;m++)//每趟排序结果的存储sql[i-2].sqdata[m]=l.data[m];}returni-2; //返回排序趟数}voidq_sort(list&l,intlow,inthigh){//快速排序(递归)intpivot;intleft,right;l.data[0]=l.data[low];left=low;right=high;if(low<=high){while(low<high){while((low<high) &&(l.data[high]>=l.data[0]))high--;if(low!=high){l.data[low]=l.data[high];low++;}while((low<high) &&(l.data[low]<=l.data[0]))low++;if(low!=high){l.data[high]=l.data[low];high--;}}l.data[low]=l.data[0];pivot=low;if(left<pivot)q_sort(l,left,high-1);//递归调用if(right>pivot)q_sort(l,high+1,right);}elseprintf("未输入数据！”)；}//访问一遍数据并输出最终排序结果voidtraveres(listL,intx){printf("最终排序结果：")；for(inti=1;i<=x;i++)printf("%3d",L.data[i]);printf("\n");printf("***************************************\n\n");}voidliststring(listl,linklistsql,intnum,intx){//输出每趟排序结果intz;printf("共记录有%d趟排序结果八n”,num);traveres(l,x);printf("要查看第几趟排序结果？ ")；scanf("%d",&z);printf("\n");printf("***************************************\n\n");printf("第%d趟排序结果为："，z);for(inta=1;a<=x;a++)printf("%5d",sql[z-1].sqdata[a]);printf("\n\n");}voidmain(){//主函数部分listl;intx;inty;intnum;linklistsql;printf("请输入要排序的数据的个数：")；scanf("%d",&x);if(x==0)printf("数据个数不能为0!\n")；else{l.data=(elemtype*)malloc(x*sizeof(elemtype));//申请存储空间sql=(linklist )malloc(x *sizeof(linklist));for(intq=0;q<x;q++)sql[q].sqdata=(elemtype*)malloc(x*sizeof(elemtype));//申请存储空间printf("请输入要排序的数据：\n");for(inti=1;i<=x;i++){ //接收数据printf("请输入第%~个数据："，i);scanf("%d",&l.data[i]);}printf("请输入要使用的排序方法：1、冒泡2、直接插入排序、3、快速排序\n〃)；printf("您的选择为：");scanf("%d",&y);printf("***************************************\n");switch(y){printf("您选择了“冒泡排序"\n");num=maopao(l,sql,x);liststring(l,sql,num,x);printf("***************************************\n");break;printf("您选择了"直接插入排序"\n");num=Insertsort(l,sql,x);liststring(l,sql,num,x);printf("***************************************\n");break;printf("您选择了“快速排序"\n");q_sort(l,1,x);traveres(l,x);break;default:pri