快捷導(dǎo)航

解析C++哈夫曼樹編碼和譯碼的實(shí)現(xiàn)

更新時(shí)間：2016年11月15日 17:13:44 作者：Dmego

本篇文章主要介紹了C++哈夫曼樹編碼和譯碼的實(shí)現(xiàn)，詳細(xì)的講訴了哈夫曼樹編碼的原理，有需要的同學(xué)可以了解一下。

一．背景介紹：

給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。

二．實(shí)現(xiàn)步驟：

1.構(gòu)造一棵哈夫曼樹

2.根據(jù)創(chuàng)建好的哈夫曼樹創(chuàng)建一張哈夫曼編碼表

3.輸入一串哈夫曼序列，輸出原始字符

三．設(shè)計(jì)思想：

1.首先要構(gòu)造一棵哈夫曼樹，哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)包括權(quán)值，雙親，左右孩子；假如由n個(gè)字符來構(gòu)造一棵哈夫曼樹，則共有結(jié)點(diǎn)2n-1個(gè)；在構(gòu)造前，先初始化，初始化操作是把雙親，左右孩子的下標(biāo)值都賦為0；然后依次輸入每個(gè)結(jié)點(diǎn)的權(quán)值

2.第二步是通過n-1次循環(huán)，每次先找輸入的權(quán)值中最小的兩個(gè)結(jié)點(diǎn)，把這兩個(gè)結(jié)點(diǎn)的權(quán)值相加賦給一個(gè)新結(jié)點(diǎn)，，并且這個(gè)新結(jié)點(diǎn)的左孩子是權(quán)值最小的結(jié)點(diǎn)，右孩子是權(quán)值第二小的結(jié)點(diǎn)；鑒于上述找到的結(jié)點(diǎn)都是雙親為0的結(jié)點(diǎn)，為了下次能正確尋找到剩下結(jié)點(diǎn)中權(quán)值最小的兩個(gè)結(jié)點(diǎn)，每次循環(huán)要把找的權(quán)值最小的兩個(gè)結(jié)點(diǎn)的雙親賦值不為0（i）.就這樣通過n-1循環(huán)下、操作，創(chuàng)建了一棵哈夫曼樹，其中，前n個(gè)結(jié)點(diǎn)是葉子（輸入的字符結(jié)點(diǎn)）后n-1個(gè)是度為2的結(jié)點(diǎn)

3.編碼的思想是逆序編碼，從葉子結(jié)點(diǎn)出發(fā)，向上回溯，如果該結(jié)點(diǎn)是回溯到上一個(gè)結(jié)點(diǎn)的左孩子，則在記錄編碼的數(shù)組里存“0”，否則存“1”，注意是倒著存；直到遇到根結(jié)點(diǎn)（結(jié)點(diǎn)雙親為0），每一次循環(huán)編碼到根結(jié)點(diǎn)，把編碼存在編碼表中，然后開始編碼下一個(gè)字符（葉子）

4．譯碼的思想是循環(huán)讀入一串哈夫曼序列，讀到“0”從根結(jié)點(diǎn)的左孩子繼續(xù)讀，讀到“1”從右孩子繼續(xù)，如果讀到一個(gè)結(jié)點(diǎn)的左孩子和右孩子是否都為0，如果是說明已經(jīng)讀到了一個(gè)葉子（字符），翻譯一個(gè)字符成功，把該葉子結(jié)點(diǎn)代表的字符存在一個(gè)存儲(chǔ)翻譯字符的數(shù)組中，然后繼續(xù)從根結(jié)點(diǎn)開始讀，直到讀完這串哈夫曼序列，遇到結(jié)束符便退出翻譯循環(huán)

四．源代碼：

/***************************************
目的：1.根據(jù)輸入的字符代碼集及其權(quán)值集，
構(gòu)造赫夫曼樹，輸出各字符的赫夫曼編碼
2.輸入赫夫曼碼序列，輸出原始字符代碼
作者：Dmego  時(shí)間：2016-11-11
****************************************/
#include<iostream>
#define MAX_MA 1000
#define MAX_ZF 100
using namespace std;

//哈夫曼樹的儲(chǔ)存表示
typedef struct
{
 int weight; //結(jié)點(diǎn)的權(quán)值
 int parent, lchild, rchild;//雙親，左孩子，右孩子的下標(biāo)
}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組來儲(chǔ)存哈夫曼樹的結(jié)點(diǎn)
 
//哈夫曼編碼表的儲(chǔ)存表示
typedef char **HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼

