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

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

2013-11-15 15:17:24  來源: 數據結構 

   typedef struct
  { int num; float score; }RecType;
  void SelectSort(RecType R[]int n)
  { for(i=; i<n; i++)
  { //選擇第i大的記錄並交換到位
  k=i;       //假定第i個元素的關鍵字最大
  for(j=i+;j<=n;j++)     //找最大元素的下標
  if(R[j]score>R[k]score)  k=j;
  if(i!=k)  R[i] <>R[k];  //與第i個記錄交換
  }//for
  for(i=; i<=n; i++) //輸出成績
  { printf(%d%fR[i]numR[i]score); if(i%==) printf(\n);}
  }//SelectSort

   typedef struct
  { int key; datatype info}RecType
  void CountSort(RecType a[]b[]int n) //計數排序算法將a中記錄排序放入b中
  { for(i=;i<n;i++) //對每一個元素
  { for(j=cnt=;j<n;j++)
  if(a[j]key<a[i]key) cnt++; //統計關鍵字比它小的元素個數
  b[cnt]=a[i];
  }
  }//Count_Sort

  () 對於有n個記錄的表關鍵碼比較n

  () 簡單選擇排序算法比本算法好簡單選擇排序比較次數是n(n)/且只用一個交換記錄的空間而這種方法比較次數是n且需要另一數組空間

  [算法討論]因題目要求針對表中的每個記錄掃描待排序的表一趟所以比較次數是n若限制對任意兩個記錄之間應該只進行一次比較則可把以上算法中的比較語句改為

  for(i=;i<n;i++) a[i]count=;//各元素再增加一個計數域初始化為
  for(i=;i<n;i++)
  for(j=i+;j<n;j++)
  if(a[i]key<a[j]key) a[j]count++; else a[i]count++;

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


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