一、实验题目：基于哈夫曼树的数据压缩算法
二、实验目的：1、掌握哈夫曼树的构造算法。2、掌握哈夫曼编码的构造算法。
三、实验内容：
问题描述:
输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树，构造哈夫曼编码表，在此基础上可以对压缩文件进行压缩（即编码），同时可以对压缩后的二进制编码文件进行解压（即译码）。
输入要求:
多组数据，每组数据1行，为一个字符串（只考虑26个小写字母即可）。当输入字符串为“0”时，输入结束。
输出要求:
每组数据输出2n+3行（n为输入串中字符类别的个数）。
第1行为统计出来的字符出现频率（只输出存在的字符，格式为：字符:频度），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。第2行至第2n行为哈夫曼树的存储结构的终态（如主教材139页表5.2（b）,一行当中的数据用空格分隔）。第2n+1行为每个字符的哈夫曼编码（只输出存在的字符，格式为：字符:编码），每两组字符之间用一个空格分隔，字符按照ASCII码从小到大的顺序排列。
第2n+2行为编码后的字符串，
第2n+3行为解码后的字符串（与输入的字符串相同）。
输入样例：
aaaaaaabbbbbccdddd
aabccc
0
输出样例：
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
aabccc
四、实验要求：
1、以小组为单位团队编程。
2、分别给出算法实现所采用的存储结构的C语言描述，以及各算法步骤和算法描述。
3、编写程序实现它们的功能。