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

數據結構考研分類復習真題 第六章 答案 (五)[50]

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

  .()哈夫曼樹的構造過程

  ① 根據給定的n個權值{WWWWn}構成n棵二叉樹的集合F={TTTn}其中每棵二叉樹Ti只有權值為Wi的根結點其左右子樹均為空

  ② 在F中選取兩棵根結點的權值最小的樹作左右子樹構造一棵新二叉樹新二叉樹根結點的權值為其左右子樹上根結點的權值之和

  ③ 在F中刪除這兩棵樹同時將新得到的二叉樹加入F中

  ④ 重復②和③直到F中只剩一棵樹為止這棵樹便是哈夫曼樹

  ()含有n個葉子結點的哈夫曼樹共有n個結點采用靜態鏈表作為存儲結構設置大小為n的數組現將哈夫曼樹的結點及樹的結構定義如下

  typedef struct{float weight ;   //權值
  int parentlcrc;//雙親右子女 }node ;
  typedef node HufmTree[*n];
  void Huffman(int nfloat w[n]HufmTree T)
  //構造n個葉子結點的哈夫曼樹Tn個權值己放在W[n]數組中
  {int ijpp         //pp為最小值和次最小值的坐標
  float smallsmall;   //small和small為權值的最小值和次小值
  for(i=;i<*n;i++)   //置初值結點的權右子女雙親
  {T[i]parent=; T[i]lc=; T[i]rc=;
  if(i<n) T[i]weight=w[i]; else T[i]weight=;
  }
  for (i=n ;i<*n;i++)         //構造新二叉樹
  {p=p=;small=small=maxint; //初值
  for(j=;j<i;j++)
  if(T[j]weight<small && T[j]parent==)           //最小值
  {p=p; small=small; p=j; small=T[j]weight;}
  else if(T[j]weight<small && T[j]parent==)       //次小值
  {p=j;small=T[j]weight;}
  T[i]weight=T[p]weight+T[p]weight;              //合並成一棵新二叉樹
  T[i]lc=p; T[i]rc=p;                             //置雙親的左右子女
  T[p]parent=i; T[p]parent=i;                     //置左右子女的雙親
  }//for(i=;i<*n;i++) }//結束huffman

  求哈夫曼編碼的算法

  typedef struct {char bit[n]; int start;}codetype;
  void HuffmanCode(CodeType code[n]HufmTree T) //哈夫曼樹T已求出現求其哈夫曼編碼
  {int ijcp;
  CodeType cd;
  for(i=;i<n;i++)
  {cdstart=n;c=i;p=T[i]parent;
  while(p!=)
  {cdstart;
  if(T[p]lc==c) cdbit[cdstart]=//左分枝生成代碼
  else cdbit[cdstart]=;         // 右分枝生成代碼
  c=p; p=T[p]parent;                  //雙親變為新子女再求雙親的雙親
  }
  code[i]=cd;        //成組賦值求出一個葉子結點的哈夫曼編碼
  }//for    }//結束HuffmanCode

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

推薦文章
Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.