1、數據結構課程設計實習報告（排序操作）學 院：計算機學院 專 業： 班 級： 學 號： 姓 名： 指導教師： 完成日期： 目錄一、 需求分析 11. 運行環境 12. 程序所實現的功能 13. 程序的輸入 14. 程序的輸出 1二、 設計說明 11. 算法設計的思想 12. 主要的數據結構設計說明 23. 程序的主要流程圖 34. 程序的主要模塊 35. 程序的主要函數及其偽代碼說明 4三、 上機結果及體會 71. 實際完成的情況說明 72. 程序算法的性能分析 73. 程序運行時的初值和運行結果 84. 程序中可以改進的地方說明 115. 收獲及體會 116. 源程序及注釋 12四、 參考文獻

2、 19一、需求分析1. 運行環境：軟件環境：Microsoft Visual C+ 6.0。2. 程序所實現的功能 本程序實現了直接插入排序、折半插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、歸并排序等多種排序算法的功能，并且對每一種而言，都能輸出每一趟的排序結果。3. 程序的輸入： 本程序的輸入的格式為：元素+空格+元素，并按回車鍵結束輸入。如（49_38_65_97_76_13_27_49回車鍵），且本程序僅適用于整形數據。4. 程序的輸出： 本程序能輸出每一趟的排序結果，且輸出的格式和輸入的格式基本一致。 二、設計說明1. 算法設計的思想：(1)直接插入排序的算法設計思想為：將一個

3、記錄插入到已排好的有序表中，從而得到一個新的、記錄數增1的有序表。一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列R1.i-1中插入一個記錄Ri后，變成含有i個記錄的有序的子序列R1.i；并且，和順序表類似，為了在查找插入位置的過程中避免數組下標出界，在R0出設置監視哨。(2)折半插入排序的算法思想為：在一個有序表中進行折半查找和插入。第1頁(3)冒泡排序的算法思想為：首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序（即L->R1.key>L->R2.key），則將兩個記錄交換之，然后比較第二個記錄的關鍵字和第三個記錄的關鍵字。依次類推，直

4、至第n-1個記錄和第n個記錄的關鍵字進行過比較為止。一般地，第i趟冒泡排序是從L->R1到L->Rn-i+1依次比較相鄰事物兩個記錄的關鍵字，并在“逆序”是交換記錄，其結果是這n-i+1個記錄中關鍵字最大的記錄被交換到第n-i+1的位置上。(4)簡單選擇排序的算法設計思想為：通過n-i次關鍵字之間的比較，從n-i+1個記錄中選擇出關鍵字最小的記錄，并和第i個記錄交換之。(5)快速排序的算法設計思想為：通過每一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。(6)堆排序的算法設計思想為：將初

5、始序列建成一個堆，若在輸出堆頂的最小值后，使得剩余的n-1個元素的序列重又建成一個堆，則得到n個元素中的次小值，如此反復執行，便能得到一個有序的序列。(7)歸并排序的算法設計思想為：假設初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n2個長度為2或1的有序子序列；再兩兩歸并，如此重復，直至得到一個長度為n的有序序列為止。2. 主要的數據結構設計說明：(1) 本程序的儲存結構主要采用順序表儲存結構：typedef structint key; /關鍵字RedType; /記錄類型typedef struct RedType RMAXSIZE+1;/R0閑

6、置為哨兵int length; /順序表長度*SqList,sq; /順序表類型(2)本程序的輸入與輸出均采用了“do-while”語句，而主函數的功能選擇采用了“case”語句。如下是輸入函數的一段代碼： do i+;scanf("%d%c",&L->Ri.key,&ch); 第2頁while(ch!='n'); 3. 程序的主要流程圖：菜單退出堆 排 序直接插入排序折半插入排序冒 泡 排 序歸 并 排 序快 速 排 序簡單選擇排序輸入待排序列按任意鍵返回輸出每一趟結果4. 程序的主要模塊： (1)菜單模塊由Menu()函數實現。第3

7、頁 (2)各排序功能：直接插入排序模塊由InsertSort(SqList L)函數實現，折半插入排序模塊由BInsertSort(SqList L)函數實現，冒泡排序模塊由BubbleSort(SqList L)函數實現，簡單選擇排序模塊由SelectSort(SqList L)函數和SelectMinKey(SqList L,int i)函數實現，快速排序模塊由QSort(SqList L,int low ,int high)函數、QuickSort(SqList L)函數和Partition(SqList L,int low ,int high)函數實現，堆排序模塊由HeapAdjust

