期末数据结构实训（c++版）——哈夫曼编码大全

描述：

关于哈夫曼树的建立，编码，解码。

输入

第一行输入数字N，代表总共有多少个字符以及权值

第二第三行分别是一行字符串，以及每个字符对应的权值

接下来输入一个数M，表示接下来有M行字符串，要求你对每个字符串进行编码

再输入一个数X，表示接下来有X行编码，要求你对每行编码进行解码

输出

第一行输出所有节点的权重

接下来输出N行，每行以 “a:001”的格式输出每个字符对应的编码

接着输出M行，对输入的字符串的编码结果

最后，输出X行的解码结果

输入样例

6
abcdef
50 10 5 5 20 10
2
abcdef
defabaabbc
2
011001100100110110101101100
1100011000110101100101100

输出样例

50 10 5 5 20 10 10 20 30 50 100
a:0
b:100
c:1100
d:1101
e:111
f:101
010011001101111101
11011111010100001001001100
accbdfadb
cacadacfb

思路：

开一个数组存储每个点的“地址”（代码中的idx），每一次按照权值优先，深度其次，idx最次的顺序给数组从大到小排序，每次都能够合并数组末尾的两个“节点”，再将新节点插入数组，这样每回都能缩减数组中的一个空间，当数组只剩下一个元素时及根节点，停止更新，自从更节点开始，深搜一遍，记录每个点的二进制序列即可，ac代码如下：

ac代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int l[N],r[N],d[N],w[N],idx=1,m;
int a[N],cnt;
map<char,int> mp;
map<int,char> dmp;
map<int,string> hfm;
map<string,int>dhfm;

string ss;

bool cmp(int x,int y)
{
	if(w[x]!=w[y]) return w[x]>w[y]; //优先权值
	if(d[x]!=d[y]) return d[x]>d[y]; //其次深度
	return x>y; //最次下标
}

void dfs(int p,string str)
{
	if(!l[p]&&!r[p]) //如果没有左右儿子，表示已经搜到叶子节点了
	{
		hfm[p]=str;  //正向记录一遍
		dhfm[str]=p;  //反向记录一遍 输出要用到
		return;
	}
	
	if(l[p]) dfs(l[p],str+"0");
	if(r[p]) dfs(r[p],str+"1");
}

int main()
{
	cin>>m>>ss;
	int x;
	
	for(int i=0;i<m;i++)
	{
		mp[ss[i]]=idx; //正向记录一遍
		dmp[idx]=ss[i];//反向记录一遍 输出要用到
		cin>>x;
		a[cnt++]=idx,d[idx]=1,w[idx++]=x;
	}
	
	//建树
	while(cnt>1)
	{
		sort(a,a+cnt,cmp);  //没变都自定义排序一遍，（期末题无需考虑时间复杂度，码量越少越好[斜眼笑]）
		w[idx]=w[a[cnt-1]]+w[a[cnt-2]];   //权值更新
		d[idx]=max(d[a[cnt-1]],a[cnt-2])+1;  //深度更新
		l[idx]=a[cnt-1],r[idx]=a[cnt-2];  //记录左右儿子
		a[cnt-2]=idx++;  
		cnt--;
	}
	int root=a[cnt-1];
	
	//从root深搜记录每个点的二进制序列
	dfs(root,"");
	
	//25行的输出过程 [苦笑]
	for(int i=1;i<idx;i++) cout<<w[i]<<" ";
	cout<<endl;
	for(int i=0;i<m;i++)
		cout<<ss[i]<<":"<<hfm[mp[ss[i]]]<<endl;
	
	cin>>m;
	while(m--)
	{
		cin>>ss;
		for(int i=0;i<ss.size();i++)cout<<hfm[mp[ss[i]]];
		cout<<endl;
	}
	cin>>m;
	while(m--)
	{
		cin>>ss;
		string now;
		for(int i=0;i<ss.size();i++)
		{
			now+=ss[i];
			if(dhfm[now])cout<<dmp[dhfm[now]],now="";
		}
		cout<<endl;
	}
	
	
}