作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4096079.html
使用优先队列实现,需要注意以下几点:
1.在使用priority_queue时,内部需要存储哈夫曼树节点的指针,而不能是节点。因为构建哈夫曼树时,需要把其左右指针指向孩子,而如果储存的是节点,那么孩子的地址是会改变的。同理节点应当使用new在内存中开辟,而不能使用vector,原因是vector在数组大小为2整数次幂时,大小会倍增,开辟新数组并把老数组的数字copy过去,从而也会导致地址变化。
2.优先队列对指针的排列,需要额外写一个比较函数来比较指针指向的节点的大小。bool operator () (wcnode * node1, wcnode * node2) return node1->lessthan(node2);并在定义优先队列时使用这种方法: priority_queue <wcnode*, vector<wcnode*>, compare> 第一个参数是节点类型,第二个参数是优先队列的储存结构,第三个参数是比较函数。
3.C++在写入文件时,由于只能按字节写入,因此需要把8个bit位转化为一个字节,最后不足8位用0补齐,并记录文件总bit数,便于解码。然后写入文件。另写入二进制文件可以使用ofstream out(“output.txt”,std::ofstream::binary);
4.哈夫曼编码信息包括每种字符的映射,和该文件的总bit数。
其代码如下:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <fstream>
#include <queue>
#include <map>
#include <vector>
using namespace std;
class compare; class wcnode
{
public:
friend class compare;
char word;
int count;
wcnode* left;
wcnode* right;
bool lessthan (const wcnode *w)const
{
return count > w->count;
}
wcnode(char w='\0', int c=, wcnode* l=NULL, wcnode * r=NULL)
{
word = w; count = c; left = l; right = r;
}
}; class compare
{
public:
bool operator () (wcnode * node1, wcnode * node2)
{
return node1->lessthan(node2);
}
}; void preorder(wcnode *head, vector<bool> rec, map<char, vector<bool> > & res)
{
if( head->left == NULL && head->right == NULL )
{
res[head->word] = rec;
return;
}
vector<bool> l = rec;
l.push_back();
vector<bool> r = rec;
r.push_back();
if(head->left != NULL) preorder(head->left, l, res);
if(head->right != NULL) preorder(head->right, r, res);
}
map<char, vector<bool> > encode(map<char, int> &wordcount)
{
map<char, vector<bool> > res;
priority_queue <wcnode*, vector<wcnode*>, compare> pq;
map<char, int>::iterator t;
wcnode *tmp;
wcnode *t1, *t2, *t3; for( t = wordcount.begin() ; t != wordcount.end() ; t++ )
{
tmp = new wcnode();
tmp->word = t->first;
tmp->count = t->second;
pq.push(tmp);
}
while( pq.size() > )
{
t1 = pq.top();
pq.pop();
t2 = pq.top();
pq.pop();
t3 = new wcnode();
t3->count = t1->count + t2->count;
t3->left = t1;
t3->right = t2;
pq.push(t3);
}
wcnode *huffmanhead = pq.top();
vector<bool> rec;
preorder(huffmanhead, rec, res);
map<char, vector<bool> >::iterator it;
for( it = res.begin() ; it != res.end() ; it++ )
{
cout<<it->first<<":";
for( int i = ; i < it->second.size() ; i++ )
{
cout<<it->second[i];
}
cout<<", ";
}
return res;
} void output(string s, string passage, map<char, vector<bool> > res)
{
ofstream out(s.c_str());
vector<bool> bit;
for( int i = ; i < passage.size() ; i++ )
{
vector<bool> tmp = res[passage[i]];
for( int i = ; i < tmp.size(); i++ )
{
bit.push_back(tmp[i]);
}
}
char outputchar = ;
for( int i = ; i < bit.size() ; i++ )
{
if( i % == )
{
out.write(&outputchar, sizeof(outputchar));
outputchar = ;
}
outputchar = outputchar + bit[i];
outputchar = outputchar * ;
}
if( outputchar != )
{
out.write(&outputchar, sizeof(outputchar));
}
out.close();
}
int main(int argc, char *argv[])
{
char tmp;
ifstream in("Aesop_Fables.txt");
map <char, int> wordcount;
map <char, vector<bool> > res;
string passage;
while( in.get(tmp) )
{
passage += tmp;
if( wordcount.count(tmp) == )
{
wordcount[tmp] = ;
}
else
{
wordcount[tmp]++;
}
}
res = encode(wordcount);
output("outAesop.txt", passage, res);
in.close();
}