8、(SqList L,int s,int m)函數和HeapSort(SqList L)函數實現，歸并排序模塊由MergeSort(SqList L, int length)函數實現。 (3)輸入與輸出模塊：輸入模塊由CreatSqList(SqList L)函數實現，輸出模塊由PrintSort(SqList L)函數和FiPrintSort(SqList L)函數實現。5. 程序的主要函數及其偽代碼說明： (1)直接插入排序： void InsertSort(SqList L) /直接插入排序 int i,j; for(i=2;i<=L->length;+i)if(L->R

9、i.key<L->Ri-1.key) /需將L->Ri插入有序子表L->R0=L->Ri; /復制為哨兵L->Ri=L->Ri-1;for(j=i-2;(L->R0.key<L->Rj.key);-j)L->Rj+1=L->Rj;/記錄后移L->Rj+1=L->R0;/插入到正確的位置PrintSort(L); /輸出排序結果a=1; (2)折半插入排序： void BInsertSort(SqList L) /折半插入排序int i,j,m,low,high;for(i=2;i<=L->lengt

10、h;+i) L->R0=L->Ri;/將L->Ri暫存到L->R0 low=1;high=i-1; while(low<=high)/在Rlow.high中折半查找有序插入的位置 m=(low+high)/2; /折半第4頁 if(L->R0.key<L->Rm.key) high=m-1; /插入點在低區else low=m+1; /插入點在高區for(j=i-1;j>=high+1;-j) L->Rj+1=L->Rj; /記錄后移 L->Rhigh+1=L->R0; /插入PrintSort(L); /輸出排序結

11、果a=1;/將a重新初始化為 (3)冒泡排序： void BubbleSort(SqList L) /冒泡排序；int i,j,m;for(i=1;i<L->length;i+) for(j=0;j<L->length;j+) /選擇表L中最大的依次放到最后面的位置中去 if(L->Rj.key>L->Rj+1.key&&j<L->length) m=L->Rj.key;L->Rj.key=L->Rj+1.key; L->Rj+1.key=m;PrintSort(L);/輸出排序結果 a=1; (4)

12、簡單選擇排序： void SelectSort(SqList L) /簡單選擇排序int i,j,m;int SelectMinKey(SqList L,int i);for(i=1;i<L->length;+i) /選擇第i小的記錄，并交換到位j=SelectMinKey(L,i); /在L->Ri.L->length中選擇key最小記錄if(i!=j) /與第i個記錄交換m=L->Ri.key;L->Ri.key=L->Rj.key;L->Rj.key=m; PrintSort(L);a=1; (5)快速排序： void QuickSort(

13、SqList L) /快速排序QSort(L,1,L->length); /對順序表L調用快速排序第5頁a=1; void QSort(SqList L,int low ,int high)int pivotloc;if(low<high) pivotloc=Partition(L,low,high);/L表一分為二 QSort(L,low,pivotloc-1); /對低位子表遞歸排序 QSort(L,pivotloc+1,high);/對高位子表遞歸排序(6)堆排序： void HeapSort(SqList L) /堆排序int i,m;for(i=L->length/

14、2;i>0;-i) /把L->R1.L->length建成大頂堆 HeapAdjust(L,i,L->length);for(i=L->length;i>1;-i)m=L->R1.key;/將堆頂記錄和當前未經排序子序列L->R1.i中L->R1.key=L->Ri.key; /最后一個記錄相互交換L->Ri.key=m;PrintSort(L);HeapAdjust(L,1,i-1); /將L->R1.i-1重新調整為大頂堆a=1;(7)歸并排序： void MergeSort(SqList L, int length)

15、 /歸并排序 int i, left_min, left_max, right_min, right_max, next; int *tmp = (int*)malloc(sizeof(int) * length); if (tmp = NULL) fputs("Error: out of memoryn", stderr); for (i = 1; i < length; i *= 2) / i為步長，1,2,4,8 for (left_min = 1; left_min <= length-i; left_min = right_max) right_min

16、=left_max = left_min+i; right_max=left_max + i; if (right_max > length) right_max = length+1; next = 1;第6頁 while (left_min < left_max && right_min < right_max) tmpnext+ = L->Rleft_min.key >L->Rright_min.key ? L->Rright_min+.key : L->Rleft_min+.key; while (left_min <

17、; left_max) L->R-right_min.key = L->R-left_max.key; while (next > 1) L->R-right_min.key = tmp-next; PrintSort(L); a=1; free(tmp);三、上機結果及體會1. 實際完成的情況說明： 本程序基本完成了直接插入排序、折半插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序以及歸并排序的算法功能，并能輸出各種排序算法的每一趟排序結果。 本程序僅支持整形數據（int 類型）。2. 程序算法的性能分析：第7頁3. 程序運行時的初值和運行結果： (1)直接插入排序

