版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、<p><b> 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p><b> 設(shè)計說明書</b></p><p><b> 計算機科學(xué)與技術(shù)系</b></p><p><b> 2011年9月9日</b></p><p> 內(nèi)部堆排序算法的實現(xiàn)&
2、lt;/p><p><b> 課程設(shè)計任務(wù)書</b></p><p> 2011—2012學(xué)年第一學(xué)期</p><p> 課程設(shè)計名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 </p><p> 設(shè)計題目:
3、 內(nèi)部堆排序算法的實現(xiàn) </p><p> 完成期限:自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周</p><p> 設(shè)計依據(jù)、要求及主要內(nèi)容:</p><p> 堆實質(zhì)上是滿
4、足如下性質(zhì)的完全二叉樹:樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。如關(guān)鍵字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分別滿足堆性質(zhì)(1)和(2),故它們均是堆。 </p><p> 大根堆和小根堆:根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最小者的堆稱為小根堆,又稱最小堆。根結(jié)點(亦稱為堆頂)的關(guān)鍵字是堆里所有結(jié)點關(guān)鍵字中最大者
5、,稱為大根堆,又稱最大堆。注意:①堆中任一子樹亦是堆。②以上討論的堆實際上是二叉堆(Binary Heap),</p><p> 大根堆排序的基本思想:</p><p> ?、?先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區(qū)。</p><p> ② 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換,由此得到新的無序區(qū)R[1.
6、.n-1]和有序區(qū)R[n],且滿足R[1..n-1].keys≤R[n].key。</p><p> ?、塾捎诮粨Q后新的根R[1]可能違反堆性質(zhì),故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換,由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n],且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].key
7、s,同樣要將R[1..n-2]調(diào)整為堆。</p><p> 要求 :(1)給出一個符合堆序列的一組數(shù),能夠建立大根堆和小根堆。</p><p> (2)界面友好,可操作性強。</p><p> ?。?)能夠?qū)崿F(xiàn)數(shù)據(jù)個數(shù)的變化輸入,并建立相應(yīng)的堆。</p><p> 指導(dǎo)教師(簽字):
8、 教研室主任(簽字): </p><p> 批準(zhǔn)日期: 年 月 日</p><p><b> 摘 要</b></p><p> 隨著計算機技術(shù)的發(fā)展,為了查找方便,通常希望通過排序使表是按關(guān)鍵字有序的。本課題利用簡單選擇排序中的堆排序方法,通過建立大、小根堆,并對數(shù)據(jù)元素
9、進行排序輸出,實現(xiàn)對用戶輸入的一組可以組成堆的數(shù)據(jù)元素進行處理,使其按關(guān)鍵字排成為一個有序的序列,從而有效地提高了查找效率。</p><p> 關(guān)鍵詞:堆;排序;查找</p><p><b> 目 錄</b></p><p><b> 1 課題描述1</b></p><p><b&g
10、t; 2 設(shè)計過程2</b></p><p><b> 2.1 流程圖2</b></p><p> 2.1.1函數(shù)設(shè)計思想流程圖2</p><p> 2.1.2程序流程圖2</p><p> 2.2分步程序設(shè)計7</p><p> 2.2.1 建立堆函數(shù)7<
11、;/p><p> 2.2.2輸出堆函數(shù)7</p><p> 2.2.3輸出已排序數(shù)組函數(shù)9</p><p> 2.2.4主函數(shù)9</p><p><b> 3 測試12</b></p><p> 3.1第一組測試數(shù)據(jù)測試結(jié)果12</p><p> 3.2第
12、二組測試數(shù)據(jù)測試結(jié)果13</p><p><b> 總 結(jié)16</b></p><p><b> 參考資料17</b></p><p><b> 附 錄18</b></p><p><b> 程序源代碼18</b></p>
13、<p><b> 1 課題描述</b></p><p> 隨著計算機技術(shù)的發(fā)展,為了查找方便,通常希望計算機中的表是按關(guān)鍵字有序的。因為有序的順序表可采用查找效率較高的折半查找法,而無序的表只能進行順序查找。排序是計算機程序設(shè)計中的一種重要操作,它的功能是將一個數(shù)據(jù)元素(或記錄)的任意序列,重新排列成一個按關(guān)鍵字有序的序列。因此,學(xué)習(xí)和研究各種排序方法是計算機工作者的重要課
14、題之一。</p><p> 本課題利用簡單選擇排序中的堆排序方法,通過對用戶輸入的可以組成堆的數(shù)據(jù)元素建立大、小根堆,并將其進行排序輸出,使其成為一個按關(guān)鍵字排序的有序序列,從而有效地提高了查找的效率。</p><p> 開發(fā)工具:TC 2.0</p><p><b> 2 設(shè)計過程</b></p><p><
15、;b> 2.1 流程圖</b></p><p> 2.1.1函數(shù)設(shè)計思想流程圖:</p><p> 函數(shù)設(shè)計思想流程圖如圖2.1。</p><p> 圖2.1 函數(shù)設(shè)計思想流程圖</p><p> 2.1.2程序流程圖</p><p> 建立大根堆函數(shù)的程序流程圖如圖2.2。</p
16、><p> 圖2.2 建立大根堆函數(shù)的程序流程圖</p><p> 建立小根堆函數(shù)的程序流程圖如圖2.3。</p><p> 圖2.3 建立小根堆函數(shù)的程序流程圖</p><p> 輸出大根堆函數(shù)的程序流程圖如圖2.4。</p><p> 圖2.4 輸出大根堆函數(shù)的程序流程圖</p><
17、p> 輸出小根堆函數(shù)的程序流程圖如圖2.5。</p><p> 圖2.5 輸出小根堆函數(shù)的程序流程圖</p><p><b> 2.2分步程序設(shè)計</b></p><p> 2.2.1 建立堆函數(shù)</p><p> 當(dāng)運行程序,用戶按照提示輸入正確的信息并敲擊回車鍵時,程序就會相應(yīng)地建立出大、小根堆函數(shù)
18、,為后續(xù)的運行做準(zhǔn)備。</p><p><b> 程序源代碼如下:</b></p><p><b> //建立大根堆函數(shù)</b></p><p> void buildbig(int *a,int i,int n){</p><p><b> int tmp;</b>&
19、lt;/p><p><b> k=i;</b></p><p><b> j=2*k+1;</b></p><p> while(j<=n){</p><p> if(j<n && a[j]<a[j+1])</p><p><b&g
20、t; j++;</b></p><p> if(a[k]>=a[j])break;</p><p><b> tmp=a[k];</b></p><p> a[k]=a[j];</p><p> a[j]=tmp; </p><p><b>
21、k=j;</b></p><p><b> j=2*j+1;</b></p><p><b> }</b></p><p><b> }</b></p><p><b> //建立小根堆函數(shù)</b></p><p&g
22、t; void buildlittle(int *a,int i,int n){</p><p><b> int tmp;</b></p><p><b> k=i;</b></p><p><b> j=2*k+1;</b></p><p> while(j<
23、;=n){</p><p> if(j<n && a[j]>a[j+1])</p><p><b> j++;</b></p><p> if(a[k]<=a[j])break;</p><p><b> tmp=a[k];</b></p>&
24、lt;p> a[k]=a[j];</p><p> a[j]=tmp; </p><p><b> k=j;</b></p><p><b> j=2*j+1;</b></p><p><b> }</b></p><p>
25、<b> }</b></p><p> 2.2.2輸出堆函數(shù)</p><p> 當(dāng)計算機已經(jīng)生成了相應(yīng)的堆函數(shù)之后,就會自動運行此模塊,將其輸出。</p><p><b> 程序源代碼如下:</b></p><p><b> //輸出大根堆函數(shù)</b></p&g
26、t;<p> void prnthpbig(int *a,int b1,int b2){</p><p><b> int size;</b></p><p> int h=0,sum=0,item=1;</p><p> int i,j,cnt,start,tmp;</p><p> size=
27、b2-b1+1;</p><p> while(sum<=size){</p><p> sum+=item;</p><p><b> h++;</b></p><p><b> item*=2;</b></p><p><b> }</b&
28、gt;</p><p><b> item=1;</b></p><p><b> cnt=0;</b></p><p><b> start=b1;</b></p><p><b> tmp=1;</b></p><p>
29、 printf("───────────────────────\n"); </p><p> printf("▼大根堆排序如下:┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈\n");</p><p><b> while(1){</b></p><p> for(i=0;i<h;i++){<
30、/p><p> for(j=0;j<h-i;j++)</p><p> printf(" ");</p><p> for(j=0;j<i+1;j++)printf(" "); </p><p> for(j=0;j<tmp;j++){</p><p>
31、; if(cnt>size-1)goto end;</p><p> printf("%4d",a[cnt++]);</p><p><b> }</b></p><p> printf("\n");</p><p><b> tmp*=2;</b&
32、gt;</p><p><b> } </b></p><p><b> }</b></p><p><b> end:</b></p><p> printf("\n"); </p><p>
33、return; </p><p><b> }</b></p><p><b> //輸出小根堆函數(shù)</b></p><p> void prnthplittle(int *a,int b1,int b2){</p><p><b> int si
34、ze;</b></p><p> int h=0,sum=0,item=1;</p><p> int i,j,cnt,start,tmp;</p><p> size=b2-b1+1;</p><p> while(sum<=size){</p><p> sum+=item;</p
35、><p><b> h++;</b></p><p><b> item*=2;</b></p><p><b> }</b></p><p><b> item=1;</b></p><p><b> cnt=0;
36、</b></p><p><b> start=b1;</b></p><p><b> tmp=1;</b></p><p> printf("───────────────────────\n"); </p><p> printf("▲小
37、根堆排序如下:┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈\n");</p><p><b> while(1){</b></p><p> for(i=0;i<h;i++){</p><p> for(j=0;j<h-i;j++)</p><p> printf(" ");&l
38、t;/p><p> for(j=0;j<i+1;j++)printf(" "); </p><p> for(j=0;j<tmp;j++){</p><p> if(cnt>size-1)goto end;</p><p> printf("%4d",a[cnt++]);</
39、p><p><b> }</b></p><p> printf("\n");</p><p><b> tmp*=2;</b></p><p><b> } </b></p><p><b> }<
40、/b></p><p><b> end:</b></p><p> printf("\n"); </p><p> return; </p><p><b> }</b></p><p>
41、 2.2.3輸出已排序數(shù)組函數(shù)</p><p> 輸出已經(jīng)排好的序列數(shù)據(jù),顯示每一步排序出的結(jié)果。</p><p><b> 源代碼如下:</b></p><p> //輸出已排序數(shù)組函數(shù)</p><p> void prntar(int *a,int b2,int len){</p><p&
42、gt;<b> int i; </b></p><p> printf("○已排序序列數(shù)如下:┈┈┈┈┈┈┈┈┈┈┈┈┈┈\n");</p><p> for(i=0;i<b2;i++){</p><p> printf(" ");</p><p> }
43、 </p><p> for(i=b2;i<=len;i++){</p><p> printf("%3d",a[i]);</p><p> } </p><p> printf("\n");</p><p><b> } &
44、lt;/b></p><p><b> 2.2.4主函數(shù)</b></p><p> 運行程序時,在用戶數(shù)據(jù)輸入正確之后,主函數(shù)運行并調(diào)用相應(yīng)的函數(shù),完成全部任務(wù)。</p><p><b> 源代碼如下:</b></p><p><b> main(){</b>&l
45、t;/p><p> int a[50];</p><p><b> int i;</b></p><p><b> int tmp;</b></p><p><b> int sum;</b></p><p><b> int len;&
46、lt;/b></p><p> printf("╭━━━━━━━━━━━━━━━━━━━━━━╮\n");</p><p> printf("┃─── 計本092 金強勝 0918014051 ────┃\n");</p><p> printf("┃
47、 ┃\n");</p><p> printf("┃──────(數(shù)據(jù)結(jié)構(gòu)課程設(shè)計)──────┃\n");</p><p> printf("┃───── 內(nèi)部堆排序算法的實現(xiàn) ─────┃\n");</p><p> printf("╰──────────
48、────────────╯\n");</p><p> printf("★請您輸入欲排序數(shù)的個數(shù),并以回車鍵結(jié)束:");</p><p> scanf("%3d",&len);</p><p> printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n"); </p&
49、gt;<p> printf("★請輸入能組建堆的無序序列數(shù)的值,并以回車鍵結(jié)束:\n ");</p><p> for(i=0;i<len;i++)</p><p> scanf("%3d",&a[i]); </p><p> tmp=1;sum=0;</p>
50、<p> while(sum+tmp<=len){</p><p> sum+=tmp; </p><p><b> tmp*=2;</b></p><p><b> } </b></p><p><b> //建初始堆</b><
51、;/p><p> for(i=sum-1;i>=0;i--)</p><p> buildbig(a,i,len-1); </p><p> prnthpbig(a,0,len-1); </p><p><b> //改建堆</b></p><p> for(i=0;i&l
52、t;len-1;i++){</p><p><b> tmp=a[0];</b></p><p> a[0]=a[len-1-i];</p><p> a[len-1-i]=tmp;</p><p> buildbig(a,0,len-2-i);</p><p> prnthpbig(a
53、,0,len-2-i);</p><p> prntar(a,len-1-i,len-1); </p><p><b> }</b></p><p> printf("\n───────────────────────\n");</p><p> printf("★大根
54、堆排序的最后結(jié)果如下:┈┈┈┈┈┈┈┈┈┈\n"); </p><p> prnt(a,len);</p><p> printf("\n··················
55、······\n\n");</p><p> for(i=sum-1;i>=0;i--)</p><p> buildlittle(a,i,len-1);</p><p> prnthplittle(a,0,len-1);</p><p><b>
56、//改建堆</b></p><p> for(i=0;i<len-1;i++){</p><p><b> tmp=a[0];</b></p><p> a[0]=a[len-1-i];</p><p> a[len-1-i]=tmp;</p><p> buildli
57、ttle(a,0,len-2-i);</p><p> prnthplittle(a,0,len-2-i);</p><p> prntar(a,len-1-i,len-1); </p><p><b> }</b></p><p> printf("\n─────────────────
58、──────\n");</p><p> printf("★小根堆排序的最后結(jié)果如下:┈┈┈┈┈┈┈┈┈┈\n"); </p><p> prnt(a,len);</p><p> printf("\n☆☆☆☆謝謝您的使用,請按任意鍵結(jié)束!☆☆☆☆☆\n");</p><p&g
59、t;<b> return 0;</b></p><p><b> }</b></p><p><b> 3 測試</b></p><p> 3.1第一組測試數(shù)據(jù)測試結(jié)果</p><p> 測試數(shù)據(jù):96 83 27 38 11 9</p><p&
60、gt; 主界面和大根堆排序的部分過程如圖3.1。</p><p> 圖3.1 主界面和大根堆排序的部分過程</p><p> 大根堆排序的最后結(jié)果如圖3.2。</p><p> 圖3.2 大根堆排序的最后結(jié)果</p><p> 大根堆排序結(jié)束,小根堆排序的開始及部分過程如圖3.3。</p><p> 圖
61、3.3 大根堆排序結(jié)束,小根堆排序的開始及部分過程</p><p> 小根堆排序的最后結(jié)果及程序運行結(jié)束如圖3.4。</p><p> 圖3.4 小根堆排序的最后結(jié)果及程序運行結(jié)束</p><p> 3.2第二組測試數(shù)據(jù)測試結(jié)果</p><p> 測試數(shù)據(jù):12 36 24 85 47 30 53 91</p>&l
62、t;p> 主界面和大根堆排序的部分過程如圖3.5。</p><p> 圖3.5 主界面和大根堆排序的部分過程</p><p> 大根堆排序的最后結(jié)果如圖3.6。</p><p> 圖3.6 大根堆排序的最后結(jié)果</p><p> 大根堆排序結(jié)束,小根堆排序的開始及部分過程如圖3.7。</p><p>
63、; 圖3.7 大根堆排序結(jié)束,小根堆排序的開始及部分過程</p><p> 小根堆排序的最后結(jié)果及程序運行結(jié)束如圖3.8。</p><p> 圖3.8 小根堆排序的最后結(jié)果及程序運行結(jié)束</p><p><b> 總 結(jié)</b></p><p> 兩周的課程設(shè)計結(jié)束了,過程是艱辛的,但是收獲也是很大的。我
64、主要是應(yīng)用了所學(xué)習(xí)的C和C++編程語言和軟件,以及數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識,并參考相關(guān)書籍以及請教老師和同學(xué),綜合起來才完成了這次課程設(shè)計。</p><p> 本次課程設(shè)計讓我把以前學(xué)習(xí)到的知識得到鞏固和進一步的提高認(rèn)識,對已有知識有了更進一步的理解和認(rèn)識。在課程設(shè)計中,我碰到了很多的問題,通過查閱相關(guān)書籍,資料,通過自己鉆研,同時特別是得到了老師的諄諄教導(dǎo),給予了我很大的幫助,不僅給了我思路上的開闊,還讓我認(rèn)識到了
65、自己對以前所學(xué)知識的不足方面。</p><p> 隨著社會發(fā)展,計算機的迅速普及以及飛速發(fā)展,掌握計算機方面相關(guān)的知識越來越迫切,掌握一定的計算機基礎(chǔ)技術(shù)已經(jīng)成為一大必備技能。排序是計算機程序設(shè)計中極其重要的一部分,是計算機程序設(shè)計中的一個重要操作,它的功能是將一個數(shù)據(jù)元素(或記錄)的任意序列,重新排列成一個按關(guān)鍵字有序的序列。學(xué)習(xí)和研究各種排序方法是計算機工作者的重要課題之一。堆排序是選擇排序中的一種,它只需
66、要一個記錄大小的輔助空間,每個待排序的記錄僅占有一個存儲空間。堆排序方法對記錄較少的文件不值得提倡,但對于較大的文件是很有效的。堆排序在最壞的情況下,其時間復(fù)雜度也為O(nlogn)。相對于快速排序來說,這是最大的優(yōu)點。這次課程設(shè)計我主要應(yīng)用所學(xué),通過在C和C++編程環(huán)境下,實現(xiàn)了對符合堆的無序序列進行排序。 </p><p> 當(dāng)然,通過這次課程設(shè)計,我也發(fā)現(xiàn)了自身的很多不足之處,在以后的學(xué)習(xí)中,我會不斷的完
67、善自我,不斷進取,使自己有一個大的發(fā)展。</p><p><b> 參考資料</b></p><p> [1] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版).北京.清華大學(xué)出版社.2007.</p><p> [2] 羅建軍,朱丹君,顧剛,劉路放.C++程序設(shè)計教程(第二版).北京.高等教育出版社.2007.</p><p&g
68、t; [3] 譚浩強.C語言程序設(shè)計教程.高等教育出版社.2004.</p><p> [4]何欽銘,顏暉C.語言程序設(shè)計.北京.高等教育出版社.2008.</p><p> [5]AL KELLEY,IRA POHL.C語言教程[M].4版.徐波,譯.北京:機械工業(yè)出版社.2007.</p><p> [6]KOCHAN S G.C語言編程[M].3版.張
69、小潘,譯.北京:電子工業(yè)出版社,2006.</p><p><b> 附 錄</b></p><p><b> 程序源代碼:</b></p><p> #include<stdio.h></p><p><b> int k,j;</b></p>
70、;<p><b> //建立大根堆函數(shù)</b></p><p> void buildbig(int *a,int i,int n){</p><p><b> int tmp;</b></p><p><b> k=i;</b></p><p><
71、b> j=2*k+1;</b></p><p> while(j<=n){</p><p> if(j<n && a[j]<a[j+1])</p><p><b> j++;</b></p><p> if(a[k]>=a[j])break;</p
72、><p><b> tmp=a[k];</b></p><p> a[k]=a[j];</p><p> a[j]=tmp; </p><p><b> k=j;</b></p><p><b> j=2*j+1;</b></p
73、><p><b> }</b></p><p><b> }</b></p><p><b> //建立小根堆函數(shù)</b></p><p> void buildlittle(int *a,int i,int n){</p><p><b>
74、; int tmp;</b></p><p><b> k=i;</b></p><p><b> j=2*k+1;</b></p><p> while(j<=n){</p><p> if(j<n && a[j]>a[j+1])</p
75、><p><b> j++;</b></p><p> if(a[k]<=a[j])break;</p><p><b> tmp=a[k];</b></p><p> a[k]=a[j];</p><p> a[j]=tmp; </p>
76、<p><b> k=j;</b></p><p><b> j=2*j+1;</b></p><p><b> }</b></p><p><b> }</b></p><p><b> //輸出數(shù)組函數(shù)</b&g
77、t;</p><p> void prnt(int *a,int n){</p><p><b> int i;</b></p><p> printf("\n");</p><p> for(i=0;i<n;i++){</p><p> printf(&quo
78、t;%3d",a[i]);</p><p><b> }</b></p><p> printf("\n");</p><p><b> }</b></p><p><b> //輸出大根堆函數(shù)</b></p><p&g
79、t; void prnthpbig(int *a,int b1,int b2){</p><p><b> int size;</b></p><p> int h=0,sum=0,item=1;</p><p> int i,j,cnt,start,tmp;</p><p> size=b2-b1+1;<
80、;/p><p> while(sum<=size){</p><p> sum+=item;</p><p><b> h++;</b></p><p><b> item*=2;</b></p><p><b> }</b></p&g
81、t;<p><b> item=1;</b></p><p><b> cnt=0;</b></p><p><b> start=b1;</b></p><p><b> tmp=1;</b></p><p> printf(&q
82、uot;───────────────────────\n"); </p><p> printf("▼大根堆排序如下:┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈\n");</p><p><b> while(1){</b></p><p> for(i=0;i<h;i++){</p><
83、;p> for(j=0;j<h-i;j++)</p><p> printf(" ");</p><p> for(j=0;j<i+1;j++)printf(" "); </p><p> for(j=0;j<tmp;j++){</p><p> if(cnt&g
84、t;size-1)goto end;</p><p> printf("%4d",a[cnt++]);</p><p><b> }</b></p><p> printf("\n");</p><p><b> tmp*=2;</b></p&g
85、t;<p><b> } </b></p><p><b> }</b></p><p><b> end:</b></p><p> printf("\n"); </p><p> return;
86、 </p><p><b> }</b></p><p><b> //輸出小根堆函數(shù)</b></p><p> void prnthplittle(int *a,int b1,int b2){</p><p><b> int size;</b&g
87、t;</p><p> int h=0,sum=0,item=1;</p><p> int i,j,cnt,start,tmp;</p><p> size=b2-b1+1;</p><p> while(sum<=size){</p><p> sum+=item;</p><p
88、><b> h++;</b></p><p><b> item*=2;</b></p><p><b> }</b></p><p><b> item=1;</b></p><p><b> cnt=0;</b>&
89、lt;/p><p><b> start=b1;</b></p><p><b> tmp=1;</b></p><p> printf("───────────────────────\n"); </p><p> printf("▲小根堆排序如下:┈┈┈┈
90、┈┈┈┈┈┈┈┈┈┈┈\n");</p><p><b> while(1){</b></p><p> for(i=0;i<h;i++){</p><p> for(j=0;j<h-i;j++)</p><p> printf(" ");</p>&
91、lt;p> for(j=0;j<i+1;j++)printf(" "); </p><p> for(j=0;j<tmp;j++){</p><p> if(cnt>size-1)goto end;</p><p> printf("%4d",a[cnt++]);</p><
92、p><b> }</b></p><p> printf("\n");</p><p><b> tmp*=2;</b></p><p><b> } </b></p><p><b> }</b></
93、p><p><b> end:</b></p><p> printf("\n"); </p><p> return; </p><p><b> }</b></p><p> //輸出已排序數(shù)組函
94、數(shù)</p><p> void prntar(int *a,int b2,int len){</p><p><b> int i; </b></p><p> printf("○已排序序列數(shù)如下:┈┈┈┈┈┈┈┈┈┈┈┈┈┈\n");</p><p> for(i=0;i<b2;i++
95、){</p><p> printf(" ");</p><p> } </p><p> for(i=b2;i<=len;i++){</p><p> printf("%3d",a[i]);</p><p> } <
96、/p><p> printf("\n");</p><p><b> } </b></p><p><b> main(){</b></p><p> int a[50];</p><p><b> int i;</b><
97、/p><p><b> int tmp;</b></p><p><b> int sum;</b></p><p><b> int len;</b></p><p> printf("╭━━━━━━━━━━━━━━━━━━━━━━╮\n");<
98、/p><p> printf("┃─── 計本092 金強勝 0918014051 ────┃\n");</p><p> printf("┃ ┃\n");</p><p> printf("┃──────(數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
99、)──────┃\n");</p><p> printf("┃───── 內(nèi)部堆排序算法的實現(xiàn) ─────┃\n");</p><p> printf("╰──────────────────────╯\n");</p><p> printf("★請您輸入欲排序數(shù)的個數(shù),并以回車鍵結(jié)束:&qu
100、ot;);</p><p> scanf("%3d",&len);</p><p> printf("┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄\n"); </p><p> printf("★請輸入能組建堆的無序序列數(shù)的值,并以回車鍵結(jié)束:\n ");</p><
101、p> for(i=0;i<len;i++)</p><p> scanf("%3d",&a[i]); </p><p> tmp=1;sum=0;</p><p> while(sum+tmp<=len){</p><p> sum+=tmp; </p>
102、<p><b> tmp*=2;</b></p><p><b> } </b></p><p> for(i=sum-1;i>=0;i--)</p><p> buildbig(a,i,len-1); </p><p> prnthpbig(a,0,
103、len-1); </p><p><b> //改建堆</b></p><p> for(i=0;i<len-1;i++){</p><p><b> tmp=a[0];</b></p><p> a[0]=a[len-1-i];</p><p> a[len
104、-1-i]=tmp;</p><p> buildbig(a,0,len-2-i);</p><p> prnthpbig(a,0,len-2-i);</p><p> prntar(a,len-1-i,len-1); </p><p><b> }</b></p><p>
105、 printf("\n───────────────────────\n");</p><p> printf("★大根堆排序的最后結(jié)果如下:┈┈┈┈┈┈┈┈┈┈\n"); </p><p> prnt(a,len);</p><p> printf("\n···&
106、#183;····················\n\n");</p><p> for(i=sum-1;i>=0;i--)</p><p> buildlittle(a
107、,i,len-1);</p><p> prnthplittle(a,0,len-1);</p><p><b> //改建堆</b></p><p> for(i=0;i<len-1;i++){</p><p><b> tmp=a[0];</b></p><p&
108、gt; a[0]=a[len-1-i];</p><p> a[len-1-i]=tmp;</p><p> buildlittle(a,0,len-2-i);</p><p> prnthplittle(a,0,len-2-i);</p><p> prntar(a,len-1-i,len-1); </p>
109、;<p><b> }</b></p><p> printf("\n───────────────────────\n");</p><p> printf("★小根堆排序的最后結(jié)果如下:┈┈┈┈┈┈┈┈┈┈\n"); </p><p> prnt(a,len);&l
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- c歸并排序與堆排序的課程設(shè)計
- 排序算法數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書
- 排序算法數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書
- 課程設(shè)計說明書
- 課程設(shè)計說明書
- 前門課程設(shè)計說明書
- javaweb課程設(shè)計說明書
- 后蓋課程設(shè)計說明書
- 鍋爐課程設(shè)計說明書
- 空調(diào)課程設(shè)計說明書
- 蝸輪課程設(shè)計說明書
- 采礦課程設(shè)計說明書
- 機床課程設(shè)計說明書
- caxa課程設(shè)計說明書
- 化工課程設(shè)計說明書
- vb課程設(shè)計說明書
- 課程設(shè)計說明書.doc
- 課程設(shè)計說明書.doc
- 課程設(shè)計說明書.doc
- 課程設(shè)計說明書.doc
評論
0/150
提交評論