PTA7-2哈夫曼编码（30分）
PTA 7-2 哈夫曼编码 (30分)
给定⼀段⽂字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出⼀套编码，使得⽤此编码压缩原⽂可以得到最短的编码总长。然⽽哈夫曼编码并不是唯⼀的。例如对字符串"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
【程序思路】
这⾥主要利⽤哈夫曼编码的两个性质：
哈夫曼编码可能不唯⼀，但是哈夫曼编码的长度是唯⼀的。字符串编码成01串后的长度实际上就是其以频率为权值所构成的任意⼀颗哈夫曼树的带权路径长度。
对于任何⼀个叶⼦结点，其编号⼀定不会成为其他任何⼀个结点编号的前缀—也就是说，题⽬中给出需要判断的的每个字符的编码，它不会是其他字符编码的前缀。
即可AC
【程序实现】
#include<bits/stdc++.h>
using namespace std;
int main(){
int s = 0, n, m, x, a[100];
char ch;
priority_queue<int,vector<int>,greater<int> > q; //优先队列
cin>>n;getchar();
for(int i = 0; i < n; i++) {
cin>>ch>>x;
a[i] = x;
q.push(x);
}
while(q.size() > 1) {
int x = q.top();
q.pop();
int y = q.top();
q.pop();
s = s + x + y;
q.push(x + y);
}
cin>>m;
while(m--) {
int s1 = 0;
string str[100];
for(int i = 0; i < n; i++) {
cin>>ch>>str[i];
s1 = s1 + str[i].size() * a[i];
}
if(s == s1) {
bool jdg = true;
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n; j++) {
int flag = 0;
int size = str[i].size() > str[j].size() ? str[j].size() : str[i].size();                    for(int k = 0; k < size; k++)
if(str[i][k] != str[j][k])
flag = 1;
if (!flag)
jdg = false;
}
}
if(jdg)
cout<<"Yes\n";
else
cout<<"No\n";
}
else
cout<<"No\n";
}
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。