電子發(fā)燒友App
哈夫曼算法實現(xiàn)
實現(xiàn)的時候我們用vector《bool》記錄每個char的編碼；用map《char，vector《bool》》表示整個字典；
就得到了下面的代碼（下面有兩個，一對一錯）：
先放出來這個錯的，以示警戒：
［cpp］ view plain copy/************************************************************************/
/* File Name： Huffman.cpp
* @Function： Lossless Compression
@Author： Sophia Zhang
@Create Time： 2012-9-26 10:40
@Last Modify： 2012-9-26 11:10
*/
/************************************************************************/
#include“iostream”
#include “queue”
#include “map”
#include “string”
#include “iterator”
#include “vector”
#include “algorithm”
using namespace std;
#define NChar 8 //suppose use at most 8 bits to describe all symbols
#define Nsymbols 1《《NChar //can describe 256 symbols totally （include a-z， A-Z）
typedef vector《bool》 Huff_code;//8 bit code of one char
map《char，Huff_code》 Huff_Dic; //huffman coding dictionary
class HTree
{
public ：
HTree* left;
HTree* right;
char ch;
int weight;
HTree（）{left = right = NULL; weight=0;}
HTree（HTree* l，HTree* r，int w，char c）{left = l; right = r; weight=w; ch=c;}
~HTree（）{delete left; delete right;}
int Getweight（）{return weight？weight:left-》weight+right-》weight;}
bool Isleaf（）{return ！left && ！right; }
bool operator 《 （const HTree tr） const
{
return tr.weight 《 weight;
}
};
HTree* BuildTree（int *frequency）
{
priority_queue《HTree*》 QTree;
for （int i=0;i《Nsymbols;i++）
{
if（frequency［i］）
QTree.push（new HTree（NULL，NULL，frequency［i］，（char）i））;
}
//build
while （QTree.size（）》1）
{
HTree* lc = QTree.top（）;
QTree.pop（）;
HTree* rc = QTree.top（）;
QTree.pop（）;
HTree* parent = new HTree（lc，rc，parent-》Getweight（），（char）256）;
QTree.push（parent）;
}
//return tree root
return QTree.top（）;
}
void Huffman_Coding（HTree* root， Huff_code& curcode）
{
if（root-》Isleaf（））
{
Huff_Dic［root-》ch］ = curcode;
return;
}
Huff_code& lcode = curcode;
Huff_code& rcode = curcode;
lcode.push_back（false）;
rcode.push_back（true）;
Huffman_Coding（root-》left，lcode）;
Huffman_Coding（root-》right，rcode）;
}
int main（）
{
int freq［Nsymbols］ = {0};
char *str = “this is the string need to be compressed”;
//statistic character frequency
while （*str！=‘\0’）
freq［*str++］++;
//build tree
HTree* r = BuildTree（freq）;
Huff_code nullcode;
nullcode.clear（）;
Huffman_Coding（r，nullcode）;
for（map《char，Huff_code》：：iterator it = Huff_Dic.begin（）; it ！= Huff_Dic.end（）; it++）
{
cout《《（*it）.first《《‘\t’;
Huff_code vec_code = （*it）.second;
for （vector《bool》：：iterator vit = vec_code.begin（）; vit！=vec_code.end（）;vit++）
{
cout《《（*vit）《《endl;
}
}
}
上面這段代碼，我運行出來不對。在調(diào)試的時候發(fā)現(xiàn)了一個問題，就是QTree優(yōu)先隊列中的排序出了問題，說來也是，上面的代碼中，我重載小于號是對HTree object做的；而實際上我建樹時用的是指針，那么優(yōu)先級隊列中元素為指針時該怎么辦呢？
那我們將friend bool operator 》（Node node1，Node node2）修改為friend bool operator 》（Node* node1，Node* node2），也就是傳遞的是Node的指針行不行呢？
答案是不可以，因為根據(jù)c++primer中重載操作符中講的“程序員只能為類類型或枚舉類型的操作數(shù)定義重載操作符，在把操作符聲明為類的成員時，至少有一個類或枚舉類型的參數(shù)按照值或者引用的方式傳遞”，也就是說friend bool operator 》（Node* node1，Node* node2）形參中都是指針類型的是不可以的。我們只能再建一個類，用其中的重載（）操作符作為優(yōu)先隊列的比較函數(shù)。
就得到了下面正確的代碼：
［cpp］ view plain copy/************************************************************************/
/* File Name： Huffman.cpp
* @Function： Lossless Compression
@Author： Sophia Zhang
@Create Time： 2012-9-26 10:40
@Last Modify： 2012-9-26 12:10
*/
/************************************************************************/
#include“iostream”
#include “queue”
#include “map”
#include “string”
#include “iterator”
#include “vector”
#include “algorithm”
using namespace std;
#define NChar 8 //suppose use 8 bits to describe all symbols
#define Nsymbols 1《《NChar //can describe 256 symbols totally （include a-z， A-Z）
typedef vector《bool》 Huff_code;//8 bit code of one char
map《char，Huff_code》 Huff_Dic; //huffman coding dictionary
/************************************************************************/
/* Tree Class elements：
*2 child trees
*character and frequency of current node
*/
/************************************************************************/
class HTree
{
public ：
HTree* left;
HTree* right;
char ch;
int weight;
HTree（）{left = right = NULL; weight=0;ch =‘\0’;}
HTree（HTree* l，HTree* r，int w，char c）{left = l; right = r; weight=w; ch=c;}
~HTree（）{delete left; delete right;}
bool Isleaf（）{return ！left && ！right; }
};
/************************************************************************/
/* prepare for pointer sorting*/
/*because we cannot use overloading in class HTree directly*/
/************************************************************************/
class Compare_tree
{
public：
bool operator （） （HTree* t1， HTree* t2）
{
return t1-》weight》 t2-》weight;
}
};
/************************************************************************/
/* use priority queue to build huffman tree*/
/************************************************************************/
HTree* BuildTree（int *frequency）
{
priority_queue《HTree*，vector《HTree*》，Compare_tree》 QTree;
//1st level add characters
for （int i=0;i《Nsymbols;i++）
{
if（frequency［i］）
QTree.push（new HTree（NULL，NULL，frequency［i］，（char）i））;
}
//build
while （QTree.size（）》1）
{
HTree* lc = QTree.top（）;
QTree.pop（）;
HTree* rc = QTree.top（）;
QTree.pop（）;
HTree* parent = new HTree（lc，rc，lc-》weight+rc-》weight，（char）256）;
QTree.push（parent）;
}
//return tree root
return QTree.top（）;
}
/************************************************************************/
/* Give Huffman Coding to the Huffman Tree*/
/************************************************************************/
void Huffman_Coding（HTree* root， Huff_code& curcode）
{
if（root-》Isleaf（））
{
Huff_Dic［root-》ch］ = curcode;
return;
}
Huff_code lcode = curcode;
Huff_code rcode = curcode;
lcode.push_back（false）;
rcode.push_back（true）;
Huffman_Coding（root-》left，lcode）;
Huffman_Coding（root-》right，rcode）;
}
int main（）
{
int freq［Nsymbols］ = {0};
char *str = “this is the string need to be compressed”;
//statistic character frequency
while （*str！=‘\0’）
freq［*str++］++;
//build tree
HTree* r = BuildTree（freq）;
Huff_code nullcode;
nullcode.clear（）;
Huffman_Coding（r，nullcode）;
for（map《char，Huff_code》：：iterator it = Huff_Dic.begin（）; it ！= Huff_Dic.end（）; it++）
{
cout《《（*it）.first《《‘\t’;
std：：copy（it-》second.begin（），it-》second.end（），std：：ostream_iterator《bool》（cout））;
cout《《endl;
}
}
工商網(wǎng)監(jiān)
評論