赫夫曼樹及赫夫曼編碼、譯碼的算法實作

赫夫曼樹及赫夫曼編碼是資料結構與算法中的一個重要知識點，在生活中也是應用廣泛，現在我來教大家如何建構一顆赫夫曼樹并且實作它的赫夫曼編碼。先講解思路，後面會附完整代碼及運作效果圖。

建構赫夫曼樹的算法思路如下

1.輸入一串字元，統計出每個字元的出現頻度建立字元頻度表。

typedef struct //字元頻度表 
{
	int weight; //權值 
	char c; //對應字元 
}F_W;
F_W w[100];//字元頻度存放數組
int char_count(string s,char a)  //計算單個字元頻度 
{ int i,count=0;
  for(i=0;i<s.length();i++)
  if(s[i]==a) //如果字元a出現一次 count+1 
   count++;
  return count;	
}
void create_w(string s) //建立字元頻度表w 
{ int i,j,flag; 
  w[0].weight=char_count(s,s[0]);//先統計第一個字元頻度并入表 
  w[0].c=s[0];
  int t=1; //t表示數組的循環變量 
  for(i=1;i<s.length();i++)
    { flag=1; //表示這個字元之前沒有出現過 
	  for(j=0;j<i;j++)  
	  {if(s[j]==s[i])//如果這個字元之前已經出現過
        { flag=0;
          break; 
		}
	  }
	if(flag==1) //如果之前沒出現過，統計該字元頻度并放進數組w 
	 { w[t].weight=char_count(s,s[i]);
	   w[t].c=s[i];
	   t++;
	 }
	}
}

2.從頻度表中選擇權值(即頻度)最小的兩個節點依次建構赫夫曼樹

typedef struct
{ int weight; //權值 
  int parent,lchild,rchild;//雙親及左右孩子	
  char c; //對應字元 
 }HTNode,*HuffmanTree;
void Select(HuffmanTree HT,int j,int &s1,int &s2) //在所有的字元節點中挑選兩個權值最小的指派給s1,s2 
{ int i,k,min1=0,min2=0;
  for(i=1;i<=j;i++)
  { if(HT[i].parent!=0) //如果節點已經有雙親則不算在比較範圍内 
    continue;
    if(HT[min1].weight>HT[i].weight)
     min1=i; 
	}
  for(k=1;k<=j;k++)
    { if(HT[k].parent!=0) //如果節點已經有雙親則不算在比較範圍内 
      continue;
	  if(k==min1)  //如果循環到min1直接跳到下一個，不能讓min1的值與min2的值相等 
         continue;
       if(HT[min2].weight>HT[k].weight)
       {
         min2=k;
	   }
	}
	s1=min1;
	s2=min2;
}
int Init(HuffmanTree &HT,F_W *w,int n) //初始化赫夫曼樹 
{ if(n<=1)
    return 0;
  int m=2*n-1,i; //m表示總結點數
  int s1,s2; //存儲最小兩節點的變量
  HuffmanTree p; 
  HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号不啟用 
  HT[0].weight=999;//預設0号為最大權值，為上面的min1,min2的預設值 
  for(p=HT+1,i=1;i<=n;i++,p++,w++)  //将n個字元所對應的單個根節點賦予權值 
  {  p->lchild=p->rchild=p->parent=0;
     p->weight=w->weight;
     p->c=w->c;
  }
  for(;i<=m;i++) //将剩下的分支節點置為空 
  p->lchild=p->rchild=p->parent=p->weight=0;
  for(i=n+1;i<=m;i++) //建立赫夫曼樹
  { Select(HT,i-1,s1,s2); //選出兩個最小的節點 
    HT[s1].parent=HT[s2].parent=i;
	HT[i].lchild=s1;HT[i].rchild=s2;
	HT[i].weight=HT[s1].weight+HT[s2].weight;   //權值合并為一個新節點 
	HT[i].parent=0;	
   } 
  return 1; 
 }

3.求出每個字元所對應的赫夫曼編碼，建立編碼表

int CreateTable(HuffmanCode &HC,HuffmanTree HT,int n)  //建立編碼表 對每個字元進行編碼
{ HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
  char *cd=(char *)malloc(n*sizeof(char));
  cd[n-1]='\0';
  int start,c,i,f;
  for(i=1;i<=n;++i)
  {  start=n-1; //編碼結束符位置
     for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
	   if(HT[f].lchild==c) cd[--start]='0';  //左分支設定0右分支設定1 
	   else cd[--start]='1'; 
	HC[i]=(char *)malloc((n-start)*sizeof(char)); 
    strcpy(HC[i],&cd[start]);
   } 
	free(cd);
	return 1;
 }

如下面題目要求示例：

1、初始化(Init)：能夠對輸入的任意長度的字元串s進行統計，統計每個字元的頻度，并建立哈夫曼樹

2、建立編碼表(CreateTable)：利用已經建好的哈夫曼樹進行編碼，并将每個字元的編碼輸出。

3、編碼(Encoding)：根據編碼表對輸入的字元串進行編碼，并将編碼後的字元串輸出。

4、譯碼(Decoding)：利用已經建好的哈夫曼樹對編碼後的字元串進行譯碼，并輸出譯碼結果。

下面給出完整代碼及運作結果

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef char * *HuffmanCode; //動态配置設定數組存儲每個字元的赫夫曼編碼表 
 typedef struct //字元頻度表 
{
	int weight; //權值 
	char c; //對應字元 
}F_W;
typedef struct
{ int weight; //權值 
  int parent,lchild,rchild;//雙親及左右孩子	
  char c; //對應字元 
 }HTNode,*HuffmanTree;
