數(shù)據(jù)結構課程設計排序實驗報告

1、數(shù)據(jù)結構課程設計報告專業(yè)班級姓名學號指導教師起止時間課程設計：排序綜合一、任務描述利用隨機函數(shù)產(chǎn)生n個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。（1）至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。（2）統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。要求：根據(jù)以上任務說明，設計程序完成功能。二、問題分析1、功能分析分析設計課題的要求，要求編程實現(xiàn)以下功能：（1）隨機生成N個整數(shù)，存放到線性表中；（2）起泡排序并計算所需時間

2、；（3）簡單選擇排序并計算時間；（4）希爾排序并計算時間；（5）直接插入排序并計算所需時間；（6）時間效率比較。2、數(shù)據(jù)對象分析存儲數(shù)據(jù)的線性表應為順序存儲。三、數(shù)據(jù)結構設計使用順序表實現(xiàn)，有關定義如下：typedefintStatus;設排序碼為整型量定義被排序記錄結構類型排序碼其它數(shù)據(jù)項typedefintKeyType;/typedefintInfoType;typedefstruct/KeyTypekey;/InfoTypeotherinfo;/RedType;typedefstructRedType*r;/存儲帶排序記錄的順序表/r0作哨兵或緩沖區(qū)intlength;/順序表的長度S

3、qList;/定義順序表類型四、功能設計（一）主控菜單設計為實現(xiàn)通各種排序的功能，首先設計一個含有多個菜單項的主控菜單程序，然后再為這些菜單項配上相應的功能。程序運行后，給出5個菜單項的內(nèi)容和輸入提示，如下：1 .起泡排序2 .簡單選擇排序3 .希爾排序4 .直接插入排序0.退出系統(tǒng)(二)程序模塊結構由課題要求可將程序劃分為以下幾個模塊(即實現(xiàn)程序功能所需的函數(shù))主控菜單項選擇函數(shù)menu()創(chuàng)建排序表函數(shù)InitList_Sq()起泡排序函數(shù)Bubble_sort()簡單選擇排序函數(shù)SelectSort()希爾排序函數(shù)ShellSort();對順序表L進行直接插入排序函數(shù)Insertsort

