STL实现哈夫曼算法
算法 实现 STL 哈夫曼
2023-09-27 14:27:55 时间
用C++ std::priority_queue 实现哈夫曼算法我想每个计算机专业的学生或多或少都接触过哈夫曼编码,数据结构中的老问题了。大体就是给出一些字符,和这些字符的出现频率,让你为这些字符设计一个二进制编码,要求频率最高的字符的编码最短。
用C++ std::priority_queue 实现哈夫曼算法我想每个计算机专业的学生或多或少都接触过哈夫曼编码,数据结构中的老问题了。大体就是给出一些字符,和这些字符的出现频率,让你为这些字符设计一个二进制编码,要求频率最高的字符的编码最短。解决的方法是构造一棵哈夫曼树(二叉树),其基本思路是,每次从这些字符中挑出两个频率最低的,然后构造一个新的结点,使新结点的左右孩子指针分别指向那两个节点。我想这个大家都很清楚了,我就不多说了。主要讲下这次我用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
.....
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的指针,就不会出现这个问题了,于是改写成:
然而马上遭遇了第二个问题。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
终于把这个问题给解决了。看样子仅从书本上获得的知识是不牢靠的,一定要自己实践了才会有真正的认识。
posted on 2004-03-19 19:47 Justin Shen 评论(6) 编辑 收藏
Comments
# re: 用C++ std::priority_queue 实现哈夫曼算法
earthharp
只有成树
没有编码解码吗?
我觉得用BucketSort还要优秀一些
注意你的空间是否正确回收
Posted @ 2004-03-20 01:06
# re: 用C++ std::priority_queue 实现哈夫曼算法
Justin Shen
目前只做到把每个字符的编码打印出来,因为老师只要求到这点,实际做哈夫曼编码还是会有一点问题。空间回收在遍历哈夫曼树的过程中一起完成了。
vector int
void DoPrint(hNode* r)
{
if (r- left ==NULL r- right == NULL)
{
cout r- data ": ";
for (int i = 0;i v.size();++i)
cout v;
cout endl;
v.pop_back();
delete r;
return ;
}
if (r- left)
{
v.push_back(0);
DoPrint(r- left);
}
if (r- right)
{
v.push_back(1);
DoPrint(r- right);
}
v.pop_back();
}
用C++ std::priority_queue 实现哈夫曼算法我想每个计算机专业的学生或多或少都接触过哈夫曼编码,数据结构中的老问题了。大体就是给出一些字符,和这些字符的出现频率,让你为这些字符设计一个二进制编码,要求频率最高的字符的编码最短。解决的方法是构造一棵哈夫曼树(二叉树),其基本思路是,每次从这些字符中挑出两个频率最低的,然后构造一个新的结点,使新结点的左右孩子指针分别指向那两个节点。我想这个大家都很清楚了,我就不多说了。主要讲下这次我用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
.....
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的指针,就不会出现这个问题了,于是改写成:
然而马上遭遇了第二个问题。std::priority_queue在判断优先关系的时候,直接比较指针的地址,而不是指针指向的对象的大小关系。而指针不是类,我没办法重写指针的比较操作。程序陷入了困境之中。std::priority_queue默认使用Greater 模板来生成一个function object来对元素进行比较,我试图为Greater 写一个hNode*的特化版本来改变优先队列对hNode*的比较,然而也没有成功。山重水复疑无路之时,突然想到为什么不直接为优先队列写一个function object来替代Greater 不就可以了吗?赶快写下如下代码:
![None.gif](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![ExpandedBlockStart.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockStart.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockEnd.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
![ExpandedBlockEnd.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
然后把std::priority_queue的申明变为:
priority_queue hNode*,vector hNode* ,phNodeComp
终于把这个问题给解决了。看样子仅从书本上获得的知识是不牢靠的,一定要自己实践了才会有真正的认识。
posted on 2004-03-19 19:47 Justin Shen 评论(6) 编辑 收藏
Comments
# re: 用C++ std::priority_queue 实现哈夫曼算法
earthharp
只有成树
没有编码解码吗?
我觉得用BucketSort还要优秀一些
注意你的空间是否正确回收
Posted @ 2004-03-20 01:06
# re: 用C++ std::priority_queue 实现哈夫曼算法
Justin Shen
目前只做到把每个字符的编码打印出来,因为老师只要求到这点,实际做哈夫曼编码还是会有一点问题。空间回收在遍历哈夫曼树的过程中一起完成了。
![None.gif](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![None.gif](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![ExpandedBlockStart.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockStart.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockEnd.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockStart.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockEnd.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockStart.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedSubBlockEnd.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
![InBlock.gif](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![ExpandedBlockEnd.gif](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
相关文章
- Python opencv图像处理基础总结(七) 基于分水岭算法的图像分割
- Dijkstra算法优先队列实现与Bellman_Ford队列实现的理解
- 自然语言处理(NLP)-第三方库(工具包):CRF++【通用领域命名实体识别库】【CRF++是CRF算法的一个实现】【在专业领域(电商、医药等)中的效果不好】
- 【状态估计】将变压器和LSTM与卡尔曼滤波器结合到EM算法中进行状态估计(Python代码实现)
- 基于蚁群算法的车辆路径规划问题的研究(Matlab代码实现)
- Apriori算法介绍(Python实现)
- 【大厂算法系列】编码手写顺序表相关功能,线性结构核心知识点详细剖析
- 多边形填充算法之扫描线填充算法
- 从局部信息推测基恩士的Removing BackGround Information算法的实现。
- 【算法随记三】小半径中值模糊的急速实现(16MB图7.5ms实现) + Photoshop中蒙尘和划痕算法解读。
- <<一种基于δ函数的图象边缘检测算法>>一文算法的实现。
- 双指数边缘平滑滤波器用于磨皮算法的尝试。
- 常见负载均衡算法Java代码实现
- 【BZOJ】3289: Mato的文件管理(莫队算法+树状数组)
- PHP 实现 一致性哈希 算法(转的)
- HDU 4638 Group 【树状数组,分块乱搞(莫队算法?)】
- 【算法】SMO
- 《算法技术手册》一3.5.3 使用环境
- 一遍记住 8 种排序算法与 Java 代码实现
- C++基础代码--20余种数据结构和算法的实现
- 基于自适应模拟退火算法优化Eggholder函数,测试函数的100种求解方法之16
- bayer格式插值算法实现
- 排序算法基本介绍及python实现(含详细注释)
- PHP排序算法之选择排序
- KNN算法
- Cocos2d-x 地图行走的实现3:A*算法
- verilog图像算法实现和仿真(并行处理方法)
- 七大查找算法(附C语言代码实现)
- RGBA alpha 透明度混合算法(转)
- 挑战性题目DSCT401:全源最短路径Floyd算法的并行实现