數據結構課程設計報告排序實驗報告

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

2、所需時間；3簡單項選擇擇排序并計算時間；4希爾排序并計算時間；5直接插入排序并計算所需時間；6時間效率比擬。2、數據對象分析 存儲數據的線性表應為順序存儲。三、數據構造設計使用順序表實現(xiàn)，有關定義如下：typedef int Status;typedef int KeyType ; /設排序碼為整型量typedef int InfoType;typedef struct /定義被排序記錄構造類型KeyType key ; /排序碼 InfoType otherinfo; /其它數據項 RedType ; typedef struct RedType * r; /存儲帶排序記錄的順序表 /r0作

3、哨兵或緩沖區(qū) int length ; /順序表的長度 SqList ; /定義順序表類型四、功能設計一主控菜單設計為實現(xiàn)通各種排序的功能，首先設計一個含有多個菜單項的主控菜單程序，然后再為這些菜單項配上相應的功能。程序運行后，給出5個菜單項的容和輸入提示，如下：起泡排序簡單項選擇擇排序希爾排序4. 直接插入排序0. 退出系統(tǒng)二程序模塊構造由課題要求可將程序劃分為以下幾個模塊即實現(xiàn)程序功能所需的函數：主控菜單項選擇函數menu()創(chuàng)立排序表函數 InitList_Sq()起泡排序函數Bubble_sort()簡單項選擇擇排序函數SelectSort()希爾排序函數ShellSort();對順序

4、表L進展直接插入排序函數Insertsort()三函數調用關系程序的主要構造函數調用關系如下列圖所示。其中main()是主函數，它負責調用各函數。進展調用菜單函數menu()，根據選擇項04調用相應的函數。main()函數使. - 可修編for循環(huán)實現(xiàn)重復選擇。其循環(huán)構造如下：for (;) long start,end;switch(menu()case 1:printf(* 起泡排序 *n);start=clock(); Bubble_sort(L);end=clock();printf(%d msn,end-start);fp=fopen(D: 起泡排序 .t*t,w);if(fp=NU

5、LL)/翻開文件失敗printf(翻開文件失敗!n);e*it(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(%d msn,end-start);fp=fopen(D:直接插入排序.t*t,w);if(fp=NULL)/翻開文件失敗printf(簡單項選擇擇排序!n);e*it(1);for(i=1;i=L.length;i+)fprintf(fp,%d ,L.r

6、i);fclose(fp); break;case 3:printf(* 希爾排序 *n);start=clock();ShellSort(L,an,14);end=clock();printf(%d msn,end-start);fp=fopen(D:希爾排序 .t*t,w);if(fp=NULL)/翻開文件失敗printf(翻開文件失敗!n);e*it(1);for(i=1;i=L.length;i+)fprintf(fp,%d ,L.ri);fclose(fp); break;case 4:printf(* 直接插入排序 *n);start=clock(); Insertsort(L);

7、end=clock();printf(%d msn,end-start);fp=fopen(D:直接插入排序.t*t,w);if(fp=NULL)/翻開文件失敗printf(翻開文件失敗!n);e*it(1);for(i=1;i=L.length;i+)fprintf(fp,%d ,L.ri);fclose(fp); break;case 0:printf(t 退 出 ！n);return ;四文件構造1、sort.h：單鏈表相關的定義與聲明2、sort.cpp：單鏈表運算的實現(xiàn)3、menu.h：主菜單函數的聲明4、menu.cpp：主菜單函數的實現(xiàn)5、mn.cpp：主函數 五各函數的算法設計

8、1、InitList_Sq()算法原理：數組指針r指示線性表的基址，length指示線性表的當前長度，將隨機生成的數賦給線性表，并生成相應文件。流程圖： 開場申請存 隨機生成30000個數字生成文件 Fp=NULL 將順序表打印到文件 終止程序 關閉文件 完畢代碼描述：Status InitList_Sq(SqList &L) /構造一個線性表 FILE *fp;L.r=(RedType *) malloc(LIST_INIT_SIZE*sizeof(RedType); if (! L.r) e*it(OVERFLOW); /存儲分配失敗 L.length=30001; /表長度為30001

9、srand(unsigned)time(NULL); for(int i=1;i=L.length;i+) L.ri.key=rand()%30001+1; fp=fopen(D:構造一個線性表.t*t,w);if(fp=NULL)/翻開文件失敗printf(翻開文件失敗!n);e*it(1);for(i=1;i=L.length;i+)fprintf(fp,%d ,L.ri);fclose(fp); return OK; /InitList_Sq 算法的時間復雜度分析：O(n)2.Bubble_sort()算法原理：每趟不斷將記錄兩兩比擬，假設發(fā)現(xiàn)逆序，則交換兩個記錄，使排序碼較小的元素逐漸

10、從后部移向前部就象水底的氣泡一樣逐漸向上冒。流程圖：代碼描述：void Bubble_sort(SqList &L) RedType *; int n; n=L.length; /表長 for (int i=1; i=i; j-) if(LT(L.rj+1.key,L.rj.key) flag=1; /有交換，置標志 *=L.rj; /L.rj L.rj+1 L.rj=L.rj+1; L.rj+1=*; if(flag=0) break; /假設無交換則可完畢冒泡排序 算法的時間復雜度分析：O(n2)3、SelectSort()算法原理：第1趟：從R1Rn中選取最小值,與R1交換;第2趟：從R

11、2Rn中選取最小值,與R2交換;第 i 趟：從RiRn中選取最小值,與Ri交換;第 n -1趟： 從Rn1Rn中選取最小值,與Rn1交換. 共通過n1趟,得到一個按排序碼從小到大排列的有序序列流程圖：代碼描述：void SelectSort(SqList &L) /對順序表進展簡單項選擇擇排序RedType *; for (int i=1; iL.length; +i) /在L.ri.L.length 中選擇key最小的記錄 int k=i; for(int j=i+1;j=L.length ; j+) if ( LT(L.rj.key,L.rk.key) k=j; if(k!=i) *=L.

12、ri; L.ri=L.rj; L.rj=*; /SelectSort算法的時間復雜度分析：O(n2)4、ShellInsert()算法原理：1、 分組、組直接插入排序；2、組數逐次減?。?、組數=1，完畢。代碼描述：void ShellInsert(SqList &L,int dk) /一趟Shell排序，dk為步長int i;for(i=dk+1;i0)&(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; void ShellSort(SqList &L,int dlta,int t) /Shell排序，dlta為

13、增量序列，t為增量個數int k;for(k=0;kt;k+) ShellInsert(L,dltak);/ ShellSort算法的時間復雜度分析：O(n(2n)2)Insertsort()算法原理：每步將一個待排序的對象，按其排序碼大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止。在已形成的有序表中順序查找，并在適當位置插入，把原來位置上的元素向后順移。流程圖：代碼描述：void Insertsort(SqList &L) /對順序表L進展直接插入排序 for(int i=2;i=L.length;i+) if (LT(L.ri.key,L.ri-1.key) /需將L.ri插入有序表 L.r0=L.ri; /復制為哨兵，暫存 for (int j=i-1;LT(L.r0.key,L.rj.key);j-) L.rj+1=L.rj; /位置j指示了第一個keyL.ri.key的元素 L.rj+1=L.r0; /將暫存在r0中的記錄插入到正確位置 /printf(%d ,L.ri); 算法的時間復雜度分析： On2五、測試數據和