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

北方的穷人4

北方的穷人4

2016-02-19 12:23

下面,图老师小编带您去了解一下利用C++实现哈夫曼算法,生活就是不断的发现新事物,get新技能~
我想每个计算机专业的学生或多或少都接触过哈夫曼编码,数据结构中的老问题了。大体就是给出一些字符,和这些字符的出现频率,让你为这些字符设计一个二进制编码,要求频率最高的字符的编码最短。解决的方法是构造一棵哈夫曼树(二叉树),其基本思路是,每次从这些字符中挑出两个频率最低的,然后构造一个新的结点,使新结点的左右孩子指针分别指向那两个节点。我想这个大家都很清楚了,我就不多说了。主要讲下这次我用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_queuehNode 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_queuehNode* 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_queuehNode*,vectorhNode*,phNodeComp pq;
  终于把这个问题给解决了。看样子仅从书本上获得的知识是不牢靠的,一定要自己实践了才会有真正的认识。
展开更多 50%)
分享

猜你喜欢

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

编程语言 网络编程
利用C++实现哈夫曼算法

简单快速的哈夫曼编码

C语言教程 C语言函数
简单快速的哈夫曼编码

s8lol主宰符文怎么配

英雄联盟 网络游戏
s8lol主宰符文怎么配

实现LZARI压缩算法的C++类

C语言教程 C语言函数
实现LZARI压缩算法的C++类

数据结构:哈夫曼树的应用

编程语言 网络编程
数据结构:哈夫曼树的应用

lol偷钱流符文搭配推荐

英雄联盟 网络游戏
lol偷钱流符文搭配推荐

数据结构算法集---C++语言实现

编程语言 网络编程
数据结构算法集---C++语言实现

如何用Java实现啥夫曼编码

编程语言 网络编程
如何用Java实现啥夫曼编码

lolAD刺客新符文搭配推荐

英雄联盟
lolAD刺客新符文搭配推荐

到底是什么反射泛型委托泛型

到底是什么反射泛型委托泛型

onmousewheel event 缩放图片效果

onmousewheel event 缩放图片效果
下拉加载更多内容 ↓