熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第五章 答案[44]

2013-11-15 15:11:46  來源: 數據結構 

  )在n個正整數中選出k(k<<m)個最大的數應使用堆排序方法對深度為h的堆篩選算法中關鍵字的比較次數至多為(h)次建堆總共進行的關鍵字比較次數不超過n堆排序在最壞情況下的時間復雜度是O(nlogn)

  int r[]; // r[]是整型數組

  ()void sift(int r[]int kmtag)
  //已知r[k+m]是堆本算法將r[km]調整成堆tag=建立大根堆tag=建立小根堆
  {i=k;j=*i;x=r[k];
  while (j<=m)
  {if (tag==)  //建立小根堆
  {if (j<m && r[j]>r[j+]) j++;//沿關鍵字小的方向篩選
  if(r[j]<x)) {r[i]=r[j];i=j;j=*i;}
  else break;}
  else  //建立大根堆
  {if (j<m && r[j]<r[j+]) j++;//沿關鍵字小的方向篩選
  if(r[j]>x) {r[i]=r[j];i=j;j=*i;}
  else break;}
  }
  r[i]=x;
  }//sift
  main(int argcchar *argv[])
  //根據命令行中的輸入個數中選取n個最大數或n個最小數
  {int m=ij;
  n=augv[];    //從命令行輸入的第二個參數是需要輸出的數的個數
  if(n>m){printf(參數錯誤\n);exit();}
  for(i=;i<m;i++) scanf(%d&r[i]); //輸入個大小不同的正整數
  if (augv[]==a)    //輸出n個最大數要求建立大根堆
  {for(i=m/;i>;i) sift(rim)
  printf(%d個最大數依次為\nn);
  for(i=m;i>mn+;i)  //輸出n個最大數
  {printf(%dr[i]);  j++; if((j+)%==) printf(\n);//一行打印個數
  sift(ri); } //調堆
  }
  else //(augv[]==i)    //輸出n個最小數要求建立小根堆
  {for(i=m/;i>;i) sift(rim)
  printf(%d個最小數依次為\nn);
  for(i=m;i>mn+;i)  //輸出n個最小數
  {printf(%dr[i]);  j++; if((j+)%==) printf(\n);//一行打印個數
  sift(ri); } //調堆
  }
  }//main

  [算法討論]算法討論了建堆並輸出n(n小於等於m)個最大(小)數的情況由於要求輸出n個最大數或最小數必須建立極大化堆和極小化堆注意輸出時的for循環控制到變量i從m變化到mn+這是堆的性質決定的只有堆頂元素才是最大(小)的要避免使i從到n來輸出n個最大(小)數的錯誤

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23026.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.