C++实现哈夫曼树的编码和译码

转载自：C++实现哈夫曼树的编码和译码_努力奋斗的小码农的博客-CSDN博客

（1）问题描述

输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树，构造哈夫曼编码表，在此基础上可以对压缩文件进行压缩（即编码），同时可以对压缩后的二进制编码文件进行解压（即译码）。

（2）输入要求

多组数据，每组数据1行，为一个字符串（只考虑26个小写字母即可）。当输入字符串为“0”时，输入结束。

（3）输出要求

每组数据输出2n+3行（n为输入串中字符类别的个数。第1行为统计出来的字符出现频率（只输出存在的字符，格式为：字符：频度），每两组字符之间用一个空格分隔，字符按照 ASCII 码从小到大的顺序排列。第2行至第2n行为哈夫曼树的存储结构的终态，如主教材139页表5.2（b）,一行当中的数据用空格分隔。第2n+1行为每个字符的哈夫曼编码（只输出存在的字符，格式为：

字符：编码），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。第2n+2行为编码后的字符串，第2n+3行为解码后的字符串（与输入的字符串相同）。

（4）输入样式

aaaaaaabbbbbccdddd (案例1)

aabccc            (案例2)

0

（5）输出样例

a:7  b:5  c:2  d:4   (案例1)

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:l   c:3      (案例2) 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  aabccc

代码：