數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(內(nèi)部排序之堆排序)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書內(nèi)部排序之堆排序的實(shí)現(xiàn)學(xué)生姓名 羅通 學(xué) 號 1118014124 班 級 計本1104班 成 績 指導(dǎo)教師 林勇 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院 2013年9月9日 課程設(shè)計任務(wù)書20132014學(xué)年第一學(xué)期課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課程設(shè)計題目： 內(nèi)部堆排序算法的實(shí)現(xiàn) 完 成 期 限：自 2013年 9月9日至 2013年 9月 21 日共 2 周設(shè)計內(nèi)容：1.任務(wù)說明堆排序是數(shù)據(jù)結(jié)構(gòu)中內(nèi)排序部分的重點(diǎn)知識。堆分為大頂堆和小頂堆。堆排序的過程主要解決兩個問題

2、：（1）把無序序列建成一個堆；（2）輸出堆頂元素后，重新將剩余元素調(diào)整成新堆。本課程設(shè)計主要完成的核心內(nèi)容即為此。按以下的要求運(yùn)用C/ C+結(jié)構(gòu)體、指針、數(shù)據(jù)結(jié)構(gòu)等基知識編程實(shí)現(xiàn)。2.要求1）問題分析和任務(wù)定義：根據(jù)設(shè)計題目的要求，充分地分析和理解問題，明確問題要求做什么？ 2）邏輯設(shè)計：寫出抽象數(shù)據(jù)類型的定義，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3）詳細(xì)設(shè)計：定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。4）程序編碼：把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。5）程序調(diào)試與測試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。6）結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有

3、錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析；7）編寫課程設(shè)計報告；3.參考資料指導(dǎo)教師：林勇 教研室負(fù)責(zé)人：曹陽課程設(shè)計評閱評語： 指導(dǎo)教師簽名： 年 月 日摘 要 為了查找方便，通常希望通過排序使表成為按鍵字有序的。本課題利用簡單排序的堆排序方法，通過建立大根堆，并對元素進(jìn)行輸出，實(shí)現(xiàn)用戶輸入的一組可以組成堆的數(shù)據(jù)元素進(jìn)行處理，使其按關(guān)鍵字排成一個有序的序列，從而有效的提高了查找效率。再加上界面友好、操作簡單，使其更加好用。關(guān)鍵詞：堆 排序 查找 流程控制 目 錄 1.課題描述- 2.需求分析- 2.0算法分析- 2.1 抽象數(shù)據(jù)類型定義- 2.2程序設(shè)計流程圖- 3. 各函數(shù)功能實(shí)

4、現(xiàn)及調(diào)用關(guān)系- 3.1各函數(shù)功能實(shí)現(xiàn)- 3.2 各函數(shù)之間的調(diào)用關(guān)系- 4. 主代碼- 5.程序運(yùn)行測試與結(jié)果分析- 5.1函數(shù)功能檢驗(yàn)與各步運(yùn)行結(jié)果的說明（圖）- 5.2出錯狀況的解決（圖）- 5.3 時間復(fù)雜度與空間復(fù)雜度- 6.總結(jié)- 參考文獻(xiàn)- 1 課題描述在現(xiàn)在帶生活的各個領(lǐng)域里，人們?yōu)榱瞬檎曳奖悖ǔＯＭ嬎銠C(jī)中的表是按關(guān)鍵字有序的。因此排序就成了計算機(jī)程序設(shè)計中的一種重要操作。本課題利用簡單選擇排序中的堆排序方法，通過對用戶輸入的可以組成堆的數(shù)據(jù)元素建立大、小根堆，并將其進(jìn)行排序輸出，使其成為一個按關(guān)鍵字排序的有序序列，從而有效地提高了查找的效率。開發(fā)工具：vc+6.02 問題分

5、析 2.0算法分析 堆的定義如下：n個元素的序列k1,k2,.,kn當(dāng)且僅當(dāng)滿足下關(guān)系時，稱堆。 Ki<=k2i ;ki<=k2i+1 或者 ki=>k2i; ki=>k2i+1(i = 1,2,3.,n/2)若將和此序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作為數(shù)列的存儲結(jié)構(gòu)）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有的非終端節(jié)點(diǎn)的值均不小于（或不大于）其左右孩子節(jié) 點(diǎn)的值，由此，若序列k1,k2,.,kn是堆，則堆頂元素必為序列中n個元素的最大值。 2.1抽象數(shù)據(jù)類型定義 ADT HeapSort 數(shù)據(jù)對象: D=ki|ki屬于Elemset，i = 1,2,3.

