湖州师范学院数据结构DS大作业

求真学院数据结构课程设计大作业20142832班题目：排序效率的比较专业：计算机科学与技术学生姓名：学号指导教师邵斌完成日期：湖州师院求真学院信息工程系I目录一、实验内容概述...............................................................................................................................1二、实验目的概述...............................................................................................................................1三、解题思路的描述...........................................................................................................................1四、源程序清单...................................................................................................................................1五、程序调试及测试结果...................................................................................................................8六、结论...............................................................................................................................................9七、参考文献.....................................................................................................................................10此处写大作业题目（宋体三号，居中）【内容摘要】200至300字左右，楷体BG2312五号【关键字】XXXX，XXXXX，XXXXX，XXXXX(3到5个)数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素和集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，处理各种问题。该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。该程序植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过对耗时的比较，为用户挑选出两种最优化的排序方法。关键字：排序逻辑运算数据结构时间复杂度【Abstract】中文摘要的翻译，五号，TimesNewRoman【Keywords】XXXXX，XXXXX，XXXXX，XXXXXDatastructureisthewayofcomputerstorageandorganizationdata.Adatastructureisadataelementandasetofdataelementsthathaveoneormorespecificrelationshipsbetweeneachother.Typically,carefullyselecteddatastructurescanbebroughttoahigherrunningorstorageefficiency,processingavarietyofproblems.TheprogramiswritteninClanguage,itfullyreflectstheconceptofdatastructureandalgorithmcharm.Theprogramisimplantedinavarietyofsortingmethods,thesesortingalgorithmshavethecharacteristicsofeachalgorithm,theuseofavarietyofalgorithmstoachievethesameeffect,istheso-calledallroadsleadtoRome.And,theprogramalsocollectstherunningtimeofeachalgorithm,throughthetimeofthecomparison,fortheusertopickouttwokindsofoptimizationofthesortingmethod.Keywords:sortinglogicoperationdatastructuretimecomplexity1一、实验内容概述对于直接插入排序、选择排序、冒泡排序、Shell排序、快速排序和堆排序等几种常见的排序算法进行练习，并且比较各算法在不同长度数据下的优劣。要求：（１）被排序的对象由计算机随机生成，长度分别取２０，１００，５００三种。（２）程序中要有对各种排序算法的比较，具体为比较次数和移动次数的统计。（３）对课设的结果做比较分析二、实验目的概述1.巩固和加深学生对数据结构算法的理解，提高综合运用所学课程知识的能力；2.通过各个排序算法的实现，练习包括文件的读写、动态内存的申请、函数的应用、指针的应用等多种最基本的C语言操作；3.锻炼学生的动手能力与培养其独立思考的能力。三、解题思路的描述这是一个算法性能评价的程序，重点在于算法的性能评价上。实现排序功能可以有多种方法，判断一个算法性能好坏的标准主要有时间复杂度和空间复杂度。在当今系统资源相对充足的计算机系统中，时间复杂度便成为最主要的评价标准。对于每一个排序算法，都应当有两个返回值：比较次数和移动次数。这里采用指针传递地址的方式，通过修改形参的地址从而可以改变实参的值。每个排序算法中除了含被排序对象指针外，还有两个整型变量指针，用于传递算法执行过程中的比较次数和移动次数。取定一种排序对象的长度，由计算机产生一定量的伪随机数后，主函数调用各个排序子函数，但由于排序对象也是指向一维数组的指针，在调用一次一种排序算法后，通过形参对指针的改变，被排序对象已经是有序的了。当再次调用其他函数时有可能使比较和移动次数达到最大或最小，就失去了比较的意义。因此，本程序中采用了子函数另开辟空间，参数只起到一个复制值的作用，在每个子函数结束前用delete()来释放申请排序对象的指针，避免程序出现内存耗尽的情况。四、源程序清单主要包括：#includestdio.h#includestdlib.h#includetime.hinta[501],b[501];intlen;//数组长度voidnumber()2{srand(time(0));//srand函数是初始化随机数的种子inti,t;printf(随机数长度：\n);printf(1.长度为20\n);printf(2.长度为100\n);printf(3.长度为500\n);printf(输入序号选择长度:);scanf(%d,&t);switch(t){case1:n=20;for(i=1;i=n;i++){a[i]=rand()%1000+1;//1-1000的随机数}break;case2:n=100;for(i=1;i=len;i++){a[i]=rand()%1000+1;}break;case3:n=500;for(i=1;i=len;i++){a[i]=rand()%1000+1;}break;}for(i=1;i=len;i++)b[i]=a[i];printf(随机生成的%d个数如下：\n,len);for(i=1;i=len;i++){printf(%d,a[i]);}printf(\n);}typedefstruct{intkey;//关键字}RecordNode;//排序结点类型typedefstruct{RecordNode*record;intn;//排序对象的大小3}ElemType;//排序对象的类型直接排序voidInsertSort(ElemTypeA[],intn){inti,j;ElemTypex;for(i=1;in;i++){//进行n-1次插入x=A[i];//准备插入第i个元素for(j=i-1;j=0;j--){//从第i-1个开始往前找插入点if(x.stnA[j].stn)A[j+1]=A[j];elsebreak;}A[j+1]=x;//插入}for(i=1;i=n;i++){printf(%d,a[i]);}printf(\n);printf(\n);printf(比较次数：%d次\n,i);printf(移动次数：%d次\n,j);}直接选择排序voidSelectSort(ElemTypeA[],intn){inti,j,k;ElemTypex;for(i=0;i=n-2;i++){//每一趟选择最小元素并与A[i]交换k=i;for(j=i+1;j=n-1;j++)//查找最小元素的下标if(A[j].stnA[k].stn)k=j;if(k!=i){//交换x=A[i];A[i]=A[k];A[k]=x;}}4for(i=1;i=n;i++){printf(%d,a[i]);}printf(\n);printf(\n);printf(比较次数：%d次\n,i);printf(移动次数：%d次\n,j);}}冒泡排序voidBubbleSort(ElemTypeA[],intn){inti,j,flag;//flag为交换标记ElemTypex;for(i=1;i=n-1;i++){//最多n-1趟排序flag=0;//假设本次没有交换for(j=n-1;j=i;j--)//第i趟if(A[j].stnA[j-1].stn){flag=1;//出现交换x=A[j];A[j]=A[j-1];A[j-1]=x;}if(flag==0)return;}for(i=1;i=n;i++){printf(%d,a[i]);}printf(\n);printf(\n);printf(比较次数：%d次\n,i);printf(移动次数：%d次\n,j);}}Shell排序voidShellSort(ElemTypeA[],intn,intdk)5{inti,j,temp;ElemTypex;for(i=dk;in;i++)//分别向每组的有序区域插入{temp=array[i];for(j=i-dk;(j=i%dk)&&array[j]temp;j-=dk)//比较与记录后移同时进行A[j+dk]=A[j];if(j!=i-dk)A[j+dk]=temp;//插入}for(i=1;i=n;i++){printf(%d,a[i]);}printf(\n);printf(\n);printf(比较次数：%d次\n,i);printf(移动次数：%d次\n,j);}}快速排序voidQuickSort(ElemTypeA[],ints,intt){//递归算法，对区间A[s]～A[t]进行快速排序inti=s+1,j=t;ElemTypetemp,x=A[s];//第一个为基准元素while(i=j){while(i=j&&A[i].stn=x.stn)i++;//从左到右while(i=j&&A[j].stn=x.stn)j--;//从右