數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.

1、茨筋寒工摩整數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書內(nèi)部排序之堆排序的實(shí)現(xiàn)學(xué)生姓名羅通學(xué)號-1118014124班級計本1104班成績指導(dǎo)教師林勇數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院課程設(shè)計任務(wù)書2013 2014學(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)知識。堆分為大頂堆和小頂堆。堆排序的過程主要解決兩個問題：（1）把無序序列建成一個堆；（2 ）輸出堆頂元素后，重新將剩余元素調(diào)整成新堆。本課程設(shè)計主要完成的核心內(nèi)容即為此。按以下的要求運(yùn)用C/ C+結(jié)構(gòu)體、指針、數(shù)據(jù)結(jié)構(gòu)等基

2、知識編程實(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é)果和含有錯誤的輸入及其輸出結(jié)果。算法 的時間、空間復(fù)雜性分析；7）編寫課程設(shè)計報告；3參考資料指導(dǎo)教師：林勇教研室負(fù)責(zé)人：曹陽課程設(shè)計評閱評語:指導(dǎo)教師簽名:摘要為了查找方

3、便，通常希望通過排序使表成為按鍵字有序的。本課題利用簡單排序的堆 排序方法，通過建立大根堆，并對元素進(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í)現(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.

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

5、i+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,n,n=>0;數(shù)據(jù)關(guān)系： R1=<ki,k2i,k2i+1>|Ki<=k2i;ki<=k2i+1或 ki=>k2i;ki=>k2i+1；基本操

6、作：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 HeapAdjustbig(Heap* list,int s,int m);初始條件： list 中存有一組無序數(shù)列操作結(jié)果：將 list 中的無序數(shù)列調(diào)整為一個大頂堆void HeapSortbig(Heap*

7、list);操作結(jié)果：把調(diào)整好的小頂堆進(jìn)行排序并進(jìn)行再調(diào)整void PRINTF1(Heap*list);操作結(jié)果：將排好的或者正在排列的序列進(jìn)行堆型輸出void PRINTF2(Heap*list);操作結(jié)果：輸出最終升序或者降序排序結(jié)果ADT HeapSort2.2程序設(shè)計流程圖（以大頂堆的設(shè)計為例）221整體設(shè)計思想流程圖:圖2.1整體設(shè)計思想流程圖函數(shù)設(shè)計流程圖建堆函數(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,

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

9、函數(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;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;/ 輸出堆函數(shù) ( 輸出堆型 ) 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; / 求出堆所對應(yīng)的完全二叉樹的高度 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");/ 輸出已排序數(shù)組函數(shù)void PRINTF2(Heap* list)printf("IN THE

12、 END 最終經(jīng)過堆排序后的序列為： ");for(int i=1;i<=list0.key;i+)prin tf("%d ",listi.key);prin tf("n");3.2各函數(shù)之間的調(diào)用關(guān)系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()年計算機(jī)系課程設(shè)計 ");printf("ttt2013-2014 printf("nn");printf("ttnn");printf("tt班級：計本 1104 班printf("tt姓名：羅通p

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

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

16、")；/ 調(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.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

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

18、-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>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&g

19、t;0;-i,+m) :",m);HeapAdjustlittle(list,i,list0.key); printf(" 經(jīng)過 %d 次調(diào)整的堆序列為 for(int j=1;j<=list0.key;j+) printf("%d ",listj.key);printf(" 相應(yīng)的堆形為： 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最終經(jīng)過堆排序后的序列為： ");for(int i=1;i<=list0.key;i+)printf("%d ",listi.key);printf("n");/ 主函數(shù)void main()Heap tmp;desktop();He

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

23、;printf("nn");PRINTF2(list);printf("n");printf(" 請注意 ! ! ! 現(xiàn)在是小頂堆的降序排序 printf("nnn");HeapSortlittle(list);printf(" 現(xiàn)在按照步驟來輸出已經(jīng)排好的序列for( i=1;i<=list0.key ;i+)printf(" 經(jīng)過第 %d 步調(diào)整，現(xiàn)在的已排序列是： 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.程序運(yùn)行測試與結(jié)果分析5.1函數(shù)功能檢驗(yàn)與各步運(yùn)行結(jié)果說明(圖)輸入你要排列的數(shù)列2813亠噸年計U機(jī)系譙程設(shè)計pppppdpp ppp ppppppptipFpp e(?(?ppp(*pp woE褪住涎班級*計本丄詢斗班昶輕解姓名；羅il03盹蝕G啊 ppee 學(xué)號*ljL18H1412ppppppepeecoee課題=內(nèi)部排存之堆排序 peewwepeeceu

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

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

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