最近學(xué)到Huffman編碼稼跳，于是想要實現(xiàn)出來看看屹电，查閱了一些資料阶剑，就開始動手了。
首先整理一下思路危号，Huffman編碼關(guān)鍵是構(gòu)造huffman樹牧愁，輸入字母表以及對應(yīng)權(quán)重，構(gòu)建Huffman樹外莲；由Huffman樹即可生成Huffman碼和字母表的映射猪半。
由于hufgman樹的特殊性兔朦，節(jié)點的度只有0和2，只有葉子結(jié)點代表字母磨确，其他節(jié)點均為輔助接點沽甥，當(dāng)有n個葉子的時候必然有n-1個輔助節(jié)點》Π拢考慮用連續(xù)存儲來存放摆舟，具體來說就是個結(jié)構(gòu)體數(shù)組。每個結(jié)構(gòu)體中記錄節(jié)點的字母邓了，權(quán)重恨诱，父親節(jié)點，孩子節(jié)點骗炉，沒有的置為-1照宝；在長度為2n-1的結(jié)構(gòu)體數(shù)組中，前n個存放葉子結(jié)點句葵，后n-1個存放輔助節(jié)點厕鹃，初始的時候葉子結(jié)點都沒有父親節(jié)點，構(gòu)建Huffman樹的時候笼呆，只需要依次進行n-1輪插入輔助節(jié)點操作即可（沒插入一個輔助節(jié)點就會導(dǎo)致森林中的樹減少一個）熊响。
首先定義一個hufTree類：
#include <stdlib.h>
#include "stdafx.h"
#include"Windows.h"
#include <string>
#include <iostream>
using namespace std;
class hufTree {
private:
typedef struct hufNode {
char alpha;
int weight;
int lChild, rChild, parent;
} *pNode;
int _n;
int _m;//葉子數(shù)和總節(jié)點數(shù)
pNode huf_arr;
void getMintwo(int flag,int *min1,int* min2);
public:
hufTree(char * alpha,int * weight,int N);//構(gòu)造huf樹，alpha為字母數(shù)組
~hufTree() {};
string* hufCodingtable();
string encode(string str,string * huftable, char * alpha);
string decode(string str, string * huftable, char * alpha);
};
由于要多次選取森林中權(quán)最小的兩個樹诗赌，所以汗茄，寫成函數(shù)getMintwo（）；
void hufTree::getMintwo(int flag, int *min1, int* min2) {
pNode hf = huf_arr;
*min1 = 0; *min2 = 1;
int weight1=9999, weight2=9999;
for (int i = 0; i < flag;i++)
{
if ((hf[i].parent == -1) && (hf[i].weight < weight1)) { *min1 = i; weight1 = huf_arr[i].weight; }
else if ((hf[i].parent == -1) && (hf[i].weight < weight2)) { *min2 = i; weight2 = huf_arr[i].weight; }
}
}
重載構(gòu)造函數(shù)铭若，實現(xiàn)Huffman樹的構(gòu)建,這里最開始的時候洪碳，申請長度為2n-1的結(jié)構(gòu)體數(shù)組空間，然后將前n個初始化為葉子結(jié)點叼屠，并且沒有父親節(jié)點（獨立成為一棵樹）和孩子節(jié)點瞳腌，之后在插入輔助接點形成新樹刪除舊樹之時只需改變元素之間的父子關(guān)系即可。
//構(gòu)造huf樹
hufTree::hufTree(char * alpha, int * weight, int N) {
char* tmp=new char[20];
_n = N;
_m = N * 2 - 1;
huf_arr = new hufNode[_m];
for (int i = 0; i < _n; i++)
{
huf_arr[i].alpha = alpha[i];
huf_arr[i].parent = -1;
huf_arr[i].lChild = -1;
huf_arr[i].rChild = -1;
huf_arr[i].weight = weight[i];
//*tmp = huf_arr[i].alpha;
//OutputDebugStringA(tmp);
}
int min1, min2;
for (int i = _n; i < _m; i++)
{
getMintwo(i,&min1,&min2);
huf_arr[i].parent = -1;
huf_arr[i].lChild = min1;
huf_arr[i].rChild = min2;
huf_arr[min1].parent = i;
huf_arr[min2].parent = i;
huf_arr[i].weight = huf_arr[min1].weight + huf_arr[min2].weight;
}
}
然后根據(jù)已有的Huffman樹生成對應(yīng)的編碼映射表镜雨，此處應(yīng)該有鍵值表嫂侍，但是我嫌麻煩，所以直接用兩個平行的數(shù)組分別存放鍵和值(函數(shù)值返回hufman碼表荚坞，和已知的字母表一一順序?qū)?yīng))挑宠。方法是，從對應(yīng)的葉子開始向上搜索到根節(jié)點颓影，每次判斷當(dāng)前節(jié)點是父親節(jié)點的左節(jié)點還是右節(jié)點各淀，對應(yīng)加入0或1，由于得到的碼是反序的诡挂，最后將字符串反轉(zhuǎn)后插入編碼表即可碎浇。
string* hufTree::hufCodingtable() {
string* table = new string[_n];
for (int i = 0; i < _n; i++)
{
int cur = i,parent=huf_arr[i].parent;
string tmp = "";
while (parent!=-1) {
if (huf_arr[parent].lChild==cur)
{
tmp += "0";
}
else
{
tmp += "1";
}
cur = parent;
parent = huf_arr[cur].parent;
}
reverse(tmp.begin(),tmp.end());
table[i] = tmp;
}
return table;
}
編碼和解碼函數(shù)临谱，編碼函數(shù)很簡單，每次取出一個字符奴璃，將其對應(yīng)Huffman碼值查出后加到輸出字符串即可悉默；解碼函數(shù)由于每個碼長短未知，所以設(shè)置一個buffer變量溺健，每次讀入一個二進制位到buffer麦牺，比對Huffman碼表是否有相應(yīng)的字母，如有鞭缭，取出加入輸出字符串后剖膳，buffer歸零；若無岭辣，則在buffer中再加入一個二進制位吱晒。
string hufTree::encode(string str, string * huftable, char * alpha)
{
string tmp = "";
int len = str.length();
for (int i = 0; i < len; i++)
for (int j = 0; j < _n; j++)
{
if (huf_arr[j].alpha==str.at(i))
{
tmp += huftable[j];
}
}
return tmp;
}
string hufTree::decode(string str, string * huftable, char * alpha)
{
string tmp = "";
string buffer = "";
int len = str.length();
for (int i = 0; i < len; i++)
{
buffer += str.at(i);
for (int j = 0; j < _n; j++)
{
if (huftable[j] == buffer)
{
tmp += alpha[j];
buffer = "";
}
}
}
return tmp;
}
然后就是主函數(shù)了,..以前上課老愛用getchar停住cmd黑框，今天忽然掉進個坑沦童，我把黑框關(guān)閉后再去修改了代碼后就出現(xiàn)lnk1168錯誤仑濒，原因是之前那個程序根本沒停，我去任務(wù)管理器試圖關(guān)閉發(fā)現(xiàn)關(guān)閉不了偷遗，估計是沒給它個char他不甘心停止吧墩瞳。所以改成了system（“pause”），暫時還沒出現(xiàn)問題氏豌。
int main()
{
char alpha[] = { 'a','b','c','d','e','f','g' };
int weight[] = { 1,2,3,4,5,6,7 };
hufTree hf(alpha,weight,7);
string str = "abcdefg";
string encode=hf.encode(str,hf.hufCodingtable(),alpha);
cout << encode;
string decode = hf.decode(encode,hf.hufCodingtable(),alpha);
cout << decode;
system("pause");
return 0;
}
輸出：
011001110101101110010
abcdefg
Press any key to continue . . .