18、： (2)折半插入排序：第8頁 (3)冒泡排序： (4)簡單選擇排序：第9頁 (5)快速排序： (6)堆排序：第10頁 (7)歸并排序：4. 程序中可以改進的地方說明 本程序對誤操作的處理不是很理想，而且對數據的要求也比較嚴格，只能是int類型的數據才行，另外，堆排序不能將生成的堆以二叉樹的形式輸出。以上這些都是可以改進的地方。5. 收獲及體會：通過這次課程設計的學習讓我學會了許多。讓我對數據結構知識有了很大理解！在這次課程設計中，我獨立完成了直接插入排序、折半插入排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序等幾種排序算法。雖然在算法完成的過程中出現了好多問題，但我對這次課程設計的

19、成果還是非常滿意的。 第11頁這次的課程設計還有很多不足之處，如用指針代替函數的調用。在完成這個課程設計后，我也學到了很多知識，并能訓練的掌握他們了。我撐握了每種排序算法的基本思想，并從同學那里學會了編寫程序的一般步驟：思考問題，寫出解決方案，寫出偽代碼，完成代碼，調試程序。不像以前那樣開始就直接寫代碼。 但我還是認為自己有些不足，希望以后能彌補這些不足。所以，這次的課程設計我學會了很多，不光讓我認識了數據結構知識，還讓我學會了一些道理，那就是做事情的時候即使不會做也不能慌張，要慢慢放下心來，不要光想著自己怎么、怎么不會了！不要去想不會，而是冷下心來慢慢思考、思考。這樣你就會有了思路的。 6.

20、 源程序及注釋：#include<stdio.h>#include<windows.h># define MAXSIZE 30 /順序表的最大長度int a=1; /全局變量，用于標記排序的趟數typedef structint key; /關鍵字RedType; /記錄類型typedef struct RedType RMAXSIZE+1;/R0閑置為哨兵int length; /順序表長度*SqList,sq; /順序表類型Void PrintSort(SqList L) /輸出函數 int i=1;printf("#n");printf(&qu

21、ot;第%d 趟排序結果為:",a+);while(i<=L->length) printf("%d ",L->Ri.key);i+; printf("n"); void FiPrintSort(SqList L) /輸出最終結果int i=1;printf("#n");printf("最終的排序結果為:");while(i<=L->length) printf("%d ",L->Ri.key); i+; printf("n");

22、 int CreatSqList(SqList L) /順序表的創建第12頁int i=0; int j=1; char ch;printf("#n"); printf("請輸入待排整數(整數之間用空格隔開,按回車結束):");do i+; scanf("%d%c",&L->Ri.key,&ch); while(ch!='n'); L->length=i;printf("#n"); printf("初始的待排序列為:");while(j<=L-&

23、gt;length) printf("%d ",L->Rj.key); j+; printf("n"); return 1; int artition(SqList L,int low ,int high) int key; /樞紐記錄L->R0=L->Rlow; /表的第一元素記錄樞紐關鍵字key=L->Rlow.key; while(low<high)while(low<high&&L->Rhigh.key>=key)-high;/將比樞紐記錄小的移到低端L->Rlow=L->

24、;Rhigh;while(low<high&&L->Rlow.key<=key)+low; /將比樞紐記錄大的移到高端L->Rhigh=L->Rlow;L->Rlow=L->R0; /樞紐記錄到位PrintSort(L); /輸出排序結果return low; void sertSort(SqList L) /直接插入排序 int i,j;for(i=2;i<=L->length;+i)if(L->Ri.key<L->Ri-1.key) /需將L->Ri插入有序子表L->R0=L->Ri;

25、 /復制為哨兵L->Ri=L->Ri-1;for(j=i-2;(L->R0.key<L->Rj.key);-j) L->Rj+1=L->Rj;/記錄后移L->Rj+1=L->R0;/插入到正確的位置PrintSort(L); /輸出排序結果a=1;第13頁void BInsertSort(SqList L) /折半插入排序int i,j,m,low,high;for(i=2;i<=L->length;+i)L->R0=L->Ri;/將L->Ri暫存到L->R0low=1;high=i-1;while(lo

26、w<=high) /在Rlow.high中折半查找有序插入的位置m=(low+high)/2; /折半if(L->R0.key<L->Rm.key) high=m-1; /插入點在低區else low=m+1; /插入點在高區for(j=i-1;j>=high+1;-j)L->Rj+1=L->Rj; /記錄后移 L->Rhigh+1=L->R0; /插入PrintSort(L); /輸出排序結果a=1;/將a重新初始化為1void BubbleSort(SqList L) /冒泡排序int i,j,m;for(i=1;i<L->

27、length;i+) for(j=0;j<L->length;j+) /選擇表L中最大的依次放到最后面的位置中去 if(L->Rj.key>L->Rj+1.key&&j<L->length) m=L->Rj.key; L->Rj.key=L->Rj+1.key; L->Rj+1.key=m;PrintSort(L);/輸出排序結果 a=1;void SelectSort(SqList L) /簡單選擇排序int i,j,m;int SelectMinKey(SqList L,int i);for(i=1;i<

28、;L->length;+i)/選擇第i小的記錄，并交換到位j=SelectMinKey(L,i); /在L->Ri.L->length中選擇key最小記錄if(i!=j) /與第i個記錄交換m=L->Ri.key; L->Ri.key=L->Rj.key; L->Rj.key=m; PrintSort(L);第14頁a=1;int SelectMinKey(SqList L,int i) /在L->Ri.L->length中選擇key最小記錄int m=i,n=L->Ri.key;for(;i<=L->length;i+)