//返回兩個(gè)雙親域?yàn)?且權(quán)值最小的點(diǎn)的下標(biāo)
void Select(HuffmanTree HT, int n, int &s1, int &s2)
{
 /*n代表HT數(shù)組的長度
 */

 //前兩個(gè)for循環(huán)找所有結(jié)點(diǎn)中權(quán)值最小的點(diǎn)（字符）
 for (int i = 1; i <= n; i++)
 {//利用for循環(huán)找出一個(gè)雙親為0的結(jié)點(diǎn)
  if (HT[i].parent == 0)
  {
   s1 = i;//s1初始化為i
   break;//找到一個(gè)后立即退出循環(huán)
  }
 }
 for (int i = 1; i <= n; i++)
 {/*利用for循環(huán)找到所有結(jié)點(diǎn)（字符）權(quán)值最小的一個(gè)
  并且保證該結(jié)點(diǎn)的雙親為0*/
  if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
   s1 = i;
 }
 //后兩個(gè)for循環(huán)所有結(jié)點(diǎn)中權(quán)值第二小的點(diǎn)（字符）
 for (int i = 1; i <= n; i++)
 {//利用for循環(huán)找出一個(gè)雙親為0的結(jié)點(diǎn)，并且不能是s1
  if (HT[i].parent == 0 && i != s1)
  {
   s2 = i;//s2初始化為i
   break;//找到一個(gè)后立即退出循環(huán)
  } 
 }

 for (int i = 1; i <= n; i++)
 {/*利用for循環(huán)找到所有結(jié)點(diǎn)（字符）權(quán)值第二小的一個(gè)，
  該結(jié)點(diǎn)滿足不能是s1且雙親是0*/
  if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
   s2 = i;
 }

}

//構(gòu)造哈夫曼樹
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號(hào)單元中的雙親，左孩子，右孩子的下標(biāo)都初始化為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個(gè)單元中葉子結(jié)點(diǎn)的權(quán)值
 }
/*-----------創(chuàng)建工作---------------------------*/
 int s1,s2;
 for (int i = n + 1; i <= m; ++i)
 {//通過n-1次的選擇，刪除，合并來構(gòu)造哈夫曼樹
  Select(HT, i - 1, s1, s2);
  /*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/
  /*將s1,s2的雙親域由0改為i
  (相當(dāng)于把這兩個(gè)結(jié)點(diǎn)刪除了，這兩個(gè)結(jié)點(diǎn)不再參與Select()函數(shù))*/
  HT[s1].parent = i;
  HT[s2].parent = i;
  //s1,與s2分別作為i的左右孩子
  HT[i].lchild = s1;
  HT[i].rchild = s2;
  //結(jié)點(diǎn)i的權(quán)值為s1,s2權(quán)值之和
  HT[i].weight = HT[s1].weight + HT[s2].weight;
 }
}

//從葉子到根逆向求每個(gè)字符的哈夫曼編碼，儲(chǔ)存在編碼表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
 HC = new char*[n + 1];//分配儲(chǔ)存n個(gè)字符編碼的編碼表空間
 char *cd = new char[n];//分配臨時(shí)存儲(chǔ)字符編碼的動(dòng)態(tài)空間
 cd[n - 1] = '\0';//編碼結(jié)束符
 for (int i = 1; i <= n; i++)//逐個(gè)求字符編碼
 {
  int start = n - 1;//start 開始指向最后，即編碼結(jié)束符位置
  int c = i;
  int f = HT[c].parent;//f指向結(jié)點(diǎn)c的雙親
  while (f != 0)//從葉子結(jié)點(diǎn)開始回溯，直到根結(jié)點(diǎn)
  {
   --start;//回溯一次，start向前指向一個(gè)位置
   if (HT[f].lchild == c) cd[start] = '0';//結(jié)點(diǎn)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個(gè)字符編碼分配空間
  strcpy(HC[i], &cd[start]);//把求得編碼的首地址從cd[start]復(fù)制到HC的當(dāng)前行中
 }
 delete cd;
}

