分享
 
 
 

利用C++实现哈夫曼算法

王朝c/c++·作者佚名  2006-01-06
窄屏简体版  字體: |||超大  

我想每个计算机专业的学生或多或少都接触过哈夫曼编码,数据结构中的老问题了。大体就是给出一些字符,和这些字符的出现频率,让你为这些字符设计一个二进制编码,要求频率最高的字符的编码最短。解决的方法是构造一棵哈夫曼树(二叉树),其基本思路是,每次从这些字符中挑出两个频率最低的,然后构造一个新的结点,使新结点的左右孩子指针分别指向那两个节点。我想这个大家都很清楚了,我就不多说了。主要讲下这次我用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;

终于把这个问题给解决了。

看样子仅从书本上获得的知识是不牢靠的,一定要自己实践了才会有真正的熟悉。

更多内容请看C/C++技术专题专题,或

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有