29、if(n>=L->Ri.key) n=L->Ri.key;m=i;return m; void QSort(SqList L,int low ,int high)int pivotloc;if(low<high)pivotloc=Partition(L,low,high);/L表一分為二QSort(L,low,pivotloc-1); /對低位子表遞歸排序QSort(L,pivotloc+1,high);/對高位子表遞歸排序Void QuickSort(SqList L) /快速排序QSort(L,1,L->length); /對順序表L調用快速排序a=1;voi

30、d HeapAdjust(SqList L,int s,int m) /已知L->Rs.m中記錄的關鍵字除int i,j; /L->s.key之外均滿足堆的定義，本函數調整i=L->Rs.key;/L->Rs 的關鍵字，使L->Rs.m成為一個大頂堆(對其中記錄的關鍵字而言)for(j=2*s;j<=m;j*=2) /沿key較大的孩子結點向下篩選if(j<m&&(L->Rj.key<L->Rj+1.key)+j;/j為key較大的記錄的下標if(!(i<L->Rj.key)/i應插入在位置上break;L

31、->Rs.key=L->Rj.key; s=j;/插入L->Rs.key=i;void HeapSort(SqList L) /堆排序int i,m;for(i=L->length/2;i>0;-i) /把L->R1.L->length建成大頂堆HeapAdjust(L,i,L->length);for(i=L->length;i>1;-i)第15頁m=L->R1.key; /將堆頂記錄和當前未經排序子序列L->R1.i中L->R1.key=L->Ri.key; /最后一個記錄相互交換L->Ri.key=

32、m; PrintSort(L);HeapAdjust(L,1,i-1); /將L->R1.i-1重新調整為大頂堆a=1; void MergeSort(SqList L, int length) /歸并排序 int i, left_min, left_max, right_min, right_max, next; int *tmp = (int*)malloc(sizeof(int) * length); if (tmp = NULL) fputs("Error: out of memoryn", stderr); for (i = 1; i < length

33、; i *= 2) / i為步長，1,2,4,8 for (left_min = 1; left_min <= length-i; left_min = right_max) right_min=left_max = left_min+i; right_max=left_max + i; if (right_max > length) right_max = length+1; next = 1; while (left_min < left_max && right_min < right_max) tmpnext+=L->Rleft_min.k

34、ey>L->Rright_min.key? L->Rright_min+.key : L->Rleft_min+.key; while (left_min < left_max) L->R-right_min.key = L->R-left_max.key; while (next > 1) L->R-right_min.key = tmp-next; PrintSort(L); a=1; free(tmp); void Menu() /菜單printf("t*歡迎使用本排序系統*n");printf("t*n

35、n");printf("t 直接插入排序 (InsertSort)-請輸入1 nn");第16頁printf("t 折半插入排序 (BinaryInsertSort)-請輸入2 nn");printf("t 冒泡排序 (BubbleSort)-請輸入3 nn");printf("t 選擇排序 (SelectSort)-請輸入4 nn");printf("t 快速排序 (QuickSort)-請輸入5 nn");printf("t 堆排序 (HeapSort)-請輸入6 nn&

36、quot;);printf("t 歸并排序 (MergetSort)-請輸入7 nn");printf("t 退出 (Exit)-請輸入8 nn");printf("t*n"); void main() /主函數int n,b=0; sq list=0,0; /初始化SqList L=&list;system("cls"); /清屏Menu();do printf("t請您選擇(1-8)(_):"); scanf("%d",&n); getchar();if(

37、n>=1&&n<=8) b=1; break; else b=0;printf("t您輸入有誤，請重新選擇!n"); while(b=0);while(b=1) switch(n) /用于菜單功能選擇 case 1:system("cls");/清屏 printf("tt直接插入排序(InsertSort)nn"); CreatSqList(L); InsertSort(L); FiPrintSort(L);printf("#n"); system("pause"); main(); break;case 2:system("cls");