程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 利用C++實現哈夫曼算法

利用C++實現哈夫曼算法

編輯:C++入門知識
我想每個計算機專業的學生或多或少都接觸過哈夫曼編碼,數據結構中的老問題了。大體就是給出一些字符,和這些字符的出現頻率,讓你為這些字符設計一個二進制編碼,要求頻率最高的字符的編碼最短。解決的方法是構造一棵哈夫曼樹(二叉樹),其基本思路是,每次從這些字符中挑出兩個頻率最低的,然後構造一個新的結點,使新結點的左右孩子指針分別指向那兩個節點。我想這個大家都很清楚了,我就不多說了。主要講下這次我用C++實現時遇到的問題。首先,我定義了一個哈夫曼樹結點:

class hNode
{
 public:
  friend bool operator > (hNode n1,hNode n2); //定義了大於符號,供優先隊列排列使用
  hNode(string d="",int i=0,hNode* l = NULL,hNode* r =NULL):left(l),right(r),data(d),value(i){}
  hNode* left;
  hNode* right;
  string data; //儲存的字符串
  int value; //字符串出現的次數
};

bool operator >(hNode n1,hNode n2)
{
 return n1.value > n2.value;
}
  因為只是算法課的小作業,所以我也不准備為hNode定義完整的二叉樹操作,僅僅只是存放數據的對象,所以只有一個構造函數,並且所有的data member都是公有的。

  這此寫這個算法會遇到大麻煩,主要因為是用了std::priority_queue容器。當時考慮到在哈夫曼中要每次挑選兩個頻率最小(即出現次數最小,我那個hNode裡的value是出現的次數),很自然的就想到了std::priority_queue容器,優先隊列每次都會彈出隊列中權值最高的元素,這個特性無疑是實現哈夫曼算法的最佳選擇。然而因為第一次用std::priority_queue容器,結果出了不少問題,好在最後都一一解決,也學到了不少東西。

  初步的設想是這樣的,先把所有的hNode對象都壓入優先隊列中去,然後每次彈出兩個,組成一個新的結點,再把新的結點壓入隊列,重復這一步驟,當隊列中只有一個元素時,哈夫曼樹也就完成了。像這樣:(是錯的,可別學)

while(...)
{
 std::priority_queue<hNode> q;
 .....
 hNode h1 = q.top();
 q.pop();
 hNode h2 = q.top();
 q.pop();
 hNode r;
 r.left = h1;
 r.right = h2;
 r.value = h1.value + h2.value;
 q.push(r);
}
  然而遭遇的第一個問題是,STL的所有容器的的插入都是基於by value語義的,也就是要生成一個對象的副本放在容器中。這樣的後果就是hNode的left,right指針都指到不知道什麼地方去了。大家可以稍微畫幾個圖試一下,就知道出了什麼問題了。考慮一下後,發現如果隊列裡存放hNode的指針,就不會出現這個問題了,於是改寫成:

hNode* makeTree(priority_queue<hNode*> pq)
{
 hNode* p1 = NULL;
 hNode* p2 = NULL;
 hNode* r = NULL;
 while( !pq.empty())
 {
  p1 = pq.top();
  pq.pop();
  if (pq.empty())
  {
   r = p1;
   return r;
  }
  p2 = pq.top();
  pq.pop();
  r =new hNode;
  r->left = p1;
  r->right = p2;
  r->value = p1->value +p2->value;
  pq.push(r);
 }
 return NULL;
}
  然而馬上遭遇了第二個問題。std::priority_queue在判斷優先關系的時候,直接比較指針的地址,而不是指針指向的對象的大小關系。而指針不是類,我沒辦法重寫指針的比較操作。程序陷入了困境之中。std::priority_queue默認使用Greater<>模板來生成一個function object來對元素進行比較,我試圖為Greater<>寫一個hNode*的特化版本來改變優先隊列對hNode*的比較,然而也沒有成功。山重水復疑無路之時,突然想到為什麼不直接為優先隊列寫一個function object來替代Greater<>不就可以了嗎?趕快寫下如下代碼:

struct phNodeComp
{
 bool operator () (const hNode*& left,const hNode*& right) const
 {
  return left->value > right->value;
 }
};
  然後把std::priority_queue的申明變為:

priority_queue<hNode*,vector<hNode*>,phNodeComp > pq;
  終於把這個問題給解決了。看樣子僅從書本上獲得的知識是不牢靠的,一定要自己實踐了才會有真正的認識。
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved