/*
Name: 赫夫曼編碼
Copyright: 始發于goal00001111的專欄；允許自由轉載，但必須注明作者和出處
Author: goal00001111
Date: 16-12-08 21:16
Description: 赫夫曼編碼
本程序實現了使用赫夫曼編碼壓縮數據；輸入一串字符串sourceCode——為方便理解，暫時要求字符串只包含大寫字母和空格，如果你愿意，
很容易就可以推廣到所有的字符——計算出字符串中各個字母的權重，然后對其進行赫夫曼編碼，輸出赫夫曼樹。
將赫夫曼樹的葉子結點存儲到有序二叉樹中，輸出原字符串經壓縮后得到的用'0'和'1'表示的新字符串destCode；
然后利用赫夫曼樹將字符串destCode進行譯碼，得到目標字符串objCode，比較objCode和sourceCode，發現完全一樣！
編碼譯碼成功！
最后銷毀有序二叉樹和赫夫曼樹。
本程序的一個亮點是使用了二叉堆來存儲需要合并的赫夫曼樹結點，這樣在求最小值時時間復雜度可以降低到log(n)。
另外關于赫夫曼編碼的詳細內容請參考維基百科： http://zh.wikipedia.org/wiki/%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
和數據結構自考網：http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.6.2.1.htm
關于二叉堆的詳細內容請參考百度百科：http://baike.baidu.com/view/668854.html
*/
#include<iostream>
using namespace std;
typedef char ElemType;
typedef struct sNode
{
double weight;
ElemType data;
} *Source;
typedef struct hNode
{
double weight;
ElemType data;
int lc, rc;
} *HuffmanTree;
typedef struct cNode
{
ElemType data;
string str;
struct cNode *lc, *rc;
} *Btree;
HuffmanTree CreateHuffmanTree(const Source w, int n);//創建一棵赫夫曼樹
void BuildHeap(HuffmanTree t, int n); //構造一個二叉堆；小頂堆
void PercDown(HuffmanTree t, int pos, int n);//構造二叉堆的功能子函數
void DeleteMin(HuffmanTree t, int len); //刪除二叉堆的根，并通過上移使得新得到的序列仍為二叉堆
void InsertHfNode(HuffmanTree t, int len, struct hNode x); //把x插入到原長度為len的二叉堆
void Preorder(HuffmanTree t, int p); //先序遍歷赫夫曼樹
void Postorder(Btree & t, HuffmanTree a, int n); //后序遍歷赫夫曼樹，并記錄葉子結點編碼
bool InsertBtNode(Btree & t, Btree s); //向一個二叉排序樹t中插入一個結點s
void Inorder(Btree t); //中序遍歷二叉排序樹
Btree Search(Btree p, ElemType data); //查找值為data的結點的遞歸算法
string Coding(string s, Btree t); //利用記錄了葉子結點編碼的排序二叉樹，對sourceCode進行編碼，返回編碼后的字符串
string Decode(string s, HuffmanTree hT); //利用赫夫曼樹對destCode進行解碼
void DestroyBTree(Btree & t); //銷毀一棵二叉排序樹
void DestroyHfmanTree(HuffmanTree & t, int n); //銷毀一棵赫夫曼樹
int main()
{
string sourceCode;
getline(cin, sourceCode, '\n');
int n = sourceCode.size();
const int MAX = 27; //原碼由26個大寫字母加空格組成
Source w = new struct sNode[MAX];
//讀取各個字母并初始化權重
w[MAX-1].data = ' ';
w[MAX-1].weight = 0;
for (int i=MAX-2; i>=0; i--)
{
w[i].data = 'A' + i;
w[i].weight = 0;
}
//讀取各個字母的權重
for (int i=0; i<n; i++)
{
if (sourceCode[i] == ' ')
w[26].weight++;
else
w[sourceCode[i]-'A'].weight++;
}
//獲取出現了的大寫字母和空格
n = 0;
for (int i=0; i<MAX; i++)
{
if (w[i].weight > 0)
w[n++] = w[i];
}
// //直接輸入原碼和權重
// for (int i=0; i<n; i++)
// {
// cin >> w[i].weight >> w[i].data;
// }
for (int i=0; i<n; i++)
{
cout << w[i].weight << " " << w[i].data << endl;
}
HuffmanTree hT = CreateHuffmanTree(w, n);//構造赫夫曼樹
// for (int i=1; i<2*n; i++)
// cout << hT[i].weight << " ";
// cout << endl;
//先序遍歷赫夫曼樹，并輸出結點權重和葉子結點的data
Preorder(hT, 1);
cout << endl;
//后序遍歷赫夫曼樹，并記錄葉子結點編碼
Btree bT = NULL;
Postorder(bT, hT, n);
//中序遍歷記錄了葉子結點編碼的排序二叉樹
Inorder(bT);
//利用記錄了葉子結點編碼的排序二叉樹，對sourceCode進行編碼
string destCode = Coding(sourceCode, bT);
cout << destCode << endl;
//利用赫夫曼樹對destCode進行解碼
string objCode = Decode(destCode, hT);
cout << objCode << endl;
DestroyBTree(bT); //銷毀二叉排序樹
//Inorder(bT); //再輸出試試看
DestroyHfmanTree(hT, n); //銷毀赫夫曼樹
//Preorder(hT, 1); //再輸出試試看
system("pause");
return 0;
}
//創建一棵赫夫曼樹
HuffmanTree CreateHuffmanTree(const Source w, int n)
{
HuffmanTree hT = new struct hNode[2*n]; //第一個結點不用
for (int i=0; i<n; i++)
{
hT[i+1].data = w[i].data;
hT[i+1].weight = w[i].weight;
hT[i+1].lc = hT[i+1].rc = 0;
}
BuildHeap(hT, n);//構造一個二叉堆；小頂堆
struct hNode add;
int left = n;
int right = n;
while (left > 1)
{
hT[++right] = hT[1];
add.weight = hT[1].weight;
add.lc = right; //存儲左孩子下標
DeleteMin(hT, left--);
hT[left+1] = hT[1];
add.weight += hT[1].weight;
add.rc = left+1; //存儲右孩子下標
DeleteMin(hT, left--);
InsertHfNode(hT, ++left, add);
//for (int i=1; i<=right; i++)
// cout << hT[i].weight << " ";
// cout << endl;
// system("pause");
}
return hT;
}
//構造一個二叉堆；小頂堆
void BuildHeap(HuffmanTree t, int len)
{
for (int i=len/2; i>0; i--)
{
PercDown(t, i, len);
}
}
//構造二叉堆的功能子函數
void PercDown(HuffmanTree t, int pos, int len)
{
int child;
struct hNode min = t[pos];
while (pos * 2 <= len)
{
child = pos * 2;
if (child != len && t[child+1].weight < t[child].weight)
child++;
if (min.weight > t[child].weight)
t[pos] = t[child];
else
break;
pos = child;
}
t[pos] = min;
}
//刪除二叉堆的根，并通過上移使得新得到的序列仍為二叉堆
void DeleteMin(HuffmanTree t, int len)
{
struct hNode last = t[len--];//二叉堆的最后一個元素
int child, pos = 1;
while (pos * 2 <= len) //把二叉堆的某些元素往前移，使得新得到的序列仍為二叉堆
{
child = pos * 2;
if (child != len && t[child+1].weight < t[child].weight) //若i有右兒子，且右兒子小于左兒子，c指向右兒子
child++;
if (last.weight > t[child].weight) //若i的小兒子小于二叉堆的最后一個元素，把其移到i的位置
t[pos] = t[child];
else
break;
pos = child;
}
t[pos] = last; //把二叉堆的最后一個元素放到適當的空位，此時得到的序列仍為二叉堆
}
//把x插入到原長度為len的二叉堆
void InsertHfNode(HuffmanTree t, int len, struct hNode x)
{
int i;
for (i=len; i/2>0 && t[i/2].weight>x.weight; i/=2)
t[i] = t[i/2];
t[i] = x;
}
//后序遍歷赫夫曼樹，并記錄葉子結點編碼
void Postorder(Btree & t, HuffmanTree a, int n)
{
int *stack = new int[n];
int *tag = new int[n];
char *buf = new char[n];
bool flag = true;
int top = -1;
int p = 1;
while (a[p].lc > 0 || top >= 0)
{
while (a[p].lc > 0) //先一直尋找左孩子
{
flag = true; //此時p指向的是新葉子（未輸出過的葉子）
stack[++top] = p; //結點入棧
p = a[p].lc;
tag[top] = 0; //表示右孩子沒有被訪問
buf[top] = '0'; //左孩子標記'0'
}
if (flag) //如果p指向的是新葉子
{
//cout << a[p].data << " : "; //輸出葉子結點
// for (int i=0; i<=top; i++)
// cout << buf[i];
// cout << endl;
Btree s = new struct cNode;
s->data = a[p].data;
for (int i=0; i<=top; i++)
s->str += buf[i];
s->lc = s->rc = NULL;
if (!(InsertBtNode(t, s))) //插入一個結點s
delete s;
}
if (top >= 0) //所有左孩子處理完畢后
{
if (tag[top] == 0) //如果右孩子沒有被訪問
{
flag = true; //此時p指向的是新葉子（未輸出過的葉子）
p = stack[top]; //讀取棧頂元素，但不退棧 ，因為要先輸出其右孩子結點
p = a[p].rc;
tag[top] = 1; //表示右孩子被訪問，下次直接退棧
buf[top] = '1'; //右孩子標記'1'
}
else //棧頂元素出棧
{
flag = false; //此時p指向的是舊葉子（已輸出過的葉子），不再輸出
top--;
}
}
}
}
//先序遍歷赫夫曼樹
void Preorder(HuffmanTree t, int p)
{
if (t == NULL)
return;
if (t[p].lc > 0)
{
cout << t[p].weight << endl;
Preorder(t, t[p].lc); //遍歷左子樹
Preorder(t, t[p].rc); //遍歷右子樹
}
else
cout << t[p].weight << " " << t[p].data << endl;
}
//向一個二叉排序樹t中插入一個結點s
bool InsertBtNode(Btree & t, Btree s)
{
if (t == NULL)
{
t = s;
return true;
}
else if (t->data > s->data) //把s所指結點插入到左子樹中
return InsertBtNode(t->lc, s);
else if (t->data < s->data) //把s所指結點插入到右子樹中
return InsertBtNode(t->rc, s);
else //若s->data等于b的根結點的數據域之值，則什么也不做
return false;
}
//中序遍歷二叉排序樹
void Inorder(Btree t)
{
if (t)
{
Inorder(t->lc); //遍歷左子樹
cout << t->data << " : " << t->str << endl; //輸出該結點
Inorder(t->rc); //遍歷右子樹
}
}
//查找值為data的結點的遞歸算法
Btree Search(Btree p, ElemType data)
{
if (p == NULL || p->data == data) //空樹或找到結點
return p;
if (p->data > data)
return Search(p->lc, data); //在左孩子中尋找
else
return Search(p->rc, data); //在右孩子中尋找
}
//利用記錄了葉子結點編碼的排序二叉樹，對sourceCode進行編碼，返回編碼后的字符串
string Coding(string s, Btree t)
{
Btree p = NULL;
string dest;
for (int i=0; i<s.size(); i++)
{
p = Search(t, s[i]);
if (p != NULL)
{
dest += p->str;
//dest += ' ';
}
}
return dest;
}
//利用赫夫曼樹對destCode進行解碼
string Decode(string s, HuffmanTree hT)
{
string dest;
int p = 1;
int i = 0;
while (i < s.size())
{
while (hT[p].lc > 0)//非葉子結點
{
if (s[i++] == '0')
p = hT[p].lc; //向左結點前進
else
p = hT[p].rc; //向右結點前進
}
dest += hT[p].data; //存儲葉子結點
p = 1;
}
return dest;
}
//銷毀一棵二叉排序樹
void DestroyBTree(Btree & t)
{
if (t != NULL)
{
DestroyBTree(t->lc);
DestroyBTree(t->rc);
delete t;
t = NULL;
}
}
//銷毀一棵赫夫曼樹
void DestroyHfmanTree(HuffmanTree & t, int n)
{
for (int i=n-1; i>=0; i--)
{
delete &t[i];
}
t = NULL;
}