In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters ‘a‘, ‘x‘, ‘u‘ and ‘z‘ are 4, 2, 1 and 1, respectively. We may either encode the symbols as {‘a‘=0, ‘x‘=10, ‘u‘=110, ‘z‘=111}, or in another way as {‘a‘=1, ‘x‘=01, ‘u‘=001, ‘z‘=000}, both compress the string into 14 bits. Another set of code can be given as {‘a‘=0, ‘x‘=11, ‘u‘=100, ‘z‘=101}, but {‘a‘=0, ‘x‘=01, ‘u‘=011, ‘z‘=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.
Each input file contains one test case. For each case, the first line gives an integer N (2 <= N <= 63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:
c[1] f[1] c[2] f[2] ... c[N] f[N]
where c[i] is a character chosen from {‘0‘ - ‘9‘, ‘a‘ - ‘z‘, ‘A‘ - ‘Z‘, ‘_‘}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (≤), then followed by M student submissions. Each student submission consists of N lines, each in the format:
c[i] code[i]
where c[i] is the i-th character and code[i] is an non-empty string of no more than 63 ‘0‘s and ‘1‘s.
For each test case, print in each line either "Yes" if the student‘s submission is correct, or "No" if not.
Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.
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
#include<iostream> #include<cstring> using namespace std; const int maxn = 1010; typedef struct TreeNode* Tree; struct TreeNode { Tree left,right; int weight; }; typedef struct HeapNode* Heap; struct HeapNode { TreeNode Data[maxn]; int size; }; int n,m; int w[maxn]; char ch[maxn]; int codelen; int cnt2,cnt0; Tree creatTree(); Heap creatHeap(); void Insert(Heap H, TreeNode T); Tree Huffman(Heap H); Tree Delete(Heap H); int WPL(Tree T, int depth); bool Judge(); void JudgeTree(Tree T); int main() { cin >> n; Tree T = creatTree(); Heap H = creatHeap(); for (int i = 0; i < n; i++) { getchar(); cin >> ch[i] >> w[i]; H->Data[H->size].left = H->Data[H->size].right = NULL; T->weight = w[i]; Insert(H,*T); } T = Huffman(H); codelen = WPL(T,0); //printf("%d\n",codelen); cin >> m; while (m--) { if (Judge()) { printf("Yes\n"); } else { printf("No\n"); } } return 0; } Tree creatTree() { Tree T = new TreeNode; T->left = T->right = NULL; T->weight = 0; return T; } Heap creatHeap() { Heap H = new HeapNode; H->Data[0].weight = -1; H->size = 0; return H; } void Insert(Heap H, TreeNode T) { int i = ++H->size; for (; H->Data[i/2].weight > T.weight; i /= 2) { H->Data[i] = H->Data[i/2]; } H->Data[i] = T; } Tree Huffman(Heap H) { Tree T = creatTree(); while (H->size > 1) { T->left = Delete(H); T->right = Delete(H); T->weight = T->left->weight + T->right->weight; Insert(H,*T); } T = Delete(H); return T; } Tree Delete(Heap H) { int parent,child; TreeNode Tmp = H->Data[H->size--]; Tree T = creatTree(); *T = H->Data[1]; for (parent = 1; 2*parent <= H->size; parent = child) { child = 2*parent; if (child < H->size && H->Data[child+1].weight < H->Data[child].weight) { child++; } if (H->Data[child].weight > Tmp.weight) { break; } H->Data[parent] = H->Data[child]; } H->Data[parent] = Tmp; return T; } int WPL(Tree T, int depth) { if (!T->left && !T->right) { return depth * (T->weight); } else { return WPL(T->left,depth+1) + WPL(T->right,depth+1); } } bool Judge() { char s1[maxn],s2[maxn]; bool flag = true; Tree T = creatTree(); Tree pt = NULL; int wgh; for (int i = 0; i < n; i++) { cin >> s1 >> s2; if (strlen(s2) > n) { return 0; } int j; for (j = 0; ch[j] != s1[0]; j++) { ; } wgh = w[j]; pt = T; for (j = 0; s2[j]; j++) { if (s2[j] == ‘0‘) { if (!pt->left) { pt->left = creatTree(); } pt = pt->left; } if (s2[j] == ‘1‘) { if (!pt->right) { pt->right = creatTree(); } pt = pt->right; } if (pt->weight) { flag = false; } if (!s2[j+1]) { if (pt->left || pt->right) { flag = false; } else { pt->weight = wgh; } } } } if (!flag) { return 0; } cnt0 = cnt2 = 0; JudgeTree(T); if (cnt2 != cnt0-1) { return 0; } if (codelen == WPL(T,0)) { return 1; } else { return 0; } } void JudgeTree(Tree T) { if (T) { if (!T->left && !T->right) { cnt0++; } else if(T->left && T->right) { cnt2++; } else { cnt0 = 0; } JudgeTree(T->left); JudgeTree(T->right); } }
原文：https://www.cnblogs.com/wanghao-boke/p/11783768.html