题目描述

​ 编写一个哈夫曼编码译码程序。针对一段文本，根据文本中字符出现频率构造哈夫曼树，给出每个字符的哈夫曼编码，并进行译码，计算编码前后文本大小。
为确保构建的哈夫曼树唯一，本题做如下限定：

​ 1.选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。
​ 2.若多棵二叉树根结点权值相等，则先生成的作为左子树，后生成的作为右子树，具体来说：i) 对于单结点二叉树，优先选择根结点对应字母在文本中最先出现者，如文本为 cba，三个字母均出现 1 次，但 c 在文本中最先出现，b 第二出现，故则选择 c 作为左子树，b 作为右子树。ii) 对于非单结点二叉树，先生成的二叉树作为左子树，后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等，优先选择单结点二叉树。
​ 3.生成哈夫曼编码时，哈夫曼树左分支标记为 0，右分支标记为 1。

输入格式

​ 输入为 3 行。第 1 行为一个字符串，包含不超过 5000 个字符，至少包含两个不同的字符，每个字符为 a-z 的小写字母。第 2、3 行为两个由 0、1 组成的字符串，表示待译码的哈夫曼编码。

输出格式

​ 输出第一行为用空格间隔的 2 个整数，分别为压缩前后文本大小，以字节为单位，一个字符占 1 字节，8 个二进制位占 1 字节，若压缩后文本不足 8 位，则按 1 字节算。输出从第二行开始，每行为 1 个字符的哈夫曼编码，按各字符在文本中出现次数递增顺序输出，若多个字符出现次数相同，则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串，表示译码结果，若译码失败，则输出 INVALID。

输入样例

1
2
3
cbaxyyzz
0100
011

输出样例

1
2
3
4
5
6
7
8
9
8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID

思路

先用优先队列建树，然后深搜探索出每个字符的编码，再对比特流进行译码即可。

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
struct node{
	char date;//记录字符
	int HZ;//记录频率
	int qz;//记录优先值
	node* left;//左子树
	node* right;//右子树
};
struct cmp{//优先队列排序规则
	bool operator()(const node* x,const node* y){
		if(x->HZ!=y->HZ)return x->HZ>y->HZ;
		else return x->qz>y->qz;
	}
};
string x,y,z;
int bj,wpl=0,jh;
map<char,int>mp,yxj;//记录频率和优先值
vector<char>ym;//记录译出的码
priority_queue<node*,vector<node*>,cmp>q,rnm;
map<char,vector<int> >bm;//记录各字符编码
vector<int>v;
void dfs(node* BT){
	if(BT){
		if(islower(BT->date)){
			bm[BT->date]=v;
		}
		v.push_back(0);
		dfs(BT->left);
		v.pop_back();
		v.push_back(1);
		dfs(BT->right);
		v.pop_back();
	}
}
void ym(string x){//译码函数
	ym.clear();
	node* t=new node;
	t=q.top();
	jh=1;
	for(int i=0;i<x.size();i++){
		if(x[i]=='0')t=t->left;
		else t=t->right;
		if((i==(x.size()-1))&&isupper(t->date))jh=0;
		if(islower(t->date)){
			ym.push_back(t->date);
			t=q.top();
		}
	}
	if(jh)for_each(ym.begin(),ym.end(),[](char x){cout<<x;});
	else cout<<"INVALID";
	cout<<endl;
}
int main(){
	cin>>x>>y>>z;
	for(auto k:x){
		mp[k]++;
		if(yxj[k]==0)yxj[k]=bj++;
	}
	for(auto k:mp){
		node* t=new node;
		t->date=k.first;
		t->HZ=k.second;
		t->qz=yxj[k.first];
		t->left=t->right=nullptr;
		q.push(t);
		rnm.push(t);
	}
	while(q.size()!=1){//构建哈夫曼树
		node* a=new node;
		a=q.top();
		q.pop();
		node* b=new node;
		b=q.top();
		q.pop();
		node* t=new node;
		t->date='A';
		t->qz=bj++;
		t->HZ=a->HZ+b->HZ;
		t->left=a;
		t->right=b;
		q.push(t);
		wpl+=t->HZ;
	}
    cout<<x.size()<<" ";
    int e=wpl/8;
    if(e*8<wpl)e++;
    cout<<e<<endl;
	dfs(q.top());
	while(rnm.size()){
		char k=rnm.top()->date;
		cout<<k<<":";
		for(auto r:bm[k]){
			cout<<r;
		}
		rnm.pop();
		cout<<endl;
	}
	ym(y);
	ym(z);
	return 0;
}