《数据结构》课程设计_排序算法比较以及算术表达式求值

XXXXX大学《数据结构》课程设计报告排序算法比较算术表达式求值班级：学号：姓名：指导老师：数据结构课程设计——排序算法比较、表达式求值-2-目录一课程设计1——排序算法比较一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二课程设计2——算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码三感想体会与总结数据结构课程设计——排序算法比较、表达式求值-3-排序算法比较一、需求分析利用随机函数产生N个随机整数（N=500，1000，1500，2000，2500，…,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。二、程序的主要功能1.用户输入任意个数，产生相应的随机数2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。三、程序运行平台VisualC++6.0版本四、数据结构本程序的数据结构为线形表，线性顺序表、线性链表。。1、结构体：typedefstruct{int*r;//r指向线形表的第一个结点。r[0]闲置，不同的算法有不同的用处，如用作哨兵等。intlength;//顺序表的总长度}Sqlist;2、空线性表StatusInitSqlist(Sqlist&L){L.r=(int*)malloc(MAXSIZE*sizeof(int));//分配存储空间if(!L.r){printf(存储分配失败！);exit(0);}//存储分配失败数据结构课程设计——排序算法比较、表达式求值-4-L.length=0;//初始长度为0returnOK;}五、算法及时间复杂度（一）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。（5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1=I=N）个记录交换。（6）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序（二）时间复杂度分析排序算法最差时间时间复杂度是否稳定？插入排序O(n2)O(n2)稳定冒泡排序O(n2)O(n2)稳定数据结构课程设计——排序算法比较、表达式求值-5-快速排序O(n2)O(n*log2n)不稳定选择排序O(n2)O(n2)稳定堆排序O(n*log2n)O(n*log2n)不稳定基数排序O(n*log2n)O(n2)稳定10000个数据的时间比较：算法名称用时直接插入排序0.25折半插入排序0.219起泡排序0.704快速排序0.016选择排序0.39堆排序0.0001基数排序0.016六、测试用例1、首先选择需要排序的数字个数，比如输入5000。数据结构课程设计——排序算法比较、表达式求值-6-2、系统显示出随机产生的随机数。用户选择排序方式，比如选择1.直接插入排序数据结构课程设计——排序算法比较、表达式求值-7-3、系统将随机数排序后整齐的显示出来。4、用户可以选择继续排序或者退出系统。七、程序源代码/**********************************************************************************************第六题：排序算法比较设计要求：利用随机函数产生N个随机整数（N=500，1000，1500，2000，2500，…,30000），数据结构课程设计——排序算法比较、表达式求值-8-利用直接插入排序、折半插入排序，起泡排序、快速排序、||选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。************************************************************************************************/#includestdio.h#includestdlib.h#includetime.h//计时#defineERROR0#defineOK1#defineOVERFLOW-2#defineMAXSIZE100000//用户自己规定排序的数字的长度typedefintStatus;typedefstruct{int*r;//r[0]闲置intlength;//顺序表的总长度}Sqlist;//构造一个空线性表StatusInitSqlist(Sqlist&L){L.r=(int*)malloc(MAXSIZE*sizeof(int));//分配存储空间if(!L.r){printf(存储分配失败！);exit(0);}//存储分配失败L.length=0;//初始长度为0returnOK;}//输入随机数并显示在界面上StatusScanfSqlist(int&N,Sqlist&L){inti;printf(请输入要排序的元素个数N:);scanf(%d,&N);for(i=1;i=N;i++)L.r[i]=rand();//随机产生样本整数数据结构课程设计——排序算法比较、表达式求值-9-printf(\n\n);printf(随机产生了%d个随机数，它们是：\n,N);for(i=1;i=N;i++){printf(%7.2d,L.r[i]);}printf(\n);L.length=N;//存储线性表的长度returnOK;}//输出排序之后的数据StatusPrintfSqlist(intN,SqlistL){inti;printf(数据个数：);//输出数据个数printf(%d\n,L.length);printf(排序后的数据：(从左向右依次增大)\n);//输出数据for(i=1;i=N;i++)printf(%7.2d,L.r[i]);printf(\n);returnOK;}//***************************************************************//直接插入排序//***************************************************************StatusInsertSort(Sqlist&L)//参考书P265算法10.1{inti,j;if(L.length==0){printf(要排序的数据为空！);returnERROR;}for(i=2;i=L.length;i++){if(L.r[i]L.r[i-1])//将L.r[i]插入有序子表{L.r[0]=L.r[i];//复制为监视哨L.r[i]=L.r[i-1];数据结构课程设计——排序算法比较、表达式求值-10-for(j=i-2;L.r[0]L.r[j];j--){L.r[j+1]=L.r[j];//记录后移}L.r[j+1]=L.r[0];//插入到正确位置}}returnOK;}//***************************************************************//折半插入排序//***************************************************************StatusBInsertSort(Sqlist&L)//参考书P267算法10.2{inti,j,mid,low,high;if(L.length==0){printf(要排序的数据为空！);returnERROR;}for(i=2;i=L.length;i++){L.r[0]=L.r[i];//将L.r[i]暂存在L.r[0]low=1;high=i-1;while(low=high)//在r[low..high]中折半查找有序插入的位置{mid=(low+high)/2;if(L.r[0]L.r[mid])//插入点在低半区{high=mid-1;}else{low=mid+1;//插入点在高半区}}//whilefor(j=i-1;j=high+1;j--)//插入点后的数据后移{L.r[j+1]=L.r[j];}L.r[high+1]=L.r[0];//将数据插入数据结构课程设计——排序算法比较、表达式求值-11-}//forreturnOK;}/********************************************************************************希尔排序*********************************************************************************///参考书P272算法10.4及10.5/*StatusShellInsert(Sqlist&L,intdk)//希尔插入排序{inti,j;//前后位置的增量是dkfor(i=dk+1;i=L.length;i++)//r[0]只是暂存单元，不是哨兵，{if(L.r[i]L.r[i-dk])//将L.r[i]插入有序增量子表{L.r[0]=L.r[i];//暂存L.r[0]for(j=i-dk;j0&&L.r[0]L.r[j];j-=dk){L.r[j+dk]=L.r[j];//记录后移,查找插入位置}L.r[j+dk]=L.r[0];//插入}}returnOK;}StatusShellSort(Sqlist&L,intdlta[5],intt)//希尔排序{inti;if(L.length==0){printf(要排序的数据为空！);returnERROR;}for(i=0;it;i++){ShellInsert(L,dlta[i]);//一趟增量为dlta[k]的插入排序数据结构课程设计——排序算法比较、表达式求值-12-}returnOK;}*///**************************************************************//起泡排序//**************************************************************StatusBubbleSort(Sqlist&L){inti,j,t;if(L.length==0){printf(要排序的数据为空！);returnERROR;}for(i=1;i=L.length-1;i++){for(j=1;j=L.length-i;