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

2019-11-17 05:09:58

字體：大中小

來源：轉載

供稿：網友

　　我想每個計算機專業的學生或多或少都接觸過哈夫曼編碼，數據結構中的老問題了。大體就是給出一些字符，和這些字符的出現頻率，讓你為這些字符設計一個二進制編碼，要求頻率最高的字符的編碼最短。解決的方法是構造一棵哈夫曼樹（二叉樹），其基本思路是，每次從這些字符中挑出兩個頻率最低的，然后構造一個新的結點，使新結點的左右孩子指針分別指向那兩個節點。我想這個大家都很清楚了，我就不多說了。主要講下這次我用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;
　　終于把這個問題給解決了。
看樣子僅從書本上獲得的知識是不牢靠的，一定要自己實踐了才會有真正的熟悉。