6、,n,n=>0; 數(shù)據(jù)關(guān)系：R1=<ki,k2i,k2i+1>|Ki<=k2i;ki<=k2i+1或 ki=>k2i;ki=>k2i+1 ； 基本操作： void SCANF(Heap* list); 操作結(jié)果：輸入的一組數(shù)據(jù)存入順序表中 void HeapAdjustlittle(Heap* list,int s,int m); 初始條件：list中存有一組無序數(shù)列 操作結(jié)果：將list中的無序數(shù)列調(diào)整為一個小頂堆 void HeapSortlittle(Heap*list); 操作結(jié)果：把調(diào)整好的小頂堆進(jìn)行排序并進(jìn)行再調(diào)整 void HeapAdj

7、ustbig(Heap* list,int s,int m); 初始條件：list中存有一組無序數(shù)列 操作結(jié)果：將list中的無序數(shù)列調(diào)整為一個大頂堆 void HeapSortbig(Heap*list); 操作結(jié)果：把調(diào)整好的小頂堆進(jìn)行排序并進(jìn)行再調(diào)整 void PRINTF1(Heap*list); 操作結(jié)果：將排好的或者正在排列的序列進(jìn)行堆型輸出 void PRINTF2(Heap*list); 操作結(jié)果：輸出最終升序或者降序排序結(jié)果 ADT HeapSort 2.2 程序設(shè)計流程圖（以大頂堆的設(shè)計為例）2.2.1整體設(shè)計思想流程圖：圖2.1 整體設(shè)計思想流程圖2.2.2函數(shù)設(shè)計流程圖

8、 建堆函數(shù)HeapAdjust：堆的定義如下：n個元素的序列k1,k2,.,kn當(dāng)且僅當(dāng)滿足下關(guān)系時，稱堆。Ki<=k2i ;ki<=k2i+1 或者 ki=>k2i; ki=>k2i+1(i = 1,2,3.,n/2)若將和此序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作為數(shù)列的存儲結(jié)構(gòu)）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有的非終端節(jié)點(diǎn)的值均不小于（或不大于）其左右孩子節(jié)點(diǎn)的值，由此，若序列k1,k2,.,kn是堆，則堆頂元素必為序列中n個元素的最大值。 建立大頂堆函數(shù)的程序流程圖如圖2.2。圖2.2 建立大頂堆函數(shù)的程序流程圖輸出堆形函數(shù)PRINTF1: 在堆

9、排序的函數(shù)中，結(jié)果用堆型的動態(tài)變化來反映無疑是最好的。因此，就要設(shè)計良好的流程控制來反映出程序運(yùn)行結(jié)果中的堆型。輸出大頂堆函數(shù)的程序流程圖如圖2.3。圖2.3 輸出大頂堆函數(shù)的程序流程圖3 各函數(shù)功能的實(shí)現(xiàn) 3.1 各函數(shù)的功能實(shí)現(xiàn)/大頂堆的建立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;

10、 lists = listj; s = j;lists = rc;/小頂堆的建立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;/輸出堆函數(shù)(輸出堆型)void PRINTF1(Heap* list) int h=0,sum=0,item=1

11、; int cnt=1,tmp=1; while(sum<=list0.key) sum+=item; h+; item*=2; /求出堆所對應(yīng)的完全二叉樹的高度h。 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)goto end; printf("%5d",listc

12、nt+); printf("n");tmp*=2; end: printf("n"); /輸出已排序數(shù)組函數(shù)void PRINTF2(Heap* list) printf("IN THE END 最終經(jīng)過堆排序后的序列為："); for(int i=1;i<=list0.key;i+) printf("%d ",listi.key); printf("n");3.2各函數(shù)之間的調(diào)用關(guān)系 箭頭指向主調(diào)函數(shù)，箭尾為被調(diào)函數(shù)4.主代碼#include<stdio.h>#include