//哈夫曼譯碼
void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)
{
 /*
 HT是已經(jīng)創(chuàng)建好的哈夫曼樹
 a[]用來傳入二進(jìn)制編碼
 b[]用來記錄譯出的字符
 zf[]是與哈夫曼樹的葉子對(duì)應(yīng)的字符（葉子下標(biāo)與字符下標(biāo)對(duì)應(yīng)）
 n是字符個(gè)數(shù)，相當(dāng)于zf[]數(shù)組得長度
 */

 int q = 2*n-1;//q初始化為根結(jié)點(diǎn)的下標(biāo)
 int k = 0;//記錄存儲(chǔ)譯出字符數(shù)組的下標(biāo)
 int i = 0;
 for (i = 0; a[i] != '\0';i++)
 {//for循環(huán)結(jié)束條件是讀入的字符是結(jié)束符（二進(jìn)制編碼）
  //此代碼塊用來判斷讀入的二進(jìn)制字符是0還是1
  if (a[i] == '0')
  {/*讀入0，把根結(jié)點(diǎn)(HT[q])的左孩子的下標(biāo)值賦給q
   下次循環(huán)的時(shí)候把HT[q]的左孩子作為新的根結(jié)點(diǎn)*/
   q = HT[q].lchild;
  }
  else if (a[i] == '1')
  {
   q = HT[q].rchild;
  }
  //此代碼塊用來判斷HT[q]是否為葉子結(jié)點(diǎn)
  if (HT[q].lchild == 0 && HT[q].rchild == 0)
  {/*是葉子結(jié)點(diǎn)，說明已經(jīng)譯出一個(gè)字符
  該字符的下標(biāo)就是找到的葉子結(jié)點(diǎn)的下標(biāo)*/
   b[k++] = zf[q];//把下標(biāo)為q的字符賦給字符數(shù)組b[]
   q = 2 * n - 1;//初始化q為根結(jié)點(diǎn)的下標(biāo)
   //繼續(xù)譯下一個(gè)字符的時(shí)候從哈夫曼樹的根結(jié)點(diǎn)開始
  }
 }
 /*譯碼完成之后，用來記錄譯出字符的數(shù)組由于沒有結(jié)束符輸出的
 時(shí)候回報(bào)錯(cuò)，故緊接著把一個(gè)結(jié)束符加到數(shù)組最后*/
 b[k] = '\0';
}
//菜單函數(shù)
void menu()
{
 cout << endl;
 cout << "  ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;
 cout << "  ┃  ★★★★★★★哈夫曼編碼與譯碼★★★★★★★  ┃" << endl;
 cout << "  ┃     1. 創(chuàng)建哈夫曼樹      ┃" << endl;
 cout << "  ┃     2. 進(jìn)行哈夫曼編碼      ┃" << endl;
 cout << "  ┃     3. 進(jìn)行哈夫曼譯碼      ┃" << endl;
 cout << "  ┃     4. 退出程序       ┃" << endl;
 cout << "  ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;
 cout << "      <><注意：空格字符用'- '代替><>" << endl;
 cout << endl;
}
void main()
{
 int falg;//記錄要編碼的字符個(gè)數(shù)
 char a[MAX_MA];//儲(chǔ)存輸入的二進(jìn)制字符
 char b[MAX_ZF];//存儲(chǔ)譯出的字符
 char zf[MAX_ZF];//儲(chǔ)存要編碼的字符
 HuffmanTree HT = NULL;//初始化樹為空數(shù)
 HuffmanCode HC = NULL;//初始化編碼表為空表
 menu();
 while (true)
 {
  int num;
  cout << "<><請(qǐng)選擇功能(1-創(chuàng)建 2-編碼 3-譯碼 4-退出)><>: ";
   cin >> num;
   switch (num)
   {
   case 1 :
    cout << "<><請(qǐng)輸入字符個(gè)數(shù)><>:";
    cin >> falg;
    //動(dòng)態(tài)申請(qǐng)falg個(gè)長度的字符數(shù)組，用來存儲(chǔ)要編碼的字符
    /*char *zf = new char[falg];*/
    cout << "<><請(qǐng)依次輸入" << falg << "個(gè)字符:><>: ";
    for (int i = 1; i <= falg; i++)
     cin >> zf[i];
    cout << "<><請(qǐng)依次輸入" << falg << "個(gè)字符的權(quán)值><>: ";
    CreateHuffmanTree(HT, falg);//調(diào)用創(chuàng)建哈夫曼樹的函數(shù)
    cout << endl;
    cout << "<><創(chuàng)建哈夫曼成功！,下面是該哈夫曼樹的參數(shù)輸出><>：" << endl;
    cout << endl;
    cout << "結(jié)點(diǎn)i"<<"\t"<<"字符" << "\t" << "權(quán)值" << "\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);//調(diào)用創(chuàng)建哈夫曼編碼表的函數(shù)
    cout << endl;
    cout << "<><生成哈夫曼編碼表成功！,下面是該編碼表的輸出><>：" << endl;
    cout << endl;
    cout << "結(jié)點(diǎn)i"<<"\t"<<"字符" << "\t" << "權(quán)值" << "\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 << "<><請(qǐng)輸入想要翻譯的一串二進(jìn)制編碼><>：";
    /*這樣可以動(dòng)態(tài)的直接輸入一串二進(jìn)制編碼，
    因?yàn)檫@樣輸入時(shí)最后系統(tǒng)會(huì)自動(dòng)加一個(gè)結(jié)束符*/
    cin >> a;
    TranCode(HT, a, zf, b, falg);//調(diào)用譯碼的函數(shù)，
     /*這樣可以直接把數(shù)組b輸出，因?yàn)樽詈笥?
     在數(shù)組b添加輸出時(shí)遇到結(jié)束符會(huì)結(jié)束輸出*/
    cout << endl;
    cout << "<><譯碼成功！翻譯結(jié)果為><>：" << 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

}

五．運(yùn)行截圖：