堆排序算法課程設(shè)計

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書堆排序的算法的實現(xiàn)學(xué)生姓名學(xué)號班級成績指導(dǎo)教師計算機科學(xué)與技術(shù)系2011 年3月4日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計評閱書題目堆排序原理的算法的實現(xiàn)學(xué)生姓名學(xué)號指導(dǎo)教師評語成績：指導(dǎo)教師簽名：年 月日答辯教師評語成績：答辯教師簽名：年 月日教研室意見成績：室主任簽名：年月日注：指導(dǎo)教師成績60%答辯成績40%總成績合成后按五級制記入陝筋理工警整課程設(shè)計任務(wù)書2010 2011學(xué)年第二學(xué)期專業(yè)：學(xué)號：姓名：課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目：堆排序算法的實現(xiàn)完成期限：自2011年2 月19 日至2011 年 月丄4日共2 周設(shè)計依據(jù)、要求及主要內(nèi)容（可另加附頁）：堆實質(zhì)上是滿足如下

2、性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點的關(guān)鍵字。如關(guān)鍵字序列（10, 15, 56, 25, 30, 70）和（70, 56, 30, 25, 15, 10）分別滿足堆性質(zhì)（1）和，故它們均是堆。大根堆和小根堆：根結(jié)點（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為 小根堆，又稱最小堆。根結(jié)點（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者，稱 為大根堆，又稱最大堆。注意：堆中任一子樹亦是堆。以上討論的堆實際上是二叉堆（Bi nary Heap）,大根堆排序的基本思想：先將初始文件R1.n建成一個大根堆，此堆為初始的無序區(qū)。再將關(guān)鍵字

3、最大的記錄R1（即堆頂）和無序區(qū)的最后一個記錄 Rn交換，由此得 到新的無序區(qū)R1.n-1和有序區(qū)Rn，且滿足R1.n- 1.keys Rn.key 。由于交換后新的根R1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū) R1.n-1調(diào)整為堆。 然后再次將R1.n-1中關(guān)鍵字最大的記錄R1和該區(qū)間的最后一個記錄 Rn-1交換，由 此得到新的無序區(qū)R1. n-2 和有序區(qū)Rn-1.n,且仍滿足關(guān)系 R1.n- 2.keys Rn-1.n.keys ，同樣要將 R1.n-2 調(diào)整為堆。要求：（1）給出一個符合堆序列的一組數(shù)，能夠建立大根堆和小根堆。（2）界面友好，可操作性強。（3）能夠?qū)崿F(xiàn)數(shù)據(jù)個數(shù)的變化輸入，并建

4、立相應(yīng)的堆。指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期:摘要設(shè)計了一個堆排序算法實現(xiàn)的程序， 此程序具有排序的功能， 能夠?qū)斎氲娜魏螖?shù)字進(jìn)行處理之后， 有序的輸出。在設(shè)計之前，首先要明白什么是堆，以及堆排序的原理，明白了原理之后，結(jié)合之前所掌 握的C+編程知識，分部分進(jìn)行編譯，最后再進(jìn)行組合，完成此程序之后，可視化界面比較清晰，操作 比較簡單，易于為用戶接受 。關(guān)鍵詞 ：堆排序；大頂堆 ；篩選目錄 TOC o 1-5 h z 課題描述 1問題分析和任務(wù)定義 2邏輯設(shè)計 3程序編碼 6結(jié)果分析 8總結(jié) 10參考文獻(xiàn) 11 課題描述本課題是利用堆排序的算法原理對數(shù)據(jù)進(jìn)行排序，使所輸入的數(shù)

5、據(jù)以遞減或者遞增的方式輸出,要是利用堆排序算法進(jìn)行設(shè)計，設(shè)計篩選函數(shù)，和排序函數(shù)，以及對這些函數(shù)的綜合運用。問題分析和任務(wù)定義本次程序設(shè)計，主要設(shè)計的問題是如何利用堆排序原理進(jìn)行設(shè)計，應(yīng)該結(jié)合書本所含有的理論，結(jié)合一些程序?qū)嵗?，進(jìn)行完成，本次設(shè)計的任務(wù)是， 編一個能夠?qū)崿F(xiàn)堆排序算法的程序，并設(shè)計一個可視化界面，此次程序設(shè)計過程中，有兩大模塊，一個是篩選函數(shù)，另一個是排序函數(shù)。3.1堆排序主函數(shù)流程圖 邏輯設(shè)計運用數(shù)據(jù)結(jié)構(gòu)中所學(xué)的函數(shù)進(jìn)行流程圖設(shè)計。堆排序主函數(shù)3.2堆排序篩選函數(shù) 大頂堆篩選函數(shù)3.3堆排序排序函數(shù) 大頂堆排序函數(shù) 程序編碼#in elude #in elude using n

