1、茨筋寒工摩整數據結構課程設計設計說明書內部排序之堆排序的實現學生姓名羅通學號-1118014124班級計本1104班成績指導教師林勇數學與計算機科學學院課程設計任務書2013 2014學年第一學期課程設計名稱：數據結構課程設計課程設計題目：內部堆排序算法的實現完成期限：自2013年9月9日至2013年9月21日共2周設計內容：1. 任務說明堆排序是數據結構中內排序部分的重點知識。堆分為大頂堆和小頂堆。堆排序的過程主要解決兩個問題：（1）把無序序列建成一個堆；（2 ）輸出堆頂元素后，重新將剩余元素調整成新堆。本課程設計主要完成的核心內容即為此。按以下的要求運用C/ C+結構體、指針、數據結構等基

2、知識編程實現。2. 要求1 ）問題分析和任務定義：根據設計題目的要求，充分地分析和理解問題，明確問題要求做什么？2）邏輯設計：寫出抽象數據類型的定義，各個主要模塊的算法，并畫出模塊之間的調用關系圖；3）詳細設計：定義相應的存儲結構并寫出各函數的偽碼算法。4）程序編碼：把詳細設計的結果進一步求精為程序設計語言程序。5）程序調試與測試：采用自底向上，分模塊進行，即先調試低層函數。6）結果分析：程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。算法 的時間、空間復雜性分析；7）編寫課程設計報告；3參考資料指導教師：林勇教研室負責人：曹陽課程設計評閱評語:指導教師簽名:摘要為了查找方

3、便，通常希望通過排序使表成為按鍵字有序的。本課題利用簡單排序的堆 排序方法，通過建立大根堆，并對元素進行輸出，實現用戶輸入的一組可以組成堆的數據 元素進行處理，使其按關鍵字排成一個有序的序列，從而有效的提高了查找效率。再加上 界面友好、操作簡單，使其更加好用。關鍵詞:堆 排序查找流程控制1. 課題描述 2. 需求分析 2.0 算法分析 2.1 抽象數據類型定義 2.2 程序設計流程圖 3. 各函數功能實現及調用關系 3.1 各函數功能實現 3.2 各函數之間的調用關系 4. 主代碼 5. 程序運行測試與結果分析 5.1 函數功能檢驗與各步運行結果的說明（圖） 5.2 出錯狀況的解決（圖） 5.

4、3 時間復雜度與空間復雜度 6. 總結 參考文獻 1 課題描述在現在帶生活的各個領域里， 人們為了查找方便， 通常希望計算機中的表是按關鍵字有 序的。因此排序就成了計算機程序設計中的一種重要操作。本課題利用簡單選擇排序中的堆排序方法， 通過對用戶輸入的可以組成堆的數據元素建 立大、小根堆，并將其進行排序輸出，使其成為一個按關鍵字排序的有序序列，從而有效地 提高了查找的效率。開發工具： vc+6.02 問題分析2.0 算法分析堆的定義如下：n 個元素的序列 k1,k2,kn當且僅當滿足下關系時，稱堆。Ki<=k2i ;ki<=k2i+1或者 ki=>k2i; ki=>k2

5、i+1(i = 1,2,3,n/2)若將和此序列對應的一維數組 (即以一維數組作為數列的存儲結構) 看成是一個完全二叉樹， 則堆的含義表明， 完全二叉樹中所有的非終端節點的值均不小于 (或不大于) 其左右孩子節 點的值，由此，若序列k1,k2,kn是堆，則堆頂元素必為序列中n個元素的最大值。2.1 抽象數據類型定義ADT HeapSort數據對象 : D=ki|ki 屬于 Elemset ， i = 1,2,3,n,n=>0;數據關系： R1=<ki,k2i,k2i+1>|Ki<=k2i;ki<=k2i+1或 ki=>k2i;ki=>k2i+1；基本操

