2019.12.15更正Best函數樣本數據初始化問題并且對代碼添加了注釋;
2020.11.17更正：題目說明；
原貼發于2019.11.22
注意：本題不是哈夫曼編碼裸題，學習哈夫曼編碼的同學不要過度依賴本題算法，只有參考價值；
給定一段文字，如果我們統計出字母出現的頻率，是可以根據哈夫曼算法給出一套編碼，使得用此編碼壓縮原文可以得到最短的編碼總長。然而哈夫曼編碼并不是唯一的。例如對字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出現頻率對應為 4、2、1、1。我們可以設計編碼 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，還可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套編碼都可以把原文壓縮到 14 個字節。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼編碼，因為用這套編碼壓縮得到 00001011001001 后，解碼的結果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以對應解碼的結果。本題就請你判斷任一套編碼是否哈夫曼編碼。

輸入格式：
首先第一行給出一個正整數 N（2≤N≤63），隨后第二行給出 N 個不重復的字符及其出現頻率，格式如下：

c[1] f[1] c[2] f[2] … c[N] f[N]

其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出現頻率，為不超過 1000 的整數。再下一行給出一個正整數 M（≤1000），隨后是 M 套待檢的編碼。每套編碼占 N 行，格式為：

c[i] code[i]

其中c[i]是第i個字符；code[i]是不超過63個’0’和’1’的非空字符串。

輸出格式：
對每套待檢編碼，如果是正確的哈夫曼編碼，就在一行中輸出"Yes"，否則輸出"No"。

注意：最優編碼并不一定通過哈夫曼算法得到。任何能壓縮到最優長度的前綴編碼都應被判為正確。

輸入樣例：

7 A 1 B 1 C 1 D 3 E 3 F 6 G 6 4 A 00000 B 00001 C 0001 D 001 E 01 F 10 G 11 A 01010 B 01011 C 0100 D 011 E 10 F 11 G 00 A 000 B 001 C 010 D 011 E 100 F 101 G 110 A 00000 B 00001 C 0001 D 001 E 00 F 10 G 11

輸出樣例：

Yes Yes No No

思路：這道題應該是樹這塊比較綜合的一道，題目的注意很重要，他直接給了我們一個方向：最優編碼不一定是由哈夫曼算法得到的，并且哈夫曼編碼的結果不是惟一的，這就意味著構造哈夫曼樹進行哈夫曼編碼的方式是不適用了。
經過老師的提醒，這道題應該這樣做：（1）判斷題目所給的是不是前綴編碼，即翻譯過程中會不會產生歧義；（2）編碼是不是最優的。
為此我寫了兩個函數；

bool judge(int start,int end) //判斷是否是前綴編碼 {for (int i=start;i<=end;i++){for (int j=start;j<=end;j++){if (i==j){continue;}if (strlen(in[i].code)>strlen(in[j].code)){continue;}int k;for (k=0;k<strlen(in[i].code);k++){if (in[i].code[k]!=in[j].code[k]){break;}}if (k>=strlen(in[i].code)){return false;}}}return true; } bool best(int start,int end) //哈夫曼編造樹，求加權最短路徑看是否相等 {Create self[131];int it=0; //輸入的帶權路徑和 int m=2*n-1;for (int i=start;i<=end;i++){it+=in[i].weight*in[i].P;}for (int i=0;i<n;i++){self[i].parent=self[i].lchild=self[i].rchild=-1;self[i].weight=in[start++].P;}for (int i=n;i<m;i++){self[i].parent=self[i].lchild=self[i].rchild=-1;self[i].weight=0;}int x1,x2;for (int i=n;i<m;i++){Find(self,&x1,&x2,i); //printf("&&%d %d %d %d&&\n",x1,x2,self[x1].weight,self[x2].weight);self[i].lchild=x1;self[i].rchild=x2;self[i].weight=self[x1].weight+self[x2].weight;self[x1].parent=i;self[x2].parent=i;}int itt=0;for (int i=n;i<m;i++){ //printf("##%d##\n",self[i].weight);itt+=self[i].weight;} //printf("***%d %d***\n",it,itt);if (it==itt) return true;else return false; }void Find(Create *self,int *x1,int *x2,int count) //尋找最小值下標和次小值下標 { //printf("//%d//\n",count);int min=130,pmin=130;self[min].weight=10000001;for (int i=0;i<count;i++){if (self[i].parent==-1&&self[i].weight<self[min].weight){pmin=min;min=i;}else if (self[i].parent==-1&&self[i].weight<self[pmin].weight){pmin=i;}}*x1=min;*x2=pmin; }

