《数据结构》课程设计报告.doc

数据结构课程设计报告设计题目：排序综合年 级班 级姓 名学 号指导教师 起止时间 年 学期一实习目的通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。二问题描述（具体任务） 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求： 1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3)如果采用4种或4种以上的方法者，可适当加分。具体任务：分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题：1） 建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环适用系统。2） 分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。3） 通过冒泡排序法来测试每组数据用哪种排序算法最优。三需求分析1）本演示程序对以下7种常用的内部排序算法进行实测比较：直接插入排序、直接选择排序、冒泡排序、快速排序、堆排序、希尔排序、归并排序。2）3）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入选择以何种算法进行排序，测试数据可由用户自行输入或由系统产生随机数。每次测试完毕，将显示该排序的排序时间。4）选择一键排序比较功能，测试完毕，列表显示各种算法的排序时间。并且对结果做出简单分析，给出排序时间最短的两种排序算法。四算法设计思想及流程图开始直接插入排序一键排序比较直接选择排序显示菜单冒泡排序快速排序堆排序显示随机数显示排序后的的数据和时间效率输入序号结束退出随机数显示各个排序法对同一组数据排序所用的时间和其中两种较快的方法12345670希尔排序归并排序89五C语言源代码#include #include #include #include #include #define N 21000/按键不符时提示 void Wrong() printf(n=按键错误!n);getchar();/getchar()函数从STDIN(标准输入)获取并返回下一个字符,如果到达文件尾返回EOF/显示排序结果void Disp(int a) int i;system(cls);/清屏 for(i=0;iN;i+) if(i-1)%10=9) printf(n); printf(%-7d,ai); /插入排序void InsertSort(int a) int i,j,temp; for(i=1;i0&aj-1temp;j-) / 从当前元素的上一个元素开始查找合适的位置 aj=aj-1; aj=temp; /选择排序void SelectSort(int a) int i,j,k; for(i=0;iN-1;i+) k=i; for(j=i+1;jN;j+) /从j 往前的数据都是排好的，所以从j 开始往下找剩下的元素中最下的 if(ajak) k=j; if(k!=i) int temp; temp=ak; ak=ai; ai=temp; /冒泡排序算法void BubbleSort(int a) int i,j,temp;for (i=0;ii;j-) /比较,找出本趟最小关键字的记录 if (ajaj-1) temp=aj; /进行交换,将最小关键字记录前移 aj=aj-1; aj-1=temp; /创建堆void creatheap(int a,int i,int n) int j;int t;t=ai;/保存处理元素 j=2*(i+1)-1;/处理父元素 while(j=n)if(jn)&(ajaj+1)/取较大的孩子节点 j+;if(t=0;i-)/? creatheap(a,i,n-1);/处理后，ai是这个数组后半部分的最大值 for(i=n-1;i=1;i-)t=a0;a0=ai;/把根元素（剩下元素中最大的那个）放到结尾 ，下次只要排剩下的数就可以了 ai=t;creatheap(a,0,i-1);/快速排序void quicksort(int a,int n) int i,j,low,high,temp,top=-1; struct node int low,high; stN; top+; sttop.low=0;sttop.high=n-1; while(top-1) low=sttop.low;high=sttop.high; top-; i=low;j=high; if(lowhigh) temp=alow; while(i!=j) while(itemp)j-; if(ij)ai=aj;i+; while(ij&aitemp)i+; if(ij)aj=ai;j-; ai=temp; top+;sttop.low=low;sttop.high=i-1; top+;sttop.low=i+1;sttop.high=high; /希尔排序int shell=5,3,1;/希尔排序增量序列void shellinsert(int a,int sh,int Max)int i,j,temp;for(i=sh;iMax;i+)/定位每一个元素 if(ai=0&(tempaj);j=j-sh)/比较相距sh 远的两个元素的大小，根据排序 方向决定如何调换 aj+sh=aj; aj+sh=temp;void Shellsort(int a,int shell)int k;for(k=0;k2;k+)shellinsert(a,shellk,N);/归并排序void merge(int aN,int l_start,int l_end,int r_end) int i; int n=l_start; int tempN; int r_start=l_end+1; int m=r_start; for(i=n;i=r_end;i+) if(n=l_end&m=r_end) if(anl_end) tempi=am; m+; else if(mr_end) tempi=an; n+; for(i=l_start;i=r_end;i+) ai=tempi; int msort(int aN,int start,int end) if(start=end) return 0; msort(a,start,(start+end)/2); msort(a,(start+end)/2+1,end); merge(a,start,(start+end)/2,end); /用QueryPerformanceFrequency（）和QueryPerformanceCounte（）函数计时,/精度比用clock（）高，避免了很多时候因排序速度太快而出现运行时间为0的现象。/*a表示参与计算的数组，p 代表用户选择的操作，pflag 代表是否在屏幕上输出排序结果本函数用来计算各个排序算法的时间*/ double Tcount(int a,int p,int pflag)int i,bN; for(i=0;iN;i+) bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart); /选择算法 switch(p) case 1:InsertSort(b);break; case 2:SelectSort(b);break; case 3:BubbleSort(b);break; case 4:quicksort(b,N);break; case 5:heapsort(b,N);break; case 6:Shellsort(b,shell);break; case 7:msort(b,0,N-1);break; default: break; LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; if(pflag=1) /*if(p!=6)Disp(b);getchar();*/getchar(); /控制台输出显示 FILE *fp;switch(p) case 1:printf(n直接插入排序法用的时间为 %f秒；,time);fp=fopen(直接插入排序.txt,w);break; case 2:printf(n直接选择排序法用的时间为 %f秒；,time);fp=fopen(直接选择排序.txt,w);break; case 3:printf(n冒泡排序法用的时间为 %f秒；,time);fp=fopen(冒泡排序.txt,w);break;case 4:printf(n堆排序法用的时间为 %f秒；,time);fp=fopen(堆排序.txt,w);break; case 5:printf(n快速排序法用的时间为 %f秒；,time);fp=fopen(快速排序.txt,w); break; case 6:printf(n希尔排序用法的时间为 %f秒；,time);fp=fopen(希尔排序.txt,w);break; case 7:printf(n归并排序用法的时间为 %f秒；,time);fp=fopen(归并排序.txt,w);break; default: break; for(i=0;iN;i+) fprintf(fp,%d ,bi); fclose(fp); return(time);void BubleSort(double a) /时间数组的冒泡排序 int i,j; double temp; for(i=1;i=i;j-) if(aj+1aj) temp=aj+1; aj+1=aj; aj=temp; /菜单显示 void menu()printf( n); printf( n); printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf(n=请在上述序号中选择一个并输入:);int main() int i,p,aN;/随机种子,设置rand()随机序列种子。对于给定的种子seed, rand()会反复产生特定的随机序列。 srand(int)time(NULL); for(i=0;i谢谢使用!n); getchar(); break; double TIMES7,TIMES17;/时间数组 switch(p) case 1:Tcount(a,p,1);printf(n请按任意键继续.);getchar();break; case 2:Tcount(a,p,1);printf(n请按任意键继续.);getchar();break; case 3:Tcount(a,p,1);printf(n请按任意键继续.);getchar();break; case 4:Tcount(a,p,1);printf(n请按任意键继续.);getchar();break; case 5:Tcount(a,p,1);printf(n请按任意键继续.);getchar();break; case 6:Tcount(a,p,1);printf(n请按任意键继续.);getchar();break; case 7:Tcount(a,p,1);printf(n请按任意键继续.);getchar();break; case 8:system(cls);getchar(); int u; for(u=1;u8;u+) p=u; TIMES1u=TIMESu=Tcount(a,p,0); BubleSort(TIMES); /测试用 （输出排序过的时间数组，验证排序正确性） /* printf(n); for(u=1;u8;u+) printf(%fn,TIMESu); */ /* / printf(nn); printf(排序这组数据两种较快的排序法分别是：n);/将最快的排序算法输出 if(TIMES1=TIMES11) printf(直接插入排序: %f秒!n,TIMES1); if(TIMES1=TIMES12) printf(直接选择排序: %f秒!n,TIMES1); if(TIMES1=TIMES13) printf(冒泡排序: %f秒!n,TIMES1); if(TIMES1=TIMES14) printf(堆排序: %f秒!n,TIMES1); if(TIMES1=TIMES15) printf(快速排序: %f秒!n,TIMES1); if(TIMES1=TIMES16) printf(希尔排序: %f秒!n,TIMES1); if(TIMES1=TIMES17) printf(归并排序: %f秒!n,TIMES1);/若排序较快的两种时间不并列，输出第二快的排序算法 if(TIME