7-6 哈夫曼编码 (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} 就不是哈夫曼编码，因为用这套编码压缩得到 0000 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。

输入样例：
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

讯享网

说明：我用的编译器是codblocks，可能有些地方其他编译器不太支持，下次会多加注意

思路：
首先利用数组法创建出一棵哈夫曼树（即每次寻找最小的两个根结点，并进行n-1次合并）
创建树的结构体类型

struct HTnode{ 
    char data; int weight; int lchild,rchild,parent; int way_length; }; 

具体初始化以及合并过程

讯享网HTnode H_Tree[1000]; int n; cin>>n; for(int i = 0 ; i < n; i ++){ 
    cin>>H_Tree[i].data; cin>>H_Tree[i].weight; H_Tree[i].parent=-1; H_Tree[i].lchild=-1; H_Tree[i].rchild=-1; } int i;//for iter for( i = 0 ; i < n-1 ; i ++){ 
    int j; for (j=0;j<n+i;j++){ 
    if(H_Tree[j].parent==-1) break; } int min1=j; for (int k=0;k<n+i;k++){ 
    if(H_Tree[min1].weight>H_Tree[k].weight&&H_Tree[k].parent==-1) min1=k; } H_Tree[min1].parent=n+i; for (j=0;j<n+i;j++){ 
    if(H_Tree[j].parent==-1) break; } int min2=j; for (int k=0;k<n+i;k++){ 
    if(H_Tree[min2].weight>H_Tree[k].weight&&H_Tree[k].parent==-1) min2=k; } H_Tree[min2].parent=n+i; H_Tree[n+i].weight=H_Tree[min1].weight+H_Tree[min2].weight; H_Tree[n+i].parent=-1; H_Tree[n+i].lchild=min1; H_Tree[n+i].rchild=min2; } 

下生成基于以上创造的哈夫曼树的哈夫曼编码
第一步：计算每个叶子结点到根结点的距离
第二步：∑距离×权值=加权路径长度
（这里我写的代码合并为了一步）

 int short_way=0; for(i = 0 ; i < n ; i ++){ 
    H_Tree[i].way_length=0; int temp=i; while(H_Tree[temp].parent!=-1){ 
    H_Tree[i].way_length++; temp=H_Tree[temp].parent; } short_way+=H_Tree[i].weight*H_Tree[i].way_length; } 

由于一次需要测试多组数据，所以建立一个判断函数，这样程序逻辑看起来更加清楚。
下创建flag函数
函数主要分为两部分
第一部分判断主函数中创造的哈夫曼编码的带权路径是否等于测试编码的带权路径，如果不等，直接return 0即可，否则需做第二步判断。
第二部分还需继续判断是否含有前缀重叠现象（即短码是长码的前缀）
首先需要建立一个vist辅助数组，来标记下是否被访问过。
具体操作过程为：
总共比较n次
找到n个中没有被vist标记过的长度最短的码（记为码1）
（提示：strlen函数）
对码1进行vist标记（表示访问过）
下判断码1是否为其他的没有被vist标记过的长码的前缀，若是，直接return 0即可。
（提示：strncmp函数）
最后，return 1；

讯享网int flag(HTnode H_Tree[100],int short_way,int n){ 
    char coding[100][100]; char c[100]; for(int i = 0 ; i < n ; i ++){ 
    cin>>c[i]; cin>>coding[i]; } int short_way1=0; for(int i = 0; i < n ; i ++){ 
    for(int j = 0; j < n; j++) if(H_Tree[i].data==c[j]){ 
    short_way1+=H_Tree[i].weight*strlen(coding[j]); break; } } if(short_way1 != short_way) return 0; //下判断是否含有前缀重叠 int vist[1000]={ 
   0}; int min; for(int i = 0; i< n ; i++){ 
    for(int j = 0;j <n ; j++){ 
    if(!vist[j]){ 
    min=j; break;} } for(int j = 0; j < n ; j ++){ 
    if(strlen(coding[j])<strlen(coding[min])&&!vist[j]) min=j; } vist[min]=1; for(int j = 0;j<n ; j ++){ 
    if(!strncmp(coding[min],coding[j],strlen(coding[min]))&&!vist[j]) return 0; } } return 1; } 

