我想每个计算机专业的学生或多或少都接触过哈夫曼编码,数据结构中的老问题了。大体就是给出一些字符,和这些字符的出现频率,让你为这些字符设计一个二进制编码,要求频率最高的字符的编码最短。解决的方法是构造一棵哈夫曼树(二叉树),其基本思路是,每次从这些字符中挑出两个频率最低的,然后构造一个新的结点,使新结点的左右孩子指针分别指向那两个节点。我想这个大家都很清楚了,我就不多说了。主要讲下这次我用C++实现时遇到的问题。首先,我定义了一个哈夫曼树结点: class hNode 仅仅只是存放数据的对象,所以只有一个构造函数,并且所有的data member都是公有的。 初步的设想是这样的,先把所有的hNode对象都压入优先队列中去,然后每次弹出两个,组成一个新的结点,再把新的结点压入队列,重复这一步骤,当队列中只有一个元素时,哈夫曼树也就完成了。像这样:(是错的,可别学) while(...) 然而遭遇的第一个问题是,STL的所有容器的的插入都是基于by value语义的,也就是要生成一个对象的副本放在容器中。这样的后果就是hNode的left,right指针都指到不知道什么地方去了。大家可以稍微画几个图试一下,就知道出了什么问题了。考虑一下后,发现如果队列里存放hNode的指针,就不会出现这个问题了,于是改写成: hNode* makeTree(priority_queue<hNode*> pq) 然而马上遭遇了第二个问题。std::priority_queue在判断优先关系的时候,直接比较指针的地址,而不是指针指向的对象的大小关系。而指针不是类,我没办法重写指针的比较操作。程序陷入了困境之中。std::priority_queue默认使用Greater<>模板来生成一个function object来对元素进行比较,我试图为Greater<>写一个hNode*的特化版本来改变优先队列对hNode*的比较,然而也没有成功。山重水复疑无路之时,突然想到为什么不直接为优先队列写一个function object来替代Greater<>不就可以了吗?赶快写下如下代码: struct phNodeComp 然后把std::priority_queue的申明变为: priority_queue<hNode*,vector<hNode*>,phNodeComp > pq; 终于把这个问题给解决了。看样子仅从书本上获得的知识是不牢靠的,一定要自己实践了才会有真正的认识。 |
|
来自: 千锋Python学堂 > 《程序员经验分享》