當所給的代碼符合這兩個條件時就是正確的哈夫曼編碼。

#include <bits/stdc++.h> #include <queue> using namespace std; int n; struct knot {char name; //字符 int P; //出現概率int weight; //輸入串長 char code[65]; //編碼 }a[6400],in[63001]; //a用name和P，in用name、weight(碼的長度)和code typedef struct knoto {int parent;int lchild,rchild;int weight; }Create; bool judge(int start,int end); //判斷是否有歧義,start是起始下標，end是結束下標 bool best(int start,int end); //獲取最優輸入 void Find(Create *self,int *x1,int *x2,int count); int main() {int k,itt;scanf("%d",&n);for (int i=0;i<n;i++){getchar();scanf("%c%d",&a[i].name,&a[i].P);}scanf("%d",&k); //組數 for (int i=0;i<k*n;i++){getchar();scanf("%c %s",&in[i].name,in[i].code);in[i].weight=strlen(in[i].code);in[i].P=a[i%n].P;if (i%n==n-1) //一組輸入完畢,i是從0開始的 {if (judge(i-n+1,i)&&best(i-n+1,i)){printf("Yes\n");}else{printf("No\n");}}}return 0; }bool judge(int start,int end) //此函數的功能是判斷一組輸入的編碼是不是前綴編碼，即在 { //組內比較 for (int i=start;i<=end;i++){for (int j=start;j<=end;j++){if (i==j) //如果是一個碼，不用比 {continue;}if (strlen(in[i].code)>strlen(in[j].code)) //i的碼比j的碼長，i不可能是j編碼的一部分 {continue;}int k;for (k=0;k<strlen(in[i].code);k++) //正式進入比較 {if (in[i].code[k]!=in[j].code[k]){break; //注意這里不能直接寫return true,否則會犯比較不足的錯誤 }}if (k>=strlen(in[i].code)) //順利結束，表明這不是前綴編碼，即有重復 {return false;}}}return true; //坎坷之后，才是真正的編碼 }bool best(int start,int end) //哈夫曼編造樹，求加權最短路徑看是否相等 {Create self[131];int it=0; //輸入的帶權路徑和 int m=2*n-1;for (int i=start;i<=end;i++) //計算輸入的帶權路徑和 {it+=in[i].weight*in[i].P;}for (int i=0;i<n;i++) //對已有的樣本數據進行存儲，靜態實現， {self[i].parent=self[i].lchild=self[i].rchild=-1;self[i].weight=a[i].P;}for (int i=n;i<m;i++) //這是對空間進行初始化，沒有孩子，沒有雙親，沒有權值 {self[i].parent=self[i].lchild=self[i].rchild=-1;self[i].weight=0;}int x1,x2; //保存權值最小值和次小值的數組下標 for (int i=n;i<m;i++) //從第一個不是原有數據的儲存空間開始 {Find(self,&x1,&x2,i);self[i].lchild=x1;self[i].rchild=x2; //孩子初始化 self[i].weight=self[x1].weight+self[x2].weight; //權值刷新 self[x1].parent=i; //雙親刷新 self[x2].parent=i;}int itt=0; //計算 for (int i=n;i<m;i++){itt+=self[i].weight;}if (it==itt) return true;else return false; }void Find(Create *self,int *x1,int *x2,int count) //可用stl最小堆優化 {int min=130,pmin=130; //需要保證節點不會累加到此處 self[min].weight=10000001;for (int i=0;i<count;i++){if (self[i].parent==-1&&self[i].weight<self[min].weight){pmin=min;min=i;}else if (self[i].parent==-1&&self[i].weight<self[pmin].weight){pmin=i;}}*x1=min;*x2=pmin; }

總結

以上是生活随笔為你收集整理的7-2 哈夫曼编码 (30 分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。