《(完整word版)數(shù)據(jù)結(jié)構(gòu)排序?qū)嶒瀳蟾?word文檔良心出品).doc》由會員分享，可在線閱讀，更多相關(guān)《(完整word版)數(shù)據(jù)結(jié)構(gòu)排序?qū)嶒瀳蟾?word文檔良心出品).doc（10頁珍藏版）》請在匯文網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)課程設計報告實驗五 排序一、需求分析：本演示程序用C+6.0編寫，完成各種排序的實現(xiàn)，對輸入的一組數(shù)字實現(xiàn)不同的排序方法，對其由小到大順序輸出。（1）分別對直接插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序算法進行編寫。（2）、對存儲的函數(shù)即輸入的數(shù)字進行遍歷。（3）、初始化函數(shù)對輸入的數(shù)字進行保存。（4）、主函數(shù)實現(xiàn)使用者操作界面的編寫，對輸入、選擇、保存、輸出的各種實現(xiàn)。這當中還包括了各個函數(shù)的調(diào)用的實現(xiàn)。（5）、程序所能達到的功能：完成對輸入的數(shù)字的生成，并通過對各排序的選擇實現(xiàn)數(shù)字從小到大的輸出。二、程序主要功能以及基本要求：（1）、設計一個菜單，格式如下：1、直接插

2、入排序2、希爾排序3、冒泡排序4、快速排序5、選擇排序6、堆排序7、退出（2）、選擇不同的菜單但進行相應的排序，并給出排序的關(guān)鍵字序列。三、系統(tǒng)框架圖：本程序包含了9個函數(shù)，它們分別是：（1）、直接插入排序的算法函數(shù)InsertSort（）。（2）、希爾排序的算法函數(shù)ShellSort（）。主函數(shù)（3）、冒泡排序算法函數(shù)BubbleSort（）。操作界面的設計，函數(shù)的調(diào)用。對輸入的數(shù)組進行遍歷初始化各個排序算法函數(shù)（4）、快速排序的算法函數(shù)Partition（）。（5）、選擇排序算法函數(shù)SelectSort（）。（6）、堆排序算法函數(shù)HeapAdjust（）。（7）、對存儲數(shù)字的遍歷函數(shù)Vis

3、it（）。（8）、初始化函數(shù)InitSqList（）。（9）、主函數(shù)main（）。四、詳細設計實現(xiàn)各個算法的主要內(nèi)容，下面是各個函數(shù)的主要信息：（1）各個排序函數(shù)的算法：一、直接插入排序void InsertSort(SqList &L)int i,j;for( i=2; i=L.length;i+)if(L.ri.key L.ri-1.key)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;二、希爾排序void ShellSort(SqList &L) int

4、i, j; int dk = 1;/增量 while(dk 0)dk /= 3;/減小增量for (i = dk; i = dk) & (L.rj-dk.key L.r0.key) L.rj.key = L.rj-dk.key; j -= dk; L.rj.key = L.r0.key; 三、冒泡排序void BubbleSort(SqList &L)int i,j;for(i=0;iL.length-2;i+)int flag = 1;for(j=0;j L.rj+1.key)flag = 0;int temp;temp = L.rj.key;L.rj.key = L.rj+1.key;L.

5、rj+1.key = temp;/若無交換說明已經(jīng)有序if(flag=1)break;四、快速排序int Partition(SqList &L,int low,int high)/分割區(qū)域函數(shù)L.r0 = L.rlow;int pivotkey = L.rlow.key;/一般將順序表第一個元素作為支點while(low high)while(low=pivotkey)high-;L.rlow = L.rhigh;while(lowhigh & L.rlow.key=pivotkey)low+;L.rhigh = L.rlow;L.rlow = L.r0;/返回樞軸位置return low;

6、void QSort(SqList &L,int low,int high)/每張子表的快速排序if(lowhigh)int pivotloc = Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);void QuickSort(SqList &L)QSort(L,1,L.length);五、簡單選擇排序void SelectSort(SqList &L)int min;int j;for (int i = 0; i L.length; i+) / 選擇第i小的記錄，并交換j = i;min = L.ri

7、.key;for (int k = i; k L.length; k+) / 在Ri.n-1中選擇最小的記錄if (L.rk.key min) min = L.rk.key ;j = k;if (i != j) / 與第i個記錄交換int temp = L.ri.key;L.ri.key = L.rj.key;L.rj.key = temp;六、堆排序void HeapAdjust(HeapType &H,int s,int m)/堆調(diào)整，將記錄調(diào)整為小頂堆int j;RedType rc = H.rs;/暫時存儲根結(jié)點for(j=2*s; j=m; j*=2)/沿著結(jié)點記錄較小的向下篩選if

8、(jm & H.rj.key= H.rj.key)break;H.rs = H.rj;s = j;H.rs = rc;void HeapSort(HeapType &H)int i;RedType temp;for(i = H.length; i0; -i)HeapAdjust(H,i,H.length);for(i=H.length; i1; -i)temp = H.r1;H.r1 = H.ri;H.ri = temp;HeapAdjust(H,1,i-1);（2）遍歷函數(shù)與初始化void Visit(SqList L)for(int i=1; i=L.length; i+)coutL.ri

9、.key ;coutendl;void InitSqList(SqList &L,int a)for(int i=1;i=L.length;i+)L.ri.key = ai;五、測試結(jié)果以下是各種界面的測試結(jié)果：（1）輸入的界面 :（2）排序操作界面：（3）各種排序的結(jié)果： 六、設計不足以及存在問題本程序是基于C+6.0的實現(xiàn)，其實在設計上的改進可以利用類進行操作，這種類的改進了存儲上的不足還可以實現(xiàn)了，對各種的函數(shù)基于類的實現(xiàn)，這就是對本程序的改進，這是十分重要的與是改進的基礎。本程序出現(xiàn)過的問題是主函數(shù)對個函數(shù)的調(diào)用以及對存儲數(shù)組的調(diào)用上出現(xiàn)了問題，導致排序的結(jié)果以及排序的界面出現(xiàn)了問題，的不到實現(xiàn)。后來對算法進行改進，最終把問題得以解決。10