6、作：void SCANF(Heap* list);操作結果：輸入的一組數據存入順序表中void HeapAdjustlittle(Heap* list,int s,int m);初始條件： list 中存有一組無序數列操作結果：將 list 中的無序數列調整為一個小頂堆void HeapSortlittle(Heap*list);操作結果：把調整好的小頂堆進行排序并進行再調整void HeapAdjustbig(Heap* list,int s,int m);初始條件： list 中存有一組無序數列操作結果：將 list 中的無序數列調整為一個大頂堆void HeapSortbig(Heap*

7、list);操作結果：把調整好的小頂堆進行排序并進行再調整void PRINTF1(Heap*list);操作結果：將排好的或者正在排列的序列進行堆型輸出void PRINTF2(Heap*list);操作結果：輸出最終升序或者降序排序結果ADT HeapSort2.2程序設計流程圖（以大頂堆的設計為例）221整體設計思想流程圖:圖2.1整體設計思想流程圖函數設計流程圖建堆函數HeapAdjust :堆的定義如下：n個元素的序列k1,k2,.,kn當且僅當滿足下關系時，稱堆。Ki<=k2i ;ki<=k2i+1或者 ki=>k2i; ki=>k2i+1（i = 1,2,

8、3.,n/2）若將和此序列對應的一維數組（即以一維數組作為數列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有的非終端節點的值均不小于（或不大于）其左右孩子節點的值，由此，若序列k1,k2,.,kn是堆,則堆頂元素必為序列中n個元素的最大值。建立大頂堆函數的程序流程圖如圖2.2。/ tc = lists j = 21 7/ j+ /圖2.2建立大頂堆函數的程序流程圖輸出堆形函數PRINTF1:在堆排序的函數中， 結果用堆型的動態變化來反映無疑是最好的。因此，就要設計良好的流程控制來反映出程序運行結果中的堆型。輸出大頂堆函數的程序流程圖如圖2.3。3 各函數功能的實現3.1 各