13、<stdlib.h>typedef struct NODEint key; Heap;void SCANF(Heap* list);void HeapAdjustlittle(Heap* list,int s,int m);void HeapAdjustbig(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(&q

14、uot;ttt2013-2014年計算機(jī)系課程設(shè)計");printf("nn");printf("ttnn");printf("tt 班級： 計本1104班 nn");printf("tt 姓名： 羅 通 nn");printf("tt 學(xué)號： 1118014124 nn");printf("tt 課題： 內(nèi)部排序之堆排序 nn");printf("ttnn");/用順序表來存儲堆void SCANF(Heap* list)printf(&quo

15、t;請輸入你要排序的序列的個數(shù)：");scanf("%d",&list0.key);if(list0.key >15)printf("對不起，現(xiàn)在暫時只分配了表長為15的順序表！nn");printf("請輸入小于15的值，或者手動將主函數(shù)里分配表長改為你想要的值!nn");exit(0);printf("n");printf("請輸入你要排序的數(shù)列：");for(int i=1;i<=list0.key;i+)scanf("%d",&l

16、isti.key);if(sizeof(1 = listi.key)printf("請輸入正確的數(shù)據(jù)（整形數(shù)字）。nn");exit(0);elseprintf("t");printf("n");/調(diào)整堆為大頂堆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

17、.key)break; lists = listj; s = j; lists = rc;/輸出堆頂元素開始進(jìn)行堆排序void HeapSortbig(Heap*list) Heap p; for(int i=list0.key/2,m=1;i>0;-i,+m) HeapAdjustbig(list,i,list0.key); printf("經(jīng)過%d次調(diào)整的堆序列為:",m); for(int j=1;j<=list0.key;j+) printf("%d ",listj.key); printf("相應(yīng)的堆形為：n")

18、; PRINTF1( list); printf("nn"); for(i=list0.key;i>1;-i) p = list1; list1 = listi; listi = p; HeapAdjustbig(list,1,i-1); /調(diào)整堆為小頂堆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

19、>listj.key) break; lists = listj; s = j; lists = rc;/輸出堆頂元素開始進(jìn)行堆排序void HeapSortlittle(Heap*list) Heap p; for(int i=list0.key/2,m=1;i>0;-i,+m) HeapAdjustlittle(list,i,list0.key); printf("經(jīng)過%d次調(diào)整的堆序列為:",m); for(int j=1;j<=list0.key;j+) printf("%d ",listj.key); printf("

20、;相應(yīng)的堆形為：n"); PRINTF1( list); printf("nn"); for(i=list0.key;i>1;-i) p = list1;list1 = listi;listi = p;HeapAdjustlittle(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(&quo

21、t;堆排序堆型如下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 EN

22、D 最終經(jīng)過堆排序后的序列為："); for(int i=1;i<=list0.key;i+) printf("%d ",listi.key); printf("n");/主函數(shù)void main() Heap tmp; desktop(); Heap list15; SCANF(list); printf("-n"); printf("請注意! ! !現(xiàn)在是大頂堆的升序排序.n"); printf("-nnn"); HeapSortbig(list); printf("

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

24、ntf("-nnn"); HeapSortlittle(list); printf("-現(xiàn)在按照步驟來輸出已經(jīng)排好的序列-nnn"); for( i=1;i<=list0.key ;i+) printf("經(jīng)過第%d步調(diào)整，現(xiàn)在的已排序列是：",i); for(int j=1;j<i+1;j+)printf("%d ",listj.key ); printf("nn"); printf("nn"); PRINTF2(list);5.程序運(yùn)行測試與結(jié)果分析 5.1函

25、數(shù)功能檢驗(yàn)與各步運(yùn)行結(jié)果說明（圖） 5.1.1 輸入你要排列的數(shù)列5.1.2 輸入數(shù)列的大頂堆建立與調(diào)整5.1.3 大頂堆的分布排序結(jié)果 5.1.4 大頂堆的升序排序的最終結(jié)果 5.1.5輸入序列堆排序與調(diào)整5.1.6 小頂堆的分布排序結(jié)果 5.1.7 小頂堆的升序排序的最終結(jié)果 5.2出錯情況的分析 情況一：輸入的數(shù)列中元素個數(shù)超過初始上限 解決方法： 情況二：在輸入數(shù)據(jù)時，不小心輸入了不可排序的字符 解決方法：5.3時間復(fù)雜度與空間復(fù)雜度分析 堆排序是選擇排序中的一種，它只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。堆排序方法對記錄較少的文件不值得提倡，但對于較大的文件是很有效的。堆排序在最壞的情況下，其時間復(fù)雜度也為O（nlogn）。相對于快速排序來說，這是最大的優(yōu)點(diǎn)。6 總結(jié)學(xué)期初的課程設(shè)計實(shí)踐讓我把以