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.
Input Specification: 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 (≤1000), 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.
Output Specification: 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.
Sample Input:
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 11Sample Output:
Yes Yes No No思路： 1.利用vector的push，pop和STL带的sort函数模拟最小堆，计算得到给定编码的WPL，检查学生输入的编码总长是否等于WPL； 2.对学生输入的编码建立二叉树，检查每个编码是否都在二叉树叶子节点上； 3.若1和2条件都满足输出Yes，否则输出No。
#include<iostream> #include<vector> #include<algorithm> using namespace std; struct Node{ char data; int fre; }; struct TNode{ struct TNode *left; struct TNode *right; }; bool cmp(int a, int b){ return a > b; } TNode* NewNode(){ TNode *root = new TNode; root->left = NULL; root->right = NULL; return root; } bool Check(TNode *root, string s){ bool flag = 0; for(int i = 0; i < s.size(); i++){ if(s[i] == '0'){ if(!root->left){ root->left = NewNode(); root = root->left; if(i == s.size() - 1){ flag = 1; } } else{ root = root->left; } } else if(s[i] == '1'){ if(!root->right){ root->right = NewNode(); root = root->right; if(i == s.size() - 1){ flag = 1; } } else{ root = root->right; } } } return flag; } int main(){ int n1, n2; Node temp; int wpl = 0; scanf("%d", &n1); vector<Node> v1; vector<int> v2; for(int i = 0; i < n1; i++){ scanf(" %c %d", &temp.data, &temp.fre); v1.push_back(temp); v2.push_back(temp.fre); } int size = v2.size(); while(size > 1){ sort(v2.begin(), v2.end(), cmp); int t = v2[size - 1] + v2[size - 2]; wpl += t; v2.pop_back(); v2.pop_back(); v2.push_back(t); size = v2.size(); } scanf("%d", &n2); for(int i = 0; i < n2; i++){ int wplCheck = 0; int flag = 1; TNode *root = NewNode(); for(int j = 0; j < n1; j++){ char data; string s; cin>>data>>s; wplCheck += v1[j].fre * s.size(); if(!Check(root, s)){ flag = 0; } } if(wplCheck != wpl){ flag = 0; } if(flag){ printf("Yes\n"); } else{ printf("No\n"); } } return 0; }参考代码 蓝桥杯BASIC-28 基础练习 Huffuman树 05-树9 Huffman Codes及基本操作