9、函數的功能實現/ 大頂堆的建立void HeapAdjustbig(Heap* list,int s,int m)int j;Heap rc;rc = lists;for(j=2*s;j<=m;j*=2)if(j<m&&(listj.key<listj+1.key) +j;if(!(rc.key<listj.key)break;lists = listj; s = j;lists = rc;/ 小頂堆的建立void HeapAdjustlittle(Heap* list,int s,int m)int j;Heap rc;rc = lists;for(j

10、=2*s;j<=m;j*=2)if(j<m&&(listj.key>listj+1.key) +j;if(!(rc.key>listj.key)break;lists = listj;s = j;lists = rc;/ 輸出堆函數 ( 輸出堆型 ) void PRINTF1(Heap* list) int h=0,sum=0,item=1; int cnt=1,tmp=1; while(sum<=list0.key) sum+=item; h+;item*=2; / 求出堆所對應的完全二叉樹的高度 h 。printf("n")

11、;printf(" 堆排序堆型如下 n");while(1)for(int i=0;i<h;i+)for(int j=0;j<h-i;j+)printf(" ");for(j=0;j<tmp;j+)if(cnt>list0.key)goto end; printf("%5d",listcnt+);printf("n");tmp*=2;end:printf("n");/ 輸出已排序數組函數void PRINTF2(Heap* list)printf("IN THE

12、 END 最終經過堆排序后的序列為： ");for(int i=1;i<=list0.key;i+)prin tf("%d ",listi.key);prin tf("n");3.2各函數之間的調用關系4. 主代碼#include<stdio.h>#include<stdlib.h>typedef struct NODE int key;Heap;void SCANF(Heap* list);void HeapAdjustlittle(Heap* list,int s,int m); void HeapAdjust

13、big(Heap* list,int s,int m); void HeapSortlittle(Heap*list);void HeapSortbig(Heap*list);void PRINTF1(Heap*list);void PRINTF2(Heap*list);/ 桌面顯示個人信息void desktop()年計算機系課程設計 ");printf("ttt2013-2014 printf("nn");printf("ttnn");printf("tt班級：計本 1104 班printf("tt姓名：羅通p

14、rintf("tt學號：1118014124printf("tt課題：內部排序之堆排序nn");nn"); nn"); nn");printf("ttnn");/ 用順序表來存儲堆void SCANF(Heap* list)printf(" 請輸入你要排序的序列的個數： ");scanf("%d",&list0.key);if(list0.key >15)printf(" 對不起，現在暫時只分配了表長為 15 的順序表！ nn");print

15、f(" 請輸入小于 15 的值，或者手動將主函數里分配表長改為你想要的 值!nn ”)；exit(0);printf("n")；printf(" 請輸入你要排序的數列： ")； for(int i=1；i<=list0.key；i+) scanf("%d",&listi.key)； if(sizeof(1 = listi.key) printf(" 請輸入正確的數據(整形數字)。 nn")； exit(0)；else printf("t")； printf("n

16、")；/ 調整堆為大頂堆void HeapAdjustbig(Heap* list,int s,int m)int j；Heap rc； rc = lists； for(j=2*s；j<=m；j*=2) if(j<m&&(listj.key<listj+1.key)+j； if(!(rc.key<listj.key)break； lists = listj； s = j； lists = rc；/ 輸出堆頂元素開始進行堆排序void HeapSortbig(Heap*list)Heap p;for(int i=list0.key/2,m=1;i

17、>0;-i,+m)HeapAdjustbig(list,i,list0.key);:",m);printf("經過 %d 次調整的堆序列為for(int j=1;j<=list0.key;j+)printf("%d ",listj.key);printf(" 相應的堆形為： n"); PRINTF1( list);printf("nn");for(i=list0.key;i>1;-i)p = list1;list1 = listi; listi = p;HeapAdjustbig(list,1,i

18、-1);/ 調整堆為小頂堆void HeapAdjustlittle(Heap* list,int s,int m)int j;Heap rc;rc = lists;for(j=2*s;j<=m;j*=2)if(j<m&&(listj.key>listj+1.key)+j;if(!(rc.key>listj.key)break;lists = listj; s = j; lists = rc;/ 輸出堆頂元素開始進行堆排序 void HeapSortlittle(Heap*list)Heap p;for(int i=list0.key/2,m=1;i&g

19、t;0;-i,+m) :",m);HeapAdjustlittle(list,i,list0.key); printf(" 經過 %d 次調整的堆序列為 for(int j=1;j<=list0.key;j+) printf("%d ",listj.key);printf(" 相應的堆形為： n"); PRINTF1( list);printf("nn"); for(i=list0.key;i>1;-i)p = list1; list1 = listi; listi = p;HeapAdjustlitt

20、le(list,1,i-1);/ 輸出堆void PRINTF1(Heap* list)int h=0,sum=0,item=1;int cnt=1,tmp=1;while(sum<=list0.key)sum+=item; h+; item*=2;printf("n");printf(" 堆排序堆型如下 n");while(1)for(int i=0;i<h;i+)for(int j=0;j<h-i;j+)printf(" ");for(j=0;j<tmp;j+)if(cnt>list0.key)got

21、o end; printf("%5d",listcnt+);printf("n");tmp*=2;end:printf("n");/ 輸出最后排好的堆序列void PRINTF2(Heap* list)printf("IN THE END最終經過堆排序后的序列為： ");for(int i=1;i<=list0.key;i+)printf("%d ",listi.key);printf("n");/ 主函數void main()Heap tmp;desktop();He

22、ap list15;SCANF(list);printf("n");printf(" 請注意 ! ! ! 現在是大頂堆的升序排序 printf("nnn");HeapSortbig(list);printf(" 現在按照步驟來輸出已經排好的序列for(int i=1;i<=list0.key ;i+)printf(" 經過第 %d 步調整，現在的已排序列是： for(int j=1;j<i+1;j+)printf("%d ",listj.key );printf("nn")

23、;printf("nn");PRINTF2(list);printf("n");printf(" 請注意 ! ! ! 現在是小頂堆的降序排序 printf("nnn");HeapSortlittle(list);printf(" 現在按照步驟來輸出已經排好的序列for( i=1;i<=list0.key ;i+)printf(" 經過第 %d 步調整，現在的已排序列是： for(int j=1;j<i+1;j+) printf("%d ",listj.key );print

24、f("nn");printf("nn");PRINTF2(list);n");nnn");",i);n");nnn");",i);5.程序運行測試與結果分析5.1函數功能檢驗與各步運行結果說明(圖)輸入你要排列的數列2813亠噸年計U機系譙程設計pppppdpp ppp ppppppptipFpp e(?(?ppp(*pp woE褪住涎班級*計本丄詢斗班昶輕解姓名；羅il03盹蝕G啊 ppee 學號*ljL18H1412ppppppepeecoee課題=內部排存之堆排序 peewwepeeceu

25、 euu卩卩哄*(?叫叫* e hcpb 卩 b?r ee情諭人你要搟序的序列的個敕'B潔輸人你妥排隔的釈列* 1 3 5 0 1S 33輸入數列的大頂堆建立與調整大頂堆的分布排序結果現在按照步理來輔出已經排好的序列經過第1步調整現在的己排佯列JS，3經過黑去步調整，現在的已排序列杲a 1經過第日步調整*現在的已推序列杲1 a 1 3經過第馬步調鑿*現在的已排序列晶0 1 3 S輕過第呂步調整，現在的己排序列杲t a 1 3 s經過第呂步調整，現在的已排序列是;a 1 3 s , 15輕過第啦調鑒現在酊已排序列是0 1 3 S15 21L經過第B步調8L現在的已排序?|杲：0 13 s

26、 9152133大頂堆的升序排序的最終結果TH IHE END最終經過堆排序后的序列為* 0 1359152133輸入序列堆排序與調整諭注意t T規在是小他舉曬降序排序眸包（抿調空的堆序列為油135*152133相應的堆丹惓耕仔堆型如下591£2133經過2次調堂的堆序列汨洱13?152133相應的堆形拘工堆排序堆型如Fa17S 3152133經過2次週整的堆序列為誨13 E 9 l S1 33 相用的堆形詢013«91&2113經過峙次謂整的堆序列為詢11 S 15 K1 33 相應的菇形為:灘排序堆型如下591521711小頂堆的分布排序結果一一現在按晚步球來輪

27、出已經排好的仔列經過第直步調整.現在的己排序列是| 33經過第2步調整現在的己排序列是，33 21經過第3步調螫.現在的已排序列是|陽21 15經過執步調整.現在的已排序列晶33 21 15 9經過第石步調整.現在的已排序33 21 15 3 5經過第&步鞠4L現在的己排序列是33211595經過第丁步關整.現在的己排序是：3321 1S ?5經過第目步調整.現在的己排序5U是I 33 21 1S ? 5小頂堆的升序排序的最終結果嚴THE EHD最終經過堆排序啟的序列為.32 21 IS 9 S 3 1 «Pmss Any ke y la co nt dntie5.2出錯情況的分析情況一：輸入的數列中元素個數超過初始上限解決方法：精蓉黔勲証的順序表！晴輸入小于15的值.或者羊動將主函故里分配喪長改為你標蔓的值號情況二：在輸入數據時，不小心輸入了不可排序的字符 解決方法：請輸入你琴誹序的序列的個數，8主fl?列鑒3)1¥ipess any Jkew eentiftiie5.3時間復雜度與空間復雜度分析堆排序是選擇排序中的一種，它只需要一個記錄大小的輔助空間，每個待排序的記錄僅占 有一個存儲空間。堆排序方法對記錄較少的文件不值得提倡，但對于較大的文件是很