哈工大資料結構、算法設計、計算機系統、軟體構造等所有實驗我都會釋出在部落格上，我會慢慢更新的，如果對你有幫助的話，可以多多關注一下。
目錄
- 對于本次實驗，無非要解決的就是以下幾個問題：
-
- 看到這裡，咱們的思路就清晰了，現在正式開始講具體步驟。
-
- 1.用什麼資料結構去表示哈夫曼樹
- 2. 如何構造哈夫曼樹
- 3.哈夫曼編碼
- 4.哈夫曼解碼
- 5.最終結果展示
- 6.發現解碼前和解碼後一模一樣
- 别忘了點個關注
其他的實驗連結
哈工大資料結構實驗一 線性結構及其應用
哈工大資料結構實驗1 算術表達式求值
哈工大資料結構實驗2——二叉樹存儲結構的建立、周遊和應用
哈工大2019秋資料結構期末試題
對于本次實驗，無非要解決的就是以下幾個問題：
- 用什麼資料結構去表示哈夫曼樹
- 如何構造哈夫曼樹
- 構造了哈夫曼樹之後如何根據哈夫曼樹将文本檔案進行哈夫曼編碼以及如何解碼
本文将逐一闡述上述問題如何解決
-
首先，來看一下哈夫曼樹的定義
定義:給定n個權值作為n個子葉節點，若樹的帶權路徑最短，則這課樹被稱為哈夫曼樹。
-
這裡要注意的幾個點有:
①隻有葉節點才有權重，非葉節點不存儲字元，也不帶權重
②什麼是帶全路徑?帶權路徑就是葉節點到根節點的路徑長度乘以葉節點所帶的權重。比如下面這個二叉樹的帶權路徑為:
2x10 + 2x20 + 2x50 + 2x100 = 360
③哈夫曼樹是帶權路徑最短的二叉樹。
3. 好的，現在你已經知道哈夫曼樹的定義，也了解了帶權路徑的定義。那麼我們現在的目标就是構造出最短帶權路徑的二叉樹。相信看到這裡你已經有了構思，對于權重越大的葉節點，如果它離根節點越近，那麼這個權重很大的葉節點對總的帶權路徑長度影響就越小。(right!)
比如對于上面的那個二叉樹，對于權重為100的節點，如果我們把它放在離根節點最近的地方，50這個節點放在離根節點次近的地方，那麼我們可以構造出一棵權重路徑更小的二叉樹。如圖所示。
這棵樹的權重路徑為: 1x100 + 2x50 + 3x20 + 3x10 = 100 + 100 + 60 + 30 = 290 < 350。
看到這裡，咱們的思路就清晰了，現在正式開始講具體步驟。
假設有n個權重，構造出n個葉節點，n個權重分别為w1,w2…wn,哈夫曼樹的構造規則如下:
- 将w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
- 在森林中選出根結點的權值最小的兩棵樹進行合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
- 從森林中删除選取的兩棵樹，并将新樹加入森林；
- 重複(02)、(03)步，直到森林中隻剩一棵樹為止，該樹即為所求得的哈夫曼樹。
以{5，6，7，8，15}為例，咱們試着構造一棵二叉樹。
① 首先選出權值最小的兩棵樹進行合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；也就是選出5和6，合并成11，剩下的樹的節點權重為{7,8,11,15}
②在剩下的樹的節點權重為{7,8,11,15}，選出最小的兩個權重{7,8}構造棵新樹，權重為15，剩下的節點權重為{11,15,15}
③同理，在剩下的節點權重為{11,15,15}選出{11,15}，構造新的節點，其權重為26，剩下的節點為{15，26}
④最後，選擇{15,26}構造根節點即可。
上述構造出的 二叉樹就是哈夫曼樹。
正确性證明點選這裡看即可，本篇不在闡述
好的，現在重新回到我們開始提出的三個問題。
1.用什麼資料結構去表示哈夫曼樹
首先，每個節點需要存儲權重，以及左右兒子，同時，為了講兩個節點合并構造一個新的父節點，我們也需要在每個節點存儲父節點。
最好的資料結構就是使用靜态三叉連結清單。
所有節點構成一個數組，節點的父子關系可以用數組下标表示。
#define N 53 //帶權重的n個葉子節點數,根據檔案中字元種類的個數來确定
#define M 2*N-1 //n個葉子節點的哈夫曼樹具有2*n-1個節點
typedef struct{
float weight;//權重
int lchild;//左兒子
int rchild;//右兒子
int parent;//父親
}node;//靜态三叉連結清單
typedef node huffman[M]; //哈夫曼樹
typedef char *huffmancode[N];//存儲每個字元的哈夫曼編碼表
2. 如何構造哈夫曼樹
我的思路是：
- 給定n個權重，那麼葉節點就有n個，非葉節點n-1個。那麼首先初始化n個葉節點，包括初始化葉節點的權重，左兒子、右兒子、父親初始化為-1。父親為-1表示一開始所有的葉節點還沒有選中來構造樹。
- 然後就開始選擇兩個葉節點來構造一個新的節點，這個節點的權重為兩個兒子的權重之和。選擇政策是：從所有的沒有父親的節點找出兩個權重最小的節點。這個功能我在函數selectmin中實作，其中參數s1,和s2傳遞的是引用，在函數内改變s1和s2的值，會直接改變函數外s1和s2的值。
具體實作如下:
void selectmin(huffman &T,int k,int &s1,int &s2)：選出權重最小的兩個節點
void selectmin(huffman &T,int k,int &s1,int &s2){//選出兩個權重最小的節點
int min=1000000,tmp=0;
for(int i=0;i<=k;i++){
if(T[i].parent==-1){
if(min>T[i].weight){
min=T[i].weight;
tmp=i;
}
}
}
s1=tmp;
min=100000;
tmp=0;
for(int j=0;j<=k;j++){
if((T[j].parent==-1)&&(j!=s1)){
if(min>T[j].weight){
min=T[j].weight;
tmp=j;
}
}
}
s2=tmp;
}
void CreatTree(huffman &T,float *w,int n) {//構造哈夫曼樹
if(n<=1)
return ;
int i;
for( i=0;i<n;i++){//初始化哈夫曼樹的n個葉節點并賦予權重
T[i].weight=w[i];
T[i].lchild=-1;
T[i].rchild=-1;
T[i].parent=-1;
}
for(;i<M;i++){ //初始化哈夫曼樹的非葉節點
T[i].weight=0;
T[i].lchild=-1;
T[i].rchild=-1;
T[i].parent=-1;
}
for(i=n;i<M;i++){
int s1=0,s2=0;
selectmin(T,i-1,s1,s2);//選出權重最小的葉節點
T[s1].parent=i;
T[s2].parent=i;
T[i].lchild=s1;
T[i].rchild=s2;
T[i].weight=T[s1].weight+T[s2].weight;
}
}
3.哈夫曼編碼
- 對于一棵哈夫曼樹來說，編碼方式就是：從根節點開始，往左走，就講路徑編碼為0，往右走就講路徑編碼為1，這樣從根節點到葉節點所經過的所有01串就是對應葉節點的哈夫曼編碼。如圖所示，那麼15:編碼為0，5：編碼為10，依次類推。
- 具體實作思路:對于每一個節點，都開始遞歸的找父親節點(直到找到根節點停止遞歸)，如果這個節點是父親的右兒子，則編碼為1，否則編碼為0。将編碼01儲存在一個臨時的數組cd内即可。字元串數組HT[i]存儲了第i個葉節點的編碼01串。
void bianma(huffman T,huffmancode &HT){//對每個葉節點進行編碼
char cd[N];//臨時儲存每個節點的哈夫曼編碼
cd[N-1]='\0';
int start,c,f;
for(int i=0;i<N;i++){
start=N-1;
c=i;
f=T[i].parent;
while(f!=-1){
if(T[f].lchild==c){
cd[--start]='0';
}
else{
cd[--start]='1';
}
c=f;
f=T[f].parent;//遞歸查找
}
HT[i]=(char*)malloc((N-start)*sizeof(char));
strcpy(HT[i],&cd[start]);
}
}
void yasuo(huffmancode HC,char ch[]){//将英文檔案壓縮為哈夫曼編碼檔案
fstream in,out;
in.open("hafuman.txt"); //打開英文檔案
out.open("bianma.txt"); //打開要壓縮的哈夫曼編碼檔案
char a[100000];
in.getline(a,100001);//讀出英文檔案的内容
int len1=strlen(a);
int len2=strlen(ch);
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(ch[j]==a[i]){
out<<HC[j];//将每個字元的哈夫曼編碼輸入到哈夫曼編碼檔案中
cout<<HC[j];
}
}
}
in.close() ;//關閉檔案
out.close() ; //關閉檔案
}
4.哈夫曼解碼
哈夫曼解碼：根據01串，從根節點開始在哈夫曼樹搜尋，0就往左走1就往右走，直到走到根節點為止。
void jiema(huffman T,char *ch,char test[],char *result) {
int p=M-1;//根節點
int i=0;//訓示串的第i個字元
int j=0;//解碼出的第j個字元
int len=strlen(test);
while(i<len){
if(test[i]=='0'){
p=T[p].lchild;
}
if(test[i]=='1'){
p=T[p].rchild;
}
if(p<N){//說明此時為葉節點
result[j]=ch[p];
j++;
p=M-1;//重新指向根節點
}
i++;
}
result[j]='\0';
}
void jiemawenjian(huffman T,char *ch){//将從檔案讀入的哈夫曼編碼解碼為英文檔案
fstream in,out;
in.open("bianma.txt");
out.open("hafumanbianma.txt");
char a[100000];
in.getline(a,100001);
char c[100000] ;
jiema(T,ch,a,c);
out<<c;
// cout<<"哈夫曼編碼檔案中的内容為:"<<endl;
// cout<<a<<endl;
cout<<"解壓為英文檔案後的内容為："<<endl;
cout<<c<<endl;
in.close();
out.close();
}
void dayincode(huffmancode HC,char ch[]){//列印哈夫曼樹的葉節點對應的編碼
cout<<endl;
cout<<"每個字元的哈夫曼編碼為："<<endl<<endl;
cout<<"字元"<<"\t"<<"\t"<<"哈夫曼編碼"<<"\t"<<"\t"<<endl;
for(int i=0;i<N;i++){
cout<<ch[i]<<"\t"<<"\t"<<HC[i]<<"\t"<<"\t"<<endl;
}
cout<<endl;
}
void dayinshu(huffman T,char ch[]){
cout<<endl;
cout<<"節點"<<"\t"<<"\t"<<"字元"<<"\t"<<"\t"<<"權重"<<"\t"<<"\t"<<"父親 "<<"\t"<<"\t"<<"左兒子"<<"\t"<<"\t"<<"右兒子"<<"\t"<<"\t"<<endl;
for(int i=0;i<M;i++){
if(i<N){ cout<<i<<"\t"<<"\t"<<ch[i]<<"\t"<<"\t"<<setprecision(9)<<T[i].weight<<"\t"<<"\t"<<T[i].parent<<"\t"<<"\t"<<T[i].lchild<<"\t"<<"\t"<<T[i].rchild<<"\t"<<"\t"<<endl;
}
else{
cout<<i<<"\t"<<"\t"<<"-1"<<"\t"<<"\t"<<T[i].weight<<"\t"<<"\t"<<T[i].parent<<"\t"<<"\t"<<T[i].lchild<<"\t"<<"\t"<<T[i].rchild<<"\t"<<"\t"<<endl;
}
}
}
main函數
int main(){
huffman T;
char a[10000];//讀取檔案中的字元個數
fstream in;
in.open("hafuman.txt");//打開檔案
if(in.fail() ){//判斷是否成功打開檔案
cout<<"error"<<endl;
}
else{
in.getline(a,10001);//從檔案讀入10000個字元
}
cout<<"從檔案讀入的字元總數為："<<strlen(a)<<endl;
int x=strlen(a);
int len[1000]={0};
for(int i=0;i<x;i++){//将讀入的字元頻數記錄下來
int m=int(a[i]);
len[m]++;//字元ascall碼為m的字元頻數
}
int g=0;//記錄字元個數
char ch[1000];//每個字元
for(int i=0;i<x;i++){
if(len[i]!=0){
ch[g]=char(i);//将字元ascall碼轉化為字元并儲存在字元數組中
g++;
}
}
cout<<"檔案中的不同的字元個數為："<<g<<endl;
int str[1000];//字元出現的頻數
int k=0;
for(int i=0;i<x;i++){
if(len[i]!=0){
str[k]=len[i];
k++;
}
}
str[k]='\0';//字元出現的頻數
ch[k]='\0';
float w[1000];//字元頻率
int t=strlen(ch);
cout<<"字元\t"<<"\t"<<"頻數\t"<<"\t"<<"權重\t"<<"\t"<<endl;
for(int i=0;i<t;i++){
w[i]=(float(str[i]))/x;
cout<<ch[i]<<"\t"<<"\t"<<str[i]<<"\t"<<"\t"<<w[i]<<"\t"<<"\t"<<endl;
}
w[t]='\0';
in.close() ;
CreatTree(T,w,N);//建構哈夫曼樹
dayinshu(T,ch); //列印哈夫曼樹
huffmancode HC;//建構哈夫曼編碼
bianma(T,HC);//對哈夫曼樹進行編碼
dayincode(HC,ch);//列印每個葉節點的編碼
float sum=0.0;//哈夫曼樹平均編碼長度
for(int i=0;i<N;i++){
sum+=strlen(HC[i])*w[i];
}
cout<<"哈夫曼樹平均編碼長度為"<<sum<<endl;
cout<<"哈夫曼樹的壓縮率為："<<1 - sum / 8<<endl;
int n=0;
cout<<"-------------------------------------------"<<endl;
cout<<"0.退出 |"<<endl;
cout<<"1.将英文檔案進行壓縮為哈夫曼編碼檔案并顯示 |" <<endl;
cout<<"2.将哈夫曼編碼檔案解壓為英文檔案并顯示 |"<<endl;
cout<<"3.比較英文檔案和解壓後的英文檔案 |"<<endl;
cout<<"-------------------------------------------|"<<endl;
cin>>n;
while(n){
switch(n){
case 1:
cout<<"哈夫曼編碼檔案為："<<endl;
yasuo(HC,ch);//将英文檔案壓縮為哈夫曼編碼檔案
break;
case 2:
jiemawenjian(T,ch);//将從檔案讀入的哈夫曼編碼解壓為英文檔案
break;
case 3:
cout<<"讀入的檔案内容為:"<<endl;
cout<<a<<endl<<endl<<endl;
jiemawenjian(T,ch);
case 0:
n=0;
break;
default :
break;
}
cout<<"-------------------------------------------"<<endl;
cout<<"0.退出 |"<<endl;
cout<<"1.将英文檔案進行壓縮為哈夫曼編碼檔案并顯示 |" <<endl;
cout<<"2.将哈夫曼編碼檔案解壓為英文檔案并顯示 |"<<endl;
cout<<"3.比較英文檔案和解壓後的英文檔案 |"<<endl;
cout<<"-------------------------------------------|"<<endl;
cin>>n;
}
5.最終結果展示
- 從檔案中讀入任意一篇英文文本檔案，分别統計英文文本檔案中各字元（包括标點符号和空格）的使用頻率；
讀入的英文文本檔案：
- 統計各個字元的使用頻率
哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 - 根據已統計的字元使用頻率構造哈夫曼編碼樹，并給出每個字元的哈夫曼編碼（字元集的哈夫曼編碼表）；
哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 - 每個字元的哈夫曼編碼
哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 - 将文本檔案利用哈夫曼樹進行編碼，存儲成壓縮檔案（哈夫曼編碼檔案）；
哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 - 計算哈夫曼編碼檔案的壓縮率
哈工大資料結構實驗二——哈夫曼編碼與譯碼方法對于本次實驗，無非要解決的就是以下幾個問題：别忘了點個關注 - 将哈夫曼編碼檔案譯碼為文本檔案，并與原檔案進行比較。
讀入的英文文本檔案：
哈夫曼編碼檔案的譯碼檔案：