F_W w[100];//字元頻度存放數組 
char S1[1000]; //将字元串編碼後形成的二進制字元串存放數組 
int char_count(string s,char a)  //計算單個字元頻度 
{ int i,count=0;
  for(i=0;i<s.length();i++)
  if(s[i]==a) //如果字元a出現一次 count+1 
   count++;
  return count;	
}
void create_w(string s) //建立字元頻度表w 
{ int i,j,flag; 
  w[0].weight=char_count(s,s[0]);//先統計第一個字元頻度并入表 
  w[0].c=s[0];
  int t=1; //t表示數組的循環變量 
  for(i=1;i<s.length();i++)
    { flag=1; //表示這個字元之前沒有出現過 
	  for(j=0;j<i;j++)  
	  {if(s[j]==s[i])//如果這個字元之前已經出現過
        { flag=0;
          break; 
		}
	  }
	if(flag==1) //如果之前沒出現過，統計該字元頻度并放進數組w 
	 { w[t].weight=char_count(s,s[i]);
	   w[t].c=s[i];
	   t++;
	 }
	}
}
void Select(HuffmanTree HT,int j,int &s1,int &s2) //在所有的字元節點中挑選兩個權值最小的指派給s1,s2 
{ int i,k,min1=0,min2=0;
  for(i=1;i<=j;i++)
  { if(HT[i].parent!=0) //如果節點已經有雙親則不算在比較範圍内 
    continue;
    if(HT[min1].weight>HT[i].weight)
     min1=i; 
	}
  for(k=1;k<=j;k++)
    { if(HT[k].parent!=0) //如果節點已經有雙親則不算在比較範圍内 
      continue;
	  if(k==min1)  //如果循環到min1直接跳到下一個，不能讓min1的值與min2的值相等 
         continue;
       if(HT[min2].weight>HT[k].weight)
       {
         min2=k;
	   }
	}
	s1=min1;
	s2=min2;
}
int Init(HuffmanTree &HT,F_W *w,int n) //初始化赫夫曼樹 
{ if(n<=1)
    return 0;
  int m=2*n-1,i; //m表示總結點數
  int s1,s2; //存儲最小兩節點的變量
  HuffmanTree p; 
  HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号不啟用 
  HT[0].weight=999;//預設0号為最大權值，為上面的min1,min2的預設值 
  for(p=HT+1,i=1;i<=n;i++,p++,w++)  //将n個字元所對應的單個根節點賦予權值 
  {  p->lchild=p->rchild=p->parent=0;
     p->weight=w->weight;
     p->c=w->c;
  }
  for(;i<=m;i++) //将剩下的分支節點置為空 
  p->lchild=p->rchild=p->parent=p->weight=0;
  for(i=n+1;i<=m;i++) //建立赫夫曼樹
  { Select(HT,i-1,s1,s2); //選出兩個最小的節點 
    HT[s1].parent=HT[s2].parent=i;
	HT[i].lchild=s1;HT[i].rchild=s2;
	HT[i].weight=HT[s1].weight+HT[s2].weight;   //權值合并為一個新節點 
	HT[i].parent=0;	
   } 
  return 1; 
 } 
int CreateTable(HuffmanCode &HC,HuffmanTree HT,int n)  //建立編碼表 對每個字元進行編碼
{ HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
  char *cd=(char *)malloc(n*sizeof(char));
  cd[n-1]='\0';
  int start,c,i,f;
  for(i=1;i<=n;++i)
  {  start=n-1; //編碼結束符位置
     for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
	   if(HT[f].lchild==c) cd[--start]='0';  //左分支設定0右分支設定1 
	   else cd[--start]='1'; 
	HC[i]=(char *)malloc((n-start)*sizeof(char)); 
    strcpy(HC[i],&cd[start]);
   } 
	free(cd);
	return 1;
 } 
int Encoding(string S,int n,HuffmanCode HC) //編碼字元串 
{ int i,j;
  for(i=0;i<S.length();i++)
   {   for(j=0;j<n;j++) //在頻度表中找對應的字元 
          if(w[j].c==S[i])
           { 
		     strcat(S1,HC[j+1]);}  //将該字元的赫夫曼編碼存進S數組 
            
   }
  return 1; 
}
int Decoding(HuffmanTree HT,HuffmanCode HC,int n) //譯碼
{  int m=2*n-1,i=0,j;
    while(S1[i]!='\0')
    { if(S1[i]=='0')
       m=HT[m].lchild;
      else
	   m=HT[m].rchild;
	   if(HT[m].lchild==0) //找到葉子節點(赫夫曼樹必須有兩個節點，是以隻需判斷一個左或者右孩子)	
    	{  for(j=0;j<n;j++)
    		if(w[j].weight==HT[m].weight&&HT[m].c==w[j].c) //找到權值對應的字元 
    		 cout<<w[j].c; //輸出 
    		 m=2*n-1; //重新從根節點出發 
		 } 
	  i++;
    }

}
int main()
{ string s;
  int n=0,i;
  cin>>s;
  create_w(s);
  HuffmanTree HT;
  HuffmanCode HC;
  for(i=0;w[i].weight!=0;i++)
   n++;
  Init(HT,w,n);
  CreateTable(HC,HT,n);
  cout<<"編碼表為："<<endl; 
  for(i=1;i<=n;i++)
   cout<<w[i-1].c<<":"<<HC[i]<<" ";
   cout<<endl;
   cout<<"編碼為："<<endl;
   Encoding(s,n,HC); 
   cout<<S1<<endl; 
   cout<<"譯碼為："<<endl;
   Decoding(HT,HC,n);
   return 0;	
 }

運作結果圖：

赫夫曼樹及赫夫曼編碼、譯碼的算法實作

赫夫曼樹及赫夫曼編碼、譯碼的算法實作

繼續閱讀

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器

hdu7108哈希