c++中怎么實現(xiàn)一個哈希慢算法

c++中怎么實現(xiàn)一個哈希慢算法，相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

首先，我定義了一個哈夫曼樹結(jié)點：

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

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

while(...)
{
　std::priority_queue<hNode> q;
　.....
　hNode h2 = q.top();
　q.pop();
　hNode h3 = q.top();
　q.pop();
　hNode r;
　r.left = h2;
　r.right = h3;
　r.value = h2.value + h3.value;
}

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

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在判斷優(yōu)先關(guān)系的時候，直接比較指針的地址，而不是指針指向的對象的大小關(guān)系。而指針不是類，我沒辦法重寫指針的比較操作。程序陷入了困境之中。std::priority_queue默認使用Greater<>模板來生成一個function object來對元素進行比較，我試圖為Greater<>寫一個hNode*的特化版本來改變優(yōu)先隊列對hNode*的比較，然而也沒有成功。山重水復(fù)疑無路之時，突然想到為什么不直接為優(yōu)先隊列寫一個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;

看完上述內(nèi)容，你們掌握c++中怎么實現(xiàn)一個哈希慢算法的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！