4、()(三)函數(shù)調用關系程序的主要結構(函數(shù)調用關系)如下圖所示。其中main()是主函數(shù)，它負責調用各函數(shù)。進行調用菜單函數(shù)menu(),根據(jù)選擇項04調用相應的函數(shù)。main()函數(shù)使for循環(huán)實現(xiàn)重復選擇。其循環(huán)結構如下：for(;)longstart,end;switch(menu()case 1:printf("*起泡排序*n");start=clock();Bubble_sort(L);end=clock();printf("%dmsn",end-start);fp=fopen("D:起泡排序.txt","w&qu

5、ot;);if(fp=NULL)/打開文件失敗printf("打開文件失敗!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);break;case 2:printf("*簡單選擇排序*n");start=clock();SelectSort(L);end=clock();printf("%dmsn",end-start);fp=fopen("D:直接插入排序.txt","w");if(

6、fp=NULL)/打開文件失敗printf("簡單選擇排序!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);break;case 3:printf("*希爾排序*n");start=clock();ShellSort(L,an,14);end=clock();printf("%dmsn",end-start);fp=fopen("D:希爾排序.txt","w");if(fp=NULL

7、)/打開文件失敗printf("打開文件失敗!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);break;case 4:printf("*直接插入排序*n");start=clock();Insertsort(L);end=clock();printf("%dmsn",end-start);fp=fopen("D:直接插入排序.txt","w");if(fp=NULL)/打開文件失敗

8、printf("打開文件失敗!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);break;case0:printf("t退出！n");return;（四）文件結構1、 、sort.h：單鏈表相關的定義與聲明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指示線性表的基址，len

9、gth指示線性表的當前長度，將隨機生成的數(shù)賦給線性表，并生成相應文件。開始流程圖:代碼描述：StatusInitList_Sq(SqList&L)/構造一個線性表FILE*fp;L.r=(RedType*)malloc(LIST_INIT_SIZE*sizeof(RedType);if(!L.r)exit(OVERFLOW);存儲分配失敗L.length=30001;表長度為30001srand(unsigned)time(NULL);for(inti=1;i<=L.length;i+)L.ri.key=rand()%30001+1;fp=fopen("D:構造一個線性

10、表.txt","w");if(fp=NULL)/打開文件失敗printf("打開文件失敗!n");exit(1);for(i=1;i<=L.length;i+)fprintf(fp,"%d",L.ri);fclose(fp);returnOK;/InitList_Sq算法的時間復雜度分析：O(n)2.Bubble_sort()算法原理：每趟不斷將記錄兩兩比較，若發(fā)現(xiàn)逆序，則交換兩個記錄，使排序碼較小的元素逐漸從后部移向前部(就象水底的氣泡一樣逐漸向上冒)。流程圖：開始結束代碼描述：voidBubble_sort(SqL

11、ist&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.rj+1.key,L.rj.key)flag=1;/有交換，置標志x=L.rj;/L.rj<->L.rj+1L.rj=L.rj+1;L.rj+1=x;if(flag=0)break;/若無交換則可結束冒泡排序算法的時間復雜度分析：O(n2)3、 SelectSort()算法原理：第1趟：從R1Rn中選取最小值,與R1交換;第2趟：從R2Rn中選取最小值,與R2交換;

12、第i趟：從RiRn中選取最小值,與Ri交換;第n-1趟：從Rn1Rn中選取最小值,與Rn1交換.共通過n1趟,得到一個按排序碼從小到大排列的有序序列流程圖：開始結束代碼描述：voidSelectSort(SqList&L)/對順序表進行簡單選擇排序RedTypex;for(inti=1;i<L.length;+i)/在L.ri.L.length中選擇key最小的記錄intk=i;for(intj=i+1;j<=L.length;j+)if(LT(L.rj.key,L.rk.key)k=j;if(k!=i)x=L.ri;L.ri=L.rj;L.rj=x;/SelectSort

13、算法的時間復雜度分析：O(n2)4、 ShellInsert()算法原理：(1)、分組、組內(nèi)直接插入排序；(2)、組數(shù)逐次減?。?3)、組數(shù)=1，結束。代碼描述：voidShellInsert(SqList&L,intdk)/一趟Shell排序，dk為步長inti;for(i=dk+1;i<=L.length;i+)if(LT(L.ri.key,L.ri-dk.key)L.r0=L.ri;intj;for(j=i-dk;(j>0)&&(LT(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;L.rj+dk=L.r0;voidShel

14、lSort(SqList&L,intdlta,intt)/Shell排序，dlta為增量序列，t為增量個數(shù)intk;for(k=0;k<t;k+)ShellInsert(L,dltak);/ShellSort算法的時間復雜度分析：O(n(log2n)2)5、 Insertsort()算法原理：每步將一個待排序的對象，按其排序碼大小，插入到前面已經(jīng)排好序的一組對象的適當位置上，直到對象全部插入為止。在已形成的有序表中順序查找，并在適當位置插入，把原來位置上的元素向后順移。流程圖：代碼描述：voidInsertsort(SqList&L)對順序表L進行直接插入排序for(in

15、ti=2;i<=L.length;i+)if(LT(L.ri.key,L.ri-1.key)需將L.ri插入有序表L.r0=L.ri;/復制為“哨兵”，暫存for(intj=i-1;LT(L.r0.key,L.rj.key);j-)L.rj+1=L.rj;/位置j指示了第一個key<L.ri.key的元素L.rj+1=L.r0;/將暫存在r0中的記錄插入到正確位置/printf("%d",L.ri);算法的時間復雜度分析：O(n2)五、測試數(shù)據(jù)和結果1、測試數(shù)據(jù)隨機產(chǎn)生30000個數(shù)2、測試結果本程序在VC+部境下實現(xiàn)，下面是對以上測試數(shù)據(jù)的運行結果。(1)主菜

16、單顯示如下：Tv：,BnMicrooi：VisualStudcIVy?rojects-5Q1bug5?n.exe'排序序序F廠 ;廠序擇序人統(tǒng)/單爾茬越131左且退請選擇F»%*C：BnMicr0soitVisualStudioMyProjectssortDebugson.exe"清選搔04：起泡排序4b4URS一，序LEIfl序序thktr團吊序擇序人統(tǒng)二匕上一二<，rm.、由羊爾簟1234040s.-出請3序序-i-bh“序探序人統(tǒng)-suf-=泡單爾標上起退=12340請選擇tJQ：»簡單選擇排序1550ns排序序序kLTkt.苗書序擇序人統(tǒng)r-IS爾：！起退12340請選擇0-4：序序tF ktrtiu瘴序人統(tǒng)b - L J UL- T 1屯里了¥sfsfi1 2 3 4 w請選擇0-4 Lf希爾排序*I EH排序序序br tF 序揮序A統(tǒng) suf- 范單<in|返1 2 3 4 0rTC：,BnMicroGQitVisuilStudic'l,VyPrcject&50rtbug53n.exe"lb70ms排序請選擇0-4：WB力Wi口Visualitud