浙大数据结构：05-树9 Huffman Codes

这道题难度挺大，写起来较为费劲，这里我依然使用了STL库，使得代码量大幅减少不过百行，便于大家理解。

机翻：

1、条件准备

数组存储字符对应频率，n,student存储输入多少字符，有多少学生测试。

wpl为最小带权路径长度，后边用到了multiset，分别来算最小带权路径长度和判断学生数据是否成立。后面看到代码再细说。

#include <iostream>
#include<string>
#include <set>
using namespace std;int num[128];//存储字符对应的频率
int n,student;//输入多少字符，有多少学生
int wpl;    //带权路径长度
multiset<pair<int,int>> s;//用来算最小的带权路径长度
multiset<string> se;//用来验证输入的数据是否符合要求

主函数较为简单，先初始化一下，然后计算最小带权路径，然后输入学生，循环判断每个学生是否符合要求

int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);init();wpl=minwpl();cin>>student;for(int i=0;i<student;i++){judge(wpl);}return 0;
}

2、init函数

输入字符数，然后存储字符和其频率，用num数组存储。

s集合存入数据对，第一个为出现的频率，第二个为0.具体含义后面再说。

void init()
{cin>>n;for(int i=1;i<=n;i++){char c;int a;cin>>c>>a;s.insert({a,0});num[c]=a;}
}

3、minwpl函数

如何计算最小带权路径长度呢？我们用哈夫曼树的构造方式来模拟：先取最小的两个合并成一个新的建立小子树，再从堆里选两个，以此类推直到最后合并成一棵树。但是这样只能生成带权路径最小的树，并没有算出带权路径是多少，我们这里采用数据对第二位来保存以该结点为根结点的最小带权路径，经过递推可以算出最终结果。我们具体来看一下。

先取堆顶放入左结点，删除堆顶再取堆顶放入右结点，删除堆顶。接下来准备插入t。

t的权值放在第一位，很好求，左右结点权值相加即可，

t为根节点的wpl初始也为左右结点权值相加，然后判断这个结点是否是后天计算的（非原始的），即第二位不为0，那么就加一下它的第二位，这样能使得权值较小的被多次相加也就算出了WPL.

这里建议画几颗树推一下，否则不是很好理解（我也是想半天想到的）

int minwpl()
{if(s.size()==1)return s.begin()->second;
//递归终点，就剩一个点了，就是根节点pair<int,int> left=*s.begin();//取最小s.erase(s.begin());//删除堆顶pair<int,int> right=*s.begin();//取最小s.erase(s.begin());//删除堆顶pair<int,int> t={left.first+right.first,left.first+right.first};
//建立新的结点if(left.second)t.second+=left.second;if(right.second)t.second+=right.second;s.insert(t);//插入return minwpl();//继续递归
}

4、judge函数

对于每个学生的数据，我们直接用每个字符的编码长度*该字符的权值再累加和求出wpl与我们的wpl进行比较即可。

如何判断前缀码是否有重的呢？我把每个输入的编码的所有前缀码存入集合se中，如果有字符的编码能在其中找到则前缀代码有问题，f=1。

最后输出。

PS:这里有个小bug，应该存一下所有编码最后再判断，但这题依然AC了

void judge(int miwpl)//判断wpl、是否重了,输出
{int w=0; //算当前student的wpl
se.clear();//清空一下
int f=0;//判断是否前缀码有重的for(int i=0;i<n;i++){char c;string s;cin>>c>>s;w+=s.size()*num[c];//算wplif(se.find(s)!=se.end())f=1;//不为其它函数的前缀码
//其实这里有bug，应该所有前缀码输入完再一个个判断，但这题还能ACse.insert(s); for(int j=1;j<=s.size();j++){se.insert(s.substr(0,j));//插入可能的前缀}}if(w!=miwpl){cout<<"No"<<endl;return ;}if(f){cout<<"No"<<endl;return ;}cout<<"Yes"<<endl;
}

5、总结

这道题难度非常大，我做了一下午，做完后发现网上很多代码都用C语言实现的，200行左右，我便把C++实现给大家分享一下，主要是给大家提供一些新的思路。

完整代码如下：

#include <iostream>
#include <string>
#include <set>
using namespace std;int num[128];
int n, student;
int wpl;
multiset<pair<int, int>> s;
multiset<string> se;
void init()
{cin >> n;for (int i = 1; i <= n; i++){char c;int a;cin >> c >> a;s.insert({a, 0});num[c] = a;}
}int minwpl()
{if (s.size() == 1)return s.begin()->second;pair<int, int> left = *s.begin();s.erase(s.begin());pair<int, int> right = *s.begin();s.erase(s.begin());pair<int, int> t = {left.first + right.first, left.first + right.first};if (left.second)t.second += left.second;if (right.second)t.second += right.second;s.insert(t);return minwpl();
}void judge(int miwpl) // 判断wpl、是否重了,输出
{int w = 0;se.clear();int f = 0;for (int i = 0; i < n; i++){char c;string s;cin >> c >> s;w += s.size() * num[c];if (se.find(s) != se.end())f = 1;se.insert(s);for (int j = 1; j <= s.size(); j++){se.insert(s.substr(0, j));}}if (w != miwpl){cout << "No" << endl; return;}if (f){cout << "No" << endl; return;}cout << "Yes" << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);init();wpl = minwpl();cin >> student;for (int i = 0; i < student; i++){judge(wpl);}return 0;
}