2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩24頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論