当前位置:首页 > 机械/制造/汽车 > 汽车理论 > 《数据结构》课程设计
《数据结构》课程设计报告题目:排序效率的比较学生姓名:XXX学号:XXXXX专业班级:XXXXXXX指导老师:XXX设计日期:20XX年X月X日目录:一、问题描述二、基本要求三、概要设计四、详细设计五、运行与测试六、总结与心得一、问题描述对于直接排序、直接选择排序、冒泡排序、快速排序等五种方法编制程序上机运行。二、基本要求(1)被排序的对象由计算机随机生成,长度分别取20、100、500三种;(2)算法中增加比较次数和移动次数的统计功能;(3)对上机运行的结果做比较分析,所得出结论是什么。三、概要设计1、数据结构的设计本程序中,考虑的内容就是待排序对象,排序的依据是关键字之间的大小比较,故在每个节点的类型定义中,至少得包含着关键字key一项。被排序对象是由一个个节点构成,一个排序对象包含一系列指向一串节点的指针,排序对象的长度。2、算法的设计(1)插入排序的伪代码1)forj←2tolength[A]2)dokey←A[j]3)//InsertA[j]intothesortedsequenceA[1..j-1]4)i←j–15)whilei0andA[i]key6)doA[i+1]←A[i]7)i←i–18)A[i+1]←key(2)选择排序1)forj←1toLength[A]2)key←A[j]3)foritoLenth[A]4)ifkeyA[i]5)key←A[i]6)k←i7)A[k]←A[j]A[j]←key(3)快速排序//一次快速排序intPartition(SqList&L,intlow,inthigh){//交换顺序表L.r[low..high]的记录,使枢轴记录到位,并返回其所在位置//此时,在它之前(后)的记录均不大(小)于它。L.r[0]=L.r[low];pivotkey=L.r[low].key;//用子表的第一个记录做枢轴记录while(lowhigh){//从表的两端交替的向中间扫描while(lowhith&&L.r[high].key=pivotkey)--high;L.r[low]=L.r[high];//将此枢轴记录小的记录交换到低端while(lowhigh&&L.r[low].key=pivotkey)++low;L.r[high]=L.r[low];//将比枢轴记录大的记录交换到高端}L.r[low]=L.r[0];returnlow;//返回枢轴所在位置}//递归形式的快速排序voidQSort(SqList&L,intlow,inthigh){//对顺序表L的子序列L.r[lowhigh]做快速排序if(lowhigh){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}//}(4)堆排序MAX-HEAPIFY(A,i)1l←LEFT(i)2r←RIGHT(i)3ifl≤heap-size[A]andA[l]A[i]4thenlargest←l5elselargest←i6ifr≤heap-size[A]andA[r]A[largest]7thenlargest←r8iflargest≠i9thenexchangeA[i]↔A[largest]10MAX-HEAPIFY(A,largest)BUILD-MAX-HEAP(A)1heap-size[A]←length[A]2fori←floor(length[A]/2)downto13doMAX-HEAPIFY(A,i)HEAPSORT(A)1BUILD-MAX-HEAP(A)2fori←length[A]downto23doexchangeA[1]↔A[i]4heap-size[A]←heap-size[A]-15MAX-HEAPIFY(A,1)(5)冒泡排序读入长度为n的数组a将i从2到n枚举将j从n到i枚举a比较a[j]和a[j-1]的大小若a[j]小于a[j-1]则交换a[j-1]和a[j]四、详细设计#includeiostream#includetime.h#includestdlib.h#includewindows.h#includemath.husingnamespacestd;//直接插入排序voidInsertSort(intA[],intn){inti,j;intx;for(i=1;in;i++){//进行n-1次插入x=A[i];//准备插入第i个元素for(j=i-1;j=0;j--){//从第i-1个开始往前找插入点if(xA[j])A[j+1]=A[j];elsebreak;}A[j+1]=x;//插入}intcount=0;printf(直接插入排序结果:\n);for(intk=0;kn;k++){printf(%d\t,A[k]);count++;if(count%10==0)printf(\n);}}//冒泡排序voidBubbleSort(intA[],intn){inti,j,flag;//flag为交换标记intx;for(i=1;i=n-1;i++){//最多n-1趟排序flag=0;//假设本次没有交换for(j=n-1;j=i;j--)//第i趟if(A[j]A[j-1]){flag=1;//出现交换x=A[j];A[j]=A[j-1];A[j-1]=x;}if(flag==0)break;}}//直接选择排序voidSelectSort(intA[],intn){inti,j,k;intx;for(i=0;i=n-2;i++){//每一趟选择最小元素并与A[i]交换k=i;for(j=i+1;j=n-1;j++)//查找最小元素的下标if(A[j]A[k])k=j;if(k!=i){//交换x=A[i];A[i]=A[k];A[k]=x;}}}//快速排序voidQuickSort(intA[],ints,intt){//递归算法,对区间A[s]~A[t]进行快速排序inti=s+1,j=t;inttemp,x=A[s];//第一个为基准元素while(i=j){while(i=j&&A[i]=x)i++;//从左到右while(i=j&&A[j]=x)j--;//从右到左if(ij){temp=A[i];A[i]=A[j];A[j]=temp;i++;j--;}}if(s!=j){//交换基准元素A[s]=A[j];A[j]=x;}if(sj-1)QuickSort(A,s,j-1);//处理左区间if(j+1t)QuickSort(A,j+1,t);//处理右区间}//堆排序voidSift(intA[],intn,inti);voidCreatHeap(intA[],intn){inti;for(i=(n-2)/2;i=0;i--)Sift(A,n,i);//调整A[i..n-1]使之为一个堆}voidSift(intA[],intn,inti){//调整A[i..n-1]成为一个堆(它的左右子树已是一个堆)intx=A[i];intj=2*i+1;//j为i的左孩子while(j=n-1){//i有左子树if(j+1n&&A[j]A[j+1])j++;//使j指向左右孩子中排序码大的孩子if(xA[j]){//将A[j]上移,以便向下筛A[i]=A[j];i=j;j=2*i+1;}elsebreak;}A[i]=x;}voidHeapSort(intA[],intn){//A为待排序表,n为表的长度inti;intx;CreatHeap(A,n);//把A建成一个堆for(i=n-1;i=1;i--){x=A[0];//第个元素与第i个元素交换A[0]=A[i];A[i]=x;Sift(A,i,0);//调整A[0..i-1]使之为一个堆}}//主函数intmain(){LARGE_INTEGERBegainTime;LARGE_INTEGEREndTime;LARGE_INTEGERFrequency;QueryPerformanceFrequency(&Frequency);QueryPerformanceCounter(&BegainTime);inti,*array,choice,num;while(1){//输出菜单printf(请选择排序类型:1.直接插入排序2.冒泡排序3.选择排序4.快速排序5.堆排序0.退出\n);//选择编号cinchoice;//退出程序if(choice1||choice5)break;//输入排序数个数printf(请输入排序个数:);cinnum;//检查输入while(1){if(num1){cout请输入大于0个排序数:;cinnum;continue;}if(num0)break;}array=newint[num];//产生随机数种子srand((int)time(0));for(i=0;inum;i++){//循环生成随机数array[i]=rand();//1+(int)(num*rand()/(RAND_MAX+1.0));}switch(choice){//直接插入排序时间case1:{QueryPerformanceFrequency(&Frequency);QueryPerformanceCounter(&BegainTime);//DWORDstart_time=GetTickCount();InsertSort(array,num);//DWORDend_time=GetTickCount();QueryPerformanceCounter(&EndTime);cout直接插入排序需要时间:(double)(EndTime.QuadPart-BegainTime.QuadPart)/Frequency.QuadPart*1000msendl;//(end_time-start_time)ms!endl;//输出运行时间intcount=0;printf(直接插入排序结果:\n);for(intk=0;knum;k++){printf(%d\t,array[k]);count++;if(count%10==0)printf(\n);}break;}//冒泡排序时间case2:{QueryPerformanceFrequency(&Frequency);QueryPerformanceCounter(&BegainTime);//DWORDstart_time=GetTickCount();BubbleSort(array,num);//DWORDend_time=GetTickCount();QueryPerformanceCounter(&EndTime);cout冒泡排序需要时间:(double)(EndTime.QuadPart-BegainTime.QuadPart)/Frequency.QuadPart*1000msendl;//(end_time-start_time)ms!endl;//输出运行时间intcount=0;printf(冒泡排序结果:\n);for(intk=0;knum;k++){printf(%d\t,array[k]);count++;if(count%10==0)printf(\n);}break;}//选择排序时间case3:{QueryPerformanceFrequency(&Frequency);QueryPerformanceCounter(&BegainTime);//DWORDstart_time=GetTickCount();SelectSort(array,num);//DWORDend_time=GetTickCount();Query
本文标题:《数据结构》课程设计
链接地址:https://www.777doc.com/doc-4474128 .html