上傳人：時***

認證信息

認證類型：個人認證

認證主體：韓**（實名認證）

IP屬地：江蘇

IP屬地：江蘇 上傳時間：2023-10-26 格式：DOC 頁數(shù)：17 大?。?54.50KB 積分：20 舉報 版權(quán)申訴

《數(shù)據(jù)構(gòu)造》課程設計報告專業(yè)計算機科學與技術(shù)班級姓名學號指導教師起止時間.12~.1課程設計：排序綜合任務描述排序綜合任務：運用隨機函數(shù)產(chǎn)生n個隨機整數(shù)（0以上），對這些數(shù)進行多個辦法進行排序。規(guī)定：（1）最少采用三種辦法實現(xiàn)上述問題求解（提示，可采用的辦法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的成果保存在不同的文獻中。（2）統(tǒng)計每一種排序辦法的性能（以上機運行程序所耗費的時間為準進行對比），找出其中兩種較快的辦法。二、問題分析1、功效分析分析設計課題的規(guī)定，規(guī)定編程實現(xiàn)下列功效：（1）排序表的建立—即創(chuàng)立次序表；（2）次序表的排序—即直接插入排序、希爾排序、起泡排序、快速排序、簡樸選擇排序操作；（3）統(tǒng)計每一種排序辦法的性能—即測試上機運行程序所耗費的時間；2、數(shù)據(jù)對象分析數(shù)據(jù)信息：隨機整數(shù)數(shù)據(jù)數(shù)量能夠預先擬定（0以上）數(shù)據(jù)構(gòu)造設計使用次序表實現(xiàn)，有關(guān)定義以下：typedefintStatus;typedefintKeyType;//設排序碼為整型量typedefintInfoType;typedefstruct{//定義被排序統(tǒng)計構(gòu)造類型 KeyTypekey;//排序碼I nfoTypeotherinfo;//其它數(shù)據(jù)項}RedType;typedefstruct{ RedType*r;//存儲帶排序統(tǒng)計的次序表//r[0]作哨兵或緩沖區(qū) intlength;//次序表的長度}SqList;//定義次序表類型四、功效設計（一）主控菜單設計為實現(xiàn)通多個排序的功效，首先設計一種含有多個菜單項的主控菜單程序，然后再為這些菜單項配上對應的功效。程序運行后，給出6個菜單項的內(nèi)容和輸入提示，以下：1.直接插入排序2.希爾排序3.起泡排序4.快速排序5.簡樸選擇排序0.退出系統(tǒng)（二）程序模塊構(gòu)造由課題規(guī)定可將程序劃分為下列幾個模塊（即實現(xiàn)程序功效所需的函數(shù)）：主控菜單選函數(shù)menu()創(chuàng)立排序表函數(shù)InitList_Sq()對次序表L進行直接插入排序函數(shù)Insertsort()希爾排序函數(shù)ShellSort();起泡排序函數(shù)Bubble_sort()快速排序函數(shù)QSort()簡樸選擇排序函數(shù)SelectSort()（三）函數(shù)調(diào)用關(guān)系程序的重要構(gòu)造（函數(shù)調(diào)用關(guān)系）以下圖所示。Menu() InitList_Sq(L) Main()Insertsort(L) ShellSort() Bubble_sort() QSort() SelectSort()其中main()是主函數(shù)，它進行菜單驅(qū)動，根據(jù)選擇項0~5調(diào)用對應的函數(shù)。main()函數(shù)使用for循環(huán)實現(xiàn)重復選擇。其循環(huán)構(gòu)造以下：for(;;) { longstart,end; switch(menu()) { case1: printf("*直接插入排序*\n"); start=clock(); Insertsort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:直接插入排序.txt","w"); if(fp==NULL)//打開文獻失敗 { printf("打開文獻失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case2: printf("*希爾排序*\n"); start=clock(); ShellSort(L,an,14); end=clock(); printf("%dms\n",end-start); fp=fopen("D:希爾排序.txt","w"); if(fp==NULL)//打開文獻失敗 { printf("打開文獻失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case3: printf("*起泡排序*\n"); start=clock(); Bubble_sort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:起泡排序.txt","w"); if(fp==NULL)//打開文獻失敗 { printf("打開文獻失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case4: printf("*快速排序*\n"); start=clock(); QSort(L,0,L.length); end=clock(); printf("%dms\n",end-start); fp=fopen("D:快速排序.txt","w"); if(fp==NULL)//打開文獻失敗 { printf("打開文獻失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case5: printf("*簡樸選擇排序*\n"); start=clock(); SelectSort(L); end=clock(); printf("%dms\n",end-start); fp=fopen("D:簡樸選擇排序.txt","w"); if(fp==NULL)//打開文獻失敗 { printf("打開文獻失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); break; case0: printf("\t退出！\n"); return; } }（四）文獻構(gòu)造1、sort.h：次序表有關(guān)的定義與函數(shù)聲明2、sort.cpp：次序表排序運算的實現(xiàn)3、menu.h：主菜單函數(shù)的聲明4、menu.cpp：主菜單函數(shù)的實現(xiàn)5、mn.cpp：主函數(shù)（五）各函數(shù)的算法設計1、InitList_Sq()算法原理：數(shù)組指針r批示線性表的基址，length批示線性表的現(xiàn)在長度，將隨機生成的數(shù)賦給線性表，并生成對應文獻。流程圖： 開始申請內(nèi)存隨機生成30000個數(shù)字生成文獻 Fp=NULL 將次序表打印到文獻內(nèi)終止程序關(guān)閉文獻結(jié)束 代碼描述：StatusInitList_Sq(SqList&L){//構(gòu)造一種線性表 FILE*fp; L.r=(RedType*)malloc(LIST_INIT_SIZE*sizeof(RedType)); if(!L.r)exit(OVERFLOW);//存儲分派失敗 L.length=30001;//表長度為30001 srand((unsigned)time(NULL)); for(inti=1;i<=L.length;i++) L.r[i].key=rand()%30001+1; fp=fopen("D:構(gòu)造一種線性表.txt","w"); if(fp==NULL)//打開文獻失敗 { printf("打開文獻失敗!\n"); exit(1); } for(i=1;i<=L.length;i++) fprintf(fp,"%d",L.r[i]); fclose(fp); returnOK;}//InitList_Sq算法的時間復雜度分析：O(n)Insertsort()算法原理：每步將一種待排序的對象，按其排序碼大小，插入到前面已經(jīng)排好序的一組對象的適宜位置上，直到對象全部插入為止。在已形成的有序表中次序查找，并在適宜位置插入，把原來位置上的元素向后順移。流程圖： 開始i=2i<L.length否 是L.r[i].key<L.r[i-1].key否是L.r[0]=L.r[i]j=i-1L.r[0].key<L.r[j].key否是L.[j+1]=L.r[j]j--L.r[j+1]=L.r[0]i++結(jié)束代碼描述：voidInsertsort(SqList&L)//對次序表L進行直接插入排序{for(inti=2;i<=L.length;i++)if(LT(L.r[i].key,L.r[i-1].key))//需將L.r[i]插入有序表{L.r[0]=L.r[i];//復制為“哨兵”，暫存for(intj=i-1;LT(L.r[0].key,L.r[j].key);j--)L.r[j+1]=L.r[j];//位置j批示了第一種key≤L.r[i].key的元素L.r[j+1]=L.r[0];//將暫存在r[0]中的統(tǒng)計插入到對的位置}}算法的時間復雜度分析：O（n2）3、ShellInsert()算法原理：1、分組、組內(nèi)直接插入排序；2、組數(shù)逐次減?。?、組數(shù)=1，結(jié)束。流程圖： 開始i=dk+1i<L.length 否是L.r[i].key<L.r[i-dk].key 否是L.r[0]=L.r[i]j=i-dk(j>0)&&(LT(L.r[0].key,L.r[j].key) 否 是L.r[j+dk]=L.r[j]j-=dkL.r[j+dk]=L.r[0]i++結(jié)束代碼描述：voidShellInsert(SqList&L,intdk){//一趟Shell排序，dk為步長 inti; for(i=dk+1;i<=L.length;i++) { if(LT(L.r[i].key,L.r[i-dk].key)){ L.r[0]=L.r[i]; intj; for(j=i-dk;(j>0)&&(LT(L.r[0].key,L.r[j].key));j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0];}}}ShellSort()流程圖： 開始k=0k<tShellInsert(L,dlta[k])k++結(jié)束代碼描述：voidShellSort(SqList&L,intdlta[],intt){//Shell排序，dlta[]為增量序列，t為增量個數(shù) intk; for(k=0;k<t;k++)ShellInsert(L,dlta[k]);}//ShellSort算法的時間復雜度分析：O(n(㏒2n)2)Bubble_sort()算法原理：每趟不停將統(tǒng)計兩兩比較，若發(fā)現(xiàn)逆序，則交換兩個統(tǒng)計，使排序碼較小的元素逐步從后部移向前部（就象水底的氣泡同樣逐步向上冒）。流程圖： 開始n=L.lengthi=1i<nflag=0j=n-1j<=iL.r[j+1].key<L.r[j].key)flag=1L.r[j]←→L.r[j+1]j--flag=0i++結(jié)束代碼描述：voidBubble_sort(SqList&L){RedTypex; intn;n=L.length;//表長for(inti=1;i<n;i++){intflag=0;//進入循環(huán)，清標志for(intj=n-1;j>=i;j--)if(LT(L.r[j+1].key,L.r[j].key)){ flag=1;//有交換，置標志x=L.r[j];//L.r[j]←→L.r[j+1]L.r[j]=L.r[j+1];L.r[j+1]=x;}if(flag==0)break;//若無交換則可結(jié)束冒泡排序}}算法的時間復雜度分析：O(n2)6、Partition()算法原理：從n個待排統(tǒng)計中任取一種統(tǒng)計Ri作原則，調(diào)節(jié)序列中各個統(tǒng)計的位置，使得：排在ri前的統(tǒng)計排序碼<=ri.key排在ri后的排序碼，該過程為一趟快速排序。這樣就擬定了Ri在序列中的最后位置，同時將序列分成兩個子序列。流程圖： 開始L.r[0]=L.r[low]Pivotkey=L.r[low].keyLow<high否是low<high&&L.r[high].key>=pivotkey否是--highL.r[low]←→L.r[high]low<high&&L.r[low].key<=pivotkey否是++lowL.r[low]←→L.r[high]L.r[low]=L.r[0]returnlow結(jié)束代碼描述：intPartition(SqList&L,intlow,inthigh){/*交換子表r[low…h(huán)igh]的統(tǒng)計，使樞軸統(tǒng)計到位，并返回其位置。返回時，在樞軸之前的統(tǒng)計排序碼均不不不大于其排序碼，之后的統(tǒng)計排序碼均不不大于其排序碼。*/L.r[0]=L.r[low];//以子表的首統(tǒng)計作為樞軸，放入r[0]單 intpivotkey;pivotkey=L.r[low].key;//取樞軸的排序碼存入pivotkey變量while(low<high){ //從表的兩端交替地向中間掃描 RedTypex; RedTypet; while(low<high&&L.r[high].key>=pivotkey)--high; x=L.r[low]; L.r[low]=L.r[high]; L.r[high]=x;//將比樞軸排序碼小的統(tǒng)計交換到低端 while(low<high&&L.r[low].key<=pivotkey)++low; t=L.r[high]; L.r[high]=L.r[low]; L.r[low]=t;//將比樞軸排序碼大的統(tǒng)計交換到高端 }L.r[low]=L.r[0];//樞軸統(tǒng)計到位returnlow;//返回樞軸統(tǒng)計所在位置}//Partition7、QSort()算法原理：1、對Partition()擬定的兩個子序列分別進行快速排序，則又可擬定2個統(tǒng)計在序列中的最后位置，同時將序列分成4個子序列。2、重復直至每個序列的長度均為1時，全部統(tǒng)計排序完畢。流程圖： 開始Low<hightpivotloc=Partition(L,low,high) QSort(L,low,pivotloc-1)QSort(L,pivotloc+1,high)結(jié)束代碼描述：voidQSort(SqList&L,intlow,inthigh){//對次序表L中的子序列r[low…h(huán)igh]作快速排序if(low<high){//長度>1 intpivotloc;pivotloc=Partition(L,low,high);//一趟快排，將r[]一分為二QSort(L,low,pivotloc-1); //在左子區(qū)間進行遞歸快排，直到長度為1QSort(L,pivotloc+1,high);//在右子區(qū)間進行遞歸快排，直到長度為1}}算法的時間復雜度分析：O(nlogn)8、SelectSort()算法原理：第1趟：從R[1]~R[n]中選用最小值,與R[1]交換;第2趟：從R[2]~R[n]中選用最小值,與R[2]交換; ………第i趟：從