最后一步，将每组测试代码的判断结果以一个flag的数组进行保存，最终进行统一输出，这道题目也就完成了。

 int count; cin>>count; int flag1[10000]; for(int k = 0; k < count ; k ++){ 
    flag1[k]=flag(H_Tree,short_way,n); } for(int k = 0; k < count ; k ++){ 
    if(flag1[k]) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; } 

所有测试点
比较坑的一个点是第3个点，注意要把hfm数组和flag建立的足够大，才能通过测试点（虽然这个测试点只有1分）
这次代码写的比较匆忙，因此没有写注释，再汇总一下所有代码

讯享网#include<bits/stdc++.h> using namespace std; struct HTnode{ 
    char data; int weight; int lchild,rchild,parent; int way_length; }; int flag(HTnode H_Tree[100],int short_way,int n){ 
    char coding[100][100]; char c[100]; for(int i = 0 ; i < n ; i ++){ 
    cin>>c[i]; cin>>coding[i]; } int short_way1=0; for(int i = 0; i < n ; i ++){ 
    for(int j = 0; j < n; j++) if(H_Tree[i].data==c[j]){ 
    short_way1+=H_Tree[i].weight*strlen(coding[j]); break; } } if(short_way1 != short_way) return 0; //下判断是否含有前缀重叠 int vist[1000]={ 
   0}; int min; for(int i = 0; i< n ; i++){ 
    for(int j = 0;j <n ; j++){ 
    if(!vist[j]){ 
    min=j; break;} } for(int j = 0; j < n ; j ++){ 
    if(strlen(coding[j])<strlen(coding[min])&&!vist[j]) min=j; } vist[min]=1; for(int j = 0;j<n ; j ++){ 
    if(!strncmp(coding[min],coding[j],strlen(coding[min]))&&!vist[j]) return 0; } } return 1; } int main(){ 
    HTnode H_Tree[1000]; int n; cin>>n; for(int i = 0 ; i < n; i ++){ 
    cin>>H_Tree[i].data; cin>>H_Tree[i].weight; H_Tree[i].parent=-1; H_Tree[i].lchild=-1; H_Tree[i].rchild=-1; } int i;//for iter for( i = 0 ; i < n-1 ; i ++){ 
    int j; for (j=0;j<n+i;j++){ 
    if(H_Tree[j].parent==-1) break; } int min1=j; for (int k=0;k<n+i;k++){ 
    if(H_Tree[min1].weight>H_Tree[k].weight&&H_Tree[k].parent==-1) min1=k; } H_Tree[min1].parent=n+i; for (j=0;j<n+i;j++){ 
    if(H_Tree[j].parent==-1) break; } int min2=j; for (int k=0;k<n+i;k++){ 
    if(H_Tree[min2].weight>H_Tree[k].weight&&H_Tree[k].parent==-1) min2=k; } H_Tree[min2].parent=n+i; H_Tree[n+i].weight=H_Tree[min1].weight+H_Tree[min2].weight; H_Tree[n+i].parent=-1; H_Tree[n+i].lchild=min1; H_Tree[n+i].rchild=min2; } int short_way=0; for(i = 0 ; i < n ; i ++){ 
    H_Tree[i].way_length=0; int temp=i; while(H_Tree[temp].parent!=-1){ 
    H_Tree[i].way_length++; temp=H_Tree[temp].parent; } short_way+=H_Tree[i].weight*H_Tree[i].way_length; } int count; cin>>count; int flag1[10000]; for(int k = 0; k < count ; k ++){ 
    flag1[k]=flag(H_Tree,short_way,n); } for(int k = 0; k < count ; k ++){ 
    if(flag1[k]) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }