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对象都压入优先队列中去,然后每次弹出两个,组成一个新的结点,再把新的结点压入队列,重复这一步骤,当队列中只有一个元素时,哈夫曼树也就完成了。像这样:(是错的,可别学)
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指针都指到不知道什么地方去了。大家可以稍微画几个图试一下,就知道出了什么问题了。考虑一下后,发现如果队列里存放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;
看完上述内容,你们掌握c++中怎么实现一个哈希慢算法的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:http://blog.itpub.net/69923331/viewspace-2669260/