解析C++哈夫曼樹編碼和譯碼的實現(xiàn)
更新時間：2016年11月15日 17:13:44 作者：Dmego
本篇文章主要介紹了C++哈夫曼樹編碼和譯碼的實現(xiàn)，詳細的講訴了哈夫曼樹編碼的原理，有需要的同學可以了解一下。
一．背景介紹：
給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近。
二．實現(xiàn)步驟：
1.構造一棵哈夫曼樹
2.根據創(chuàng)建好的哈夫曼樹創(chuàng)建一張哈夫曼編碼表
3.輸入一串哈夫曼序列，輸出原始字符
三．設計思想：
1.首先要構造一棵哈夫曼樹，哈夫曼樹的結點結構包括權值，雙親，左右孩子；假如由n個字符來構造一棵哈夫曼樹，則共有結點2n-1個；在構造前，先初始化，初始化操作是把雙親，左右孩子的下標值都賦為0；然后依次輸入每個結點的權值
2.第二步是通過n-1次循環(huán)，每次先找輸入的權值中最小的兩個結點，把這兩個結點的權值相加賦給一個新結點，，并且這個新結點的左孩子是權值最小的結點，右孩子是權值第二小的結點；鑒于上述找到的結點都是雙親為0的結點，為了下次能正確尋找到剩下結點中權值最小的兩個結點，每次循環(huán)要把找的權值最小的兩個結點的雙親賦值不為0（i）.就這樣通過n-1循環(huán)下、操作，創(chuàng)建了一棵哈夫曼樹，其中，前n個結點是葉子（輸入的字符結點）后n-1個是度為2的結點
3.編碼的思想是逆序編碼，從葉子結點出發(fā)，向上回溯，如果該結點是回溯到上一個結點的左孩子，則在記錄編碼的數(shù)組里存“0”，否則存“1”，注意是倒著存；直到遇到根結點（結點雙親為0），每一次循環(huán)編碼到根結點，把編碼存在編碼表中，然后開始編碼下一個字符（葉子）
4．譯碼的思想是循環(huán)讀入一串哈夫曼序列，讀到“0”從根結點的左孩子繼續(xù)讀，讀到“1”從右孩子繼續(xù)，如果讀到一個結點的左孩子和右孩子是否都為0，如果是說明已經讀到了一個葉子（字符），翻譯一個字符成功，把該葉子結點代表的字符存在一個存儲翻譯字符的數(shù)組中，然后繼續(xù)從根結點開始讀，直到讀完這串哈夫曼序列，遇到結束符便退出翻譯循環(huán)
四．源代碼：
/***************************************
目的：1.根據輸入的字符代碼集及其權值集，
構造赫夫曼樹，輸出各字符的赫夫曼編碼
2.輸入赫夫曼碼序列，輸出原始字符代碼
作者：Dmego 時間：2016-11-11
****************************************/
#include<iostream>
#define MAX_MA 1000
#define MAX_ZF 100
using namespace std;
//哈夫曼樹的儲存表示
typedef struct
{
int weight; //結點的權值
int parent, lchild, rchild;//雙親，左孩子，右孩子的下標
}HTNode,*HuffmanTree; //動態(tài)分配數(shù)組來儲存哈夫曼樹的結點
//哈夫曼編碼表的儲存表示
typedef char **HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼編碼
//返回兩個雙親域為0且權值最小的點的下標
void Select(HuffmanTree HT, int n, int &s1, int &s2)
{
/*n代表HT數(shù)組的長度
*/
//前兩個for循環(huán)找所有結點中權值最小的點（字符）
for (int i = 1; i <= n; i++)
{//利用for循環(huán)找出一個雙親為0的結點
if (HT[i].parent == 0)
{
s1 = i;//s1初始化為i
break;//找到一個后立即退出循環(huán)
}
}
for (int i = 1; i <= n; i++)
{/*利用for循環(huán)找到所有結點（字符）權值最小的一個
并且保證該結點的雙親為0*/
if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
s1 = i;
}
//后兩個for循環(huán)所有結點中權值第二小的點（字符）
for (int i = 1; i <= n; i++)
{//利用for循環(huán)找出一個雙親為0的結點，并且不能是s1
if (HT[i].parent == 0 && i != s1)
{
s2 = i;//s2初始化為i
break;//找到一個后立即退出循環(huán)
}
}
for (int i = 1; i <= n; i++)
{/*利用for循環(huán)找到所有結點（字符）權值第二小的一個，
該結點滿足不能是s1且雙親是0*/
if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
s2 = i;
}
}
//構造哈夫曼樹
void CreateHuffmanTree(HuffmanTree &HT, int n)
{
/*-----------初始化工作-------------------------*/
if (n <= 1)
return;
int m = 2 * n - 1;
HT = new HTNode[m + 1];
for (int i = 1; i <= m; ++i)
{//將1~m號單元中的雙親，左孩子，右孩子的下標都初始化為0
HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
}
for (int i = 1; i <= n; ++i)
{
cin >> HT[i].weight;//輸入前n個單元中葉子結點的權值
}
/*-----------創(chuàng)建工作---------------------------*/
int s1,s2;
for (int i = n + 1; i <= m; ++i)
{//通過n-1次的選擇，刪除，合并來構造哈夫曼樹
Select(HT, i - 1, s1, s2);
/*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/
/*將s1,s2的雙親域由0改為i
(相當于把這兩個結點刪除了，這兩個結點不再參與Select()函數(shù))*/
HT[s1].parent = i;
HT[s2].parent = i;
//s1,與s2分別作為i的左右孩子
HT[i].lchild = s1;
HT[i].rchild = s2;
//結點i的權值為s1,s2權值之和
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
//從葉子到根逆向求每個字符的哈夫曼編碼，儲存在編碼表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
HC = new char*[n + 1];//分配儲存n個字符編碼的編碼表空間
char *cd = new char[n];//分配臨時存儲字符編碼的動態(tài)空間
cd[n - 1] = '\0';//編碼結束符
for (int i = 1; i <= n; i++)//逐個求字符編碼
{
int start = n - 1;//start 開始指向最后，即編碼結束符位置
int c = i;
int f = HT[c].parent;//f指向結點c的雙親
while (f != 0)//從葉子結點開始回溯，直到根結點
{
--start;//回溯一次，start向前指向一個位置
if (HT[f].lchild == c) cd[start] = '0';//結點c是f的左孩子，則cd[start] = 0;
else cd[start] = '1';//否則c是f的右孩子，cd[start] = 1
c = f;
f = HT[f].parent;//繼續(xù)向上回溯
}
HC[i] = new char[n - start];//為第i個字符編碼分配空間
strcpy(HC[i], &cd[start]);//把求得編碼的首地址從cd[start]復制到HC的當前行中
}
delete cd;
}
//哈夫曼譯碼
void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)
{
/*
HT是已經創(chuàng)建好的哈夫曼樹
a[]用來傳入二進制編碼
b[]用來記錄譯出的字符
zf[]是與哈夫曼樹的葉子對應的字符（葉子下標與字符下標對應）
n是字符個數(shù)，相當于zf[]數(shù)組得長度
*/
int q = 2*n-1;//q初始化為根結點的下標
int k = 0;//記錄存儲譯出字符數(shù)組的下標
int i = 0;
for (i = 0; a[i] != '\0';i++)
{//for循環(huán)結束條件是讀入的字符是結束符（二進制編碼）
//此代碼塊用來判斷讀入的二進制字符是0還是1
if (a[i] == '0')
{/*讀入0，把根結點(HT[q])的左孩子的下標值賦給q
下次循環(huán)的時候把HT[q]的左孩子作為新的根結點*/
q = HT[q].lchild;
}
else if (a[i] == '1')
{
q = HT[q].rchild;
}
//此代碼塊用來判斷HT[q]是否為葉子結點
if (HT[q].lchild == 0 && HT[q].rchild == 0)
{/*是葉子結點，說明已經譯出一個字符
該字符的下標就是找到的葉子結點的下標*/
b[k++] = zf[q];//把下標為q的字符賦給字符數(shù)組b[]
q = 2 * n - 1;//初始化q為根結點的下標
//繼續(xù)譯下一個字符的時候從哈夫曼樹的根結點開始
}
}
/*譯碼完成之后，用來記錄譯出字符的數(shù)組由于沒有結束符輸出的
時候回報錯，故緊接著把一個結束符加到數(shù)組最后*/
b[k] = '\0';
}
//菜單函數(shù)
void menu()
{
cout << endl;
cout << " ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;
cout << " ┃ ★★★★★★★哈夫曼編碼與譯碼★★★★★★★ ┃" << endl;
cout << " ┃ 1. 創(chuàng)建哈夫曼樹 ┃" << endl;
cout << " ┃ 2. 進行哈夫曼編碼 ┃" << endl;
cout << " ┃ 3. 進行哈夫曼譯碼 ┃" << endl;
cout << " ┃ 4. 退出程序 ┃" << endl;
cout << " ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;
cout << " <><注意：空格字符用'- '代替><>" << endl;
cout << endl;
}
void main()
{
int falg;//記錄要編碼的字符個數(shù)
char a[MAX_MA];//儲存輸入的二進制字符
char b[MAX_ZF];//存儲譯出的字符
char zf[MAX_ZF];//儲存要編碼的字符
HuffmanTree HT = NULL;//初始化樹為空數(shù)
HuffmanCode HC = NULL;//初始化編碼表為空表
menu();
while (true)
{
int num;
cout << "<><請選擇功能(1-創(chuàng)建 2-編碼 3-譯碼 4-退出)><>: ";
cin >> num;
switch (num)
{
case 1 :
cout << "<><請輸入字符個數(shù)><>:";
cin >> falg;
//動態(tài)申請falg個長度的字符數(shù)組，用來存儲要編碼的字符
/*char *zf = new char[falg];*/
cout << "<><請依次輸入" << falg << "個字符:><>: ";
for (int i = 1; i <= falg; i++)
cin >> zf[i];
cout << "<><請依次輸入" << falg << "個字符的權值><>: ";
CreateHuffmanTree(HT, falg);//調用創(chuàng)建哈夫曼樹的函數(shù)
cout << endl;
cout << "<><創(chuàng)建哈夫曼成功！,下面是該哈夫曼樹的參數(shù)輸出><>：" << endl;
cout << endl;
cout << "結點i"<<"\t"<<"字符" << "\t" << "權值" << "\t" << "雙親" << "\t" << "左孩子" << "\t" << "右孩子" << endl;
for (int i = 1; i <= falg * 2 - 1; i++)
{
cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << HT[i].rchild << endl;
}
cout << endl;
break;
case 2:
CreatHuffmanCode(HT, HC, falg);//調用創(chuàng)建哈夫曼編碼表的函數(shù)
cout << endl;
cout << "<><生成哈夫曼編碼表成功！,下面是該編碼表的輸出><>：" << endl;
cout << endl;
cout << "結點i"<<"\t"<<"字符" << "\t" << "權值" << "\t" << "編碼" << endl;
for (int i = 1; i <= falg; i++)
{
cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HC[i] << endl;
}
cout << endl;
break;
case 3:
cout << "<><請輸入想要翻譯的一串二進制編碼><>：";
/*這樣可以動態(tài)的直接輸入一串二進制編碼，
因為這樣輸入時最后系統(tǒng)會自動加一個結束符*/
cin >> a;
TranCode(HT, a, zf, b, falg);//調用譯碼的函數(shù)，
/*這樣可以直接把數(shù)組b輸出，因為最后有
在數(shù)組b添加輸出時遇到結束符會結束輸出*/
cout << endl;
cout << "<><譯碼成功！翻譯結果為><>：" << b << endl;
cout << endl;
break;
case 4:
cout << endl;
cout << "<><退出成功！><>" << endl;
exit(0);
default:
break;
}
}
//-abcdefghijklmnopqrstuvwxyz
//186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
//000101010111101111001111110001100100101011110110
}
五．運行截圖：
原文鏈接：http://www.cnblogs.com/dmego/p/6064069.html
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了C語言打印華氏-攝氏溫度對照表的方法,涉及C語言字符串與數(shù)字操作的相關技巧,非常簡單實用,需要的朋友可以參考下2015-07-07
軟件開發(fā)過程中經常會用到配置文件,某些應用場景要求在軟件運行時動態(tài)修改配置文件,此時就需要監(jiān)控配置文件是否被修改,下面我們就來看看如何使用C++實現(xiàn)這一功能吧2024-02-02
這篇文章主要為大家介紹了C語言數(shù)據類型和變量常量，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
用vscode來寫opencv代碼需要自己編譯OpenCV，主要用到MinGW-w64和CMake工具。接下來通過本文給大家介紹VScode搭建OpenCV環(huán)境的相關知識,需要的朋友可以參考下2021-11-11
這篇文章主要介紹了C語言程序設計譚浩強第五版課后答案(第三章習題答案)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-04-04
本章主要介紹C語言與C++的內存管理，以C++的內存分布作為引入，介紹C++不同于C語言的內存管理方式（new?delete對比?malloc?free)，感興趣的朋友來看看吧2022-04-04
這篇文章主要為大家詳細介紹了C++設計模式之策略模式Strategy ，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
這篇文章主要介紹了C語言如何實現(xiàn)翻轉字符串中的單詞，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
getchar()?字符輸入函數(shù)，沒有參數(shù)，從輸入緩沖區(qū)里面讀取一個字，需要注意一次只能讀取一個字符，這篇文章主要介紹了C語言中getchar函數(shù)使用詳解,需要的朋友可以參考下2022-12-12
Qt?加載?libjpeg?庫出現(xiàn)“長跳轉已經運行”錯誤問題解決
這篇文章主要介紹了Qt?加載?libjpeg?庫出現(xiàn)“長跳轉已經運行”錯誤,本文給大家分享完美解決方案，需要的朋友可以參考下2023-04-04