我想每個(gè)計(jì)算機(jī)專業(yè)的學(xué)生或多或少都接觸過哈夫曼編碼，數(shù)據(jù)結(jié)構(gòu)中的老問題了。大體就是給出一些字符，和這些字符的出現(xiàn)頻率，讓你為這些字符設(shè)計(jì)一個(gè)二進(jìn)制編碼，要求頻率最高的字符的編碼最短。解決的方法是構(gòu)造一棵哈夫曼樹（二叉樹），其基本思路是，每次從這些字符中挑出兩個(gè)頻率最低的，然后構(gòu)造一個(gè)新的結(jié)點(diǎn)，使新結(jié)點(diǎn)的左右孩子指針分別指向那兩個(gè)節(jié)點(diǎn)。我想這個(gè)大家都很清楚了，我就不多說了。主要講下這次我用C++實(shí)現(xiàn)時(shí)遇到的問題。首先，我定義了一個(gè)哈夫曼樹結(jié)點(diǎn)：

class hNode
{
　public:
　　friend bool operator > (hNode n1,hNode n2);　//定義了大于符號(hào)，供優(yōu)先隊(duì)列排列使用
　　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; //儲(chǔ)存的字符串
　　int value; //字符串出現(xiàn)的次數(shù)
};

bool operator >(hNode n1,hNode n2)
{
　return n1.value > n2.value;
}

僅僅只是存放數(shù)據(jù)的對(duì)象，所以只有一個(gè)構(gòu)造函數(shù)，并且所有的data member都是公有的。
　　這此寫這個(gè)算法會(huì)遇到大麻煩，主要因?yàn)槭怯昧藄td::priority_queue容器。當(dāng)時(shí)考慮到在哈夫曼中要每次挑選兩個(gè)頻率最?。闯霈F(xiàn)次數(shù)最小，我那個(gè)hNode里的value是出現(xiàn)的次數(shù)），很自然的就想到了std::priority_queue容器，優(yōu)先隊(duì)列每次都會(huì)彈出隊(duì)列中權(quán)值最高的元素，這個(gè)特性無疑是實(shí)現(xiàn)哈夫曼算法的最佳選擇。然而因?yàn)榈谝淮斡胹td::priority_queue容器，結(jié)果出了不少問題，好在最后都一一解決，也學(xué)到了不少東西。

　　初步的設(shè)想是這樣的，先把所有的hNode對(duì)象都?jí)喝雰?yōu)先隊(duì)列中去，然后每次彈出兩個(gè)，組成一個(gè)新的結(jié)點(diǎn)，再把新的結(jié)點(diǎn)壓入隊(duì)列，重復(fù)這一步驟，當(dāng)隊(duì)列中只有一個(gè)元素時(shí)，哈夫曼樹也就完成了。像這樣：（是錯(cuò)的，可別學(xué)）

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;
}

然而遭遇的第一個(gè)問題是，STL的所有容器的的插入都是基于by value語義的，也就是要生成一個(gè)對(duì)象的副本放在容器中。這樣的后果就是hNode的left,right指針都指到不知道什么地方去了。大家可以稍微畫幾個(gè)圖試一下，就知道出了什么問題了。考慮一下后，發(fā)現(xiàn)如果隊(duì)列里存放hNode的指針，就不會(huì)出現(xiàn)這個(gè)問題了，于是改寫成：

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;
}

然而馬上遭遇了第二個(gè)問題。std::priority_queue在判斷優(yōu)先關(guān)系的時(shí)候，直接比較指針的地址，而不是指針指向的對(duì)象的大小關(guān)系。而指針不是類，我沒辦法重寫指針的比較操作。程序陷入了困境之中。std::priority_queue默認(rèn)使用Greater<>模板來生成一個(gè)function object來對(duì)元素進(jìn)行比較，我試圖為Greater<>寫一個(gè)hNode*的特化版本來改變優(yōu)先隊(duì)列對(duì)hNode*的比較，然而也沒有成功。山重水復(fù)疑無路之時(shí)，突然想到為什么不直接為優(yōu)先隊(duì)列寫一個(gè)function object來替代Greater<>不就可以了嗎？趕快寫下如下代碼：

struct phNodeComp
{
　bool operator () (const hNode*& left,const hNode*& right) const
　{
　　return left->value > right->value;
　}
};

然后把std::priority_queue的申明變?yōu)椋?/p>

priority_queue<hNode*,vector<hNode*>,phNodeComp > pq;

終于把這個(gè)問題給解決了。看樣子僅從書本上獲得的知識(shí)是不牢靠的，一定要自己實(shí)踐了才會(huì)有真正的認(rèn)識(shí)。