6、 amespaee std;void BigHeapAdjust(i nt *p, int r, int len);void BigHeapSort(i nt *p, int len);int mai n()int array1OOO = 0;int n;printf(”請輸入排序元素的個數(shù)：);scan f(%d, &n);prin tf(請輸入要排序的元素：);for(i nt i=0; in; +i)scanf(%d, array+i);BigHeapSort(array, n); prin tf(結(jié)果是：); for(i nt k=0; kn; +k) prin tf(%d , arr

7、ayk); getchar(); getchar(); getchar(); return 0; void BigHeapAdjust(i nt *p, int r, int len) int tmp = pr;int j;for(j=2*r+1; j=le n-1; j=2*j+1)if(j=pj)+j;if(tmp = pj)break;pr = pj;r = j;pr = tmp; void BigHeapSort(i nt *p, int len) int i,j;for(i=le n/2-1; i=0; -i)BigHeapAdjust(p, i, le n);p0 A= ple n

8、-1;ple n-1 a= p0;p0 a= ple n-1; for(j=len-1; j1; -j) BigHeapAdjust(p, 0, j);p0 a= pj-1;pj-1 a= p0;p0 a= pj-1;5.結(jié)果分析5.1.輸入界面5.1輸入要排序的函數(shù)個數(shù)5. 2輸入元素的個數(shù)5.2輸入所要排序的函數(shù)5.3程序運行結(jié)果* D:CD ebugiji baba .exeI 5 i 元 素的 兀序： W參: 刀入是 齧果 請請結(jié)5.3函數(shù)結(jié)果輸岀5.4函數(shù)異常輸入to continueDAC092330921024051Debugixuan.exe,S4 4 4B-7 素K5 元序4

9、 32回果請請結(jié)5.4函數(shù)異常輸岀結(jié)果6. 總結(jié)在本次程序設(shè)計中，運用了堆排序的基本原理，在首先了解什么事堆的情況下，然后結(jié)合所學(xué)的知識進(jìn)行編程，在編程的過程中，首先要了解大頂堆， 小頂堆的定義，以及如何利用堆排序的原理進(jìn)行排 序，在設(shè)計程序之前，應(yīng)先畫出流程圖，在畫圖的過程中，應(yīng)該正確了解各個圖形的意義，不能錯用， 對于經(jīng)常使用的選擇， 判斷等的特殊圖形要正確使用，以及箭頭所指的方向， 都要仔細(xì)，在完成了對流程圖的設(shè)計后，就要根據(jù)流程圖進(jìn)行編程，在編程的時候，首先要明白程序的主題函數(shù)，先從主函數(shù)開始，結(jié)合流程圖進(jìn)行編譯，正確使用特殊語句，以及關(guān)鍵字，在這過程要用到for循環(huán)語句，最重要的就是

10、要寫出正確的判斷語句，搞清楚程序的結(jié)束的點， 在完成主函數(shù)的編譯之后，就要進(jìn)行子函數(shù)的編譯，次函數(shù)包括兩個子函數(shù)，一個是大頂堆的篩選，另一個是大頂堆的排序，在大頂堆的篩選的時候， 要明白堆排序的實質(zhì)，就是從最后一個非葉子節(jié)點開始，從它的左右子樹開始比較，順著子樹較大的方向往父節(jié)點平移，最后和序列的最后一個數(shù)據(jù)進(jìn)行交換，把它放置在閑置的空間內(nèi)，在進(jìn)行大頂堆的排序的時候，對上面的交換完成之后， 先找出一個最大的， 然后對其余的數(shù)據(jù)進(jìn)行重復(fù)的比較，方法和大頂堆的篩選一樣，直至待排序的數(shù)據(jù)按順序輸出。在編程的完成之后，要進(jìn)行仔細(xì)的檢驗，找出錯誤， 進(jìn)行多次驗證，確保此程序準(zhǔn)確無誤， 并且要使程序簡單明了，便于操作者使用方便。 在進(jìn)行了此次程序設(shè)計之后，明白了如何利用堆排序原理進(jìn)行對數(shù)據(jù)的排序，對以前所學(xué)的知識進(jìn)行了鞏固，增加了實踐的經(jīng)驗。參考文獻(xiàn)嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）