描述
输入一串字符串，根据给定的字符串中字符出现的频率建立相应哈夫曼树，构造哈夫曼编码表，在此基础上可以对待压缩文件进行压缩（即编码），同时可以对压缩后的二进制编码文件进行解压（即译码）。
输入
多组数据，每组数据一行，为一个字符串（只考虑26个小写字母即可）。当输入字符串为“0”时，输入结束。
输出
每组数据输出2n+3行（n为输入串中字符类别的个数）。第一行为统计出来的字符出现频率（只输出存在的字符，格式为：字符：频度），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。第二行至第2n行为哈夫曼树的存储结构的终态（形如教材139页表5.2（b），一行当中的数据用空格分隔）。第2n+1行为每个字符的哈夫曼编码（只输出存在的字符，格式为：字符：编码），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。第2n+2行为编码后的字符串，第2n+3行为解码后的字符串（与输入的字符串相同）。
样例输入1 复制
aaaaaaabbbbbccdddd
aabccc
0
样例输出1
a:7 b:5 c:2 d:4
1 7 7 0 0
2 5 6 0 0
3 2 5 0 0
4 4 5 0 0
5 6 6 3 4
6 11 7 2 5
7 18 0 1 6
a:0 b:10 c:110 d:111
00000001010101010110110111111111111
aaaaaaabbbbbccdddd
a:2 b:1 c:3
1 2 4 0 0
2 1 4 0 0
3 3 5 0 0
4 3 5 2 1
5 6 0 3 4
a:11 b:10 c:0
111110000
aabccc1
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178#include<iostream>
#include<cstring>
#include<string>
using namespace std;
#define MAXSIZE 1000
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct
{
char ss[31]; //哈夫曼编码数组，设31是为了以防二进制编码过长
int start;
}HCode;
void Select(HuffmanTree &HT,int m,int &ll,int &rr)//ll的weight小于等于rr的weight,且在数组中又先后顺序。
{
int maxsize=1000; //判断大小的最大值
for(int i=1;i<=m;i++)
{
if(HT[i].parent==0&&maxsize>HT[i].weight)//为>,不是>=,保证遇到第一个编号保留下来。
{
ll=i;
maxsize=HT[i].weight;
}
}
maxsize=1000;
for(int i=1;i<=m;i++)
{
if(HT[i].parent==0&&i!=ll&&maxsize>HT[i].weight)//同理不是>=
{
maxsize=HT[i].weight;
rr=i;
}
}
}
void CreateHuffmanTree(HuffmanTree &HT,int n,int num[]) //创建哈夫曼树
{
if(n<=0) return;
int m=2*n-1;
HT=new HTNode[m+1];
for(int i=1;i<=m;i++)
{
HT[i].parent=0;HT[i].rchild=0;HT[i].lchild=0;
}
int start=1;
for(int i=0;i<26;i++)
{
if(num[i]>0)
{
HT[start++].weight=num[i];
}
}
for(int i=n+1;i<=m;i++)
{
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void CreateHCode(HuffmanTree &HT,HCode s[],int num[],int n)
{
int jstart=1; //哈弗曼编号，即在HT数组里面存在
for(int i=0;i<26;i++)
{
s[i].start=30; //给start初始化
if(num[i]>0)
{
int jj=jstart;
if(n==1) //控制如果为一个节点的特殊情况如何编码
s[i].ss[s[i].start--]='0';
else
{
while(HT[jj].parent!=0)
{
if(HT[HT[jj].parent].lchild==jj)
{s[i].ss[s[i].start--]='0'; //编码是一个入栈，出栈的过程
jj=HT[jj].parent;
}
else
{s[i].ss[s[i].start--]='1';
jj=HT[jj].parent;
}
}
}
jstart++;
}
}
}
int main()
{
string str;
int num[30];
while(cin>>str)
{
int n=0;//这里一定要赋值为0，不然这个n一直在循环里存在，bug都找不到，我太粗心了。
memset(num,0,sizeof(num));
if(str[0]=='0')
break;
for(int i=0;i<str.length();i++)
{
int a=int(str[i])-97;
num[a]++;
}
char b;
int j; //j为暂时变量，存储位置
for(int i=0;i<26;i++)
{
if(num[i]>0) //输出控制num数组很重要
{
b=char(i+97);
cout<<b<<":"<<num[i];
j=i;
n++;
break;
}
}
for(int i=j+1;i<26;i++)
{
if(num[i]>0)
{
b=char(i+97);
n++;
cout<<" "<<b<<":"<<num[i];
}
}
cout<<endl;
HuffmanTree HT;
int m=2*n-1;
CreateHuffmanTree(HT,n,num);
for(int i=1;i<=m;i++)
{
cout<<i<<" "<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
}
HCode s[30]; //26个字母的哈夫曼编码
CreateHCode(HT,s,num,n);
for(int i=0;i<26;i++)
{
if(num[i]>0)
{
b=char(i+97);
cout<<b<<":";
for(int k=s[i].start+1;k<=30;k++)
{
cout<<s[i].ss[k];
}
j=i;
break;}
}
for(int i=j+1;i<26;i++)
{
if(num[i]>0)
{
b=char(i+97);
cout<<" "<<b<<":";
for(int k=s[i].start+1;k<=30;k++)
{
cout<<s[i].ss[k];
}
}
}
cout<<endl;
for(int i=0;i<str.length();i++)
{
int p=int(str[i])-97;
for(int k=s[p].start+1;k<=30;k++)
cout<<s[p].ss[k];
}
cout<<endl;
cout<<str<<endl;
str.clear();
}
return 0;
}
