目的：熟练掌握二叉树应用（Huffman编码）的基本算法实现；进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力

要求：(1).假设文档内容从键盘输入；

(2).设计哈夫曼算法的存储结构；

(3).设计哈夫曼编码和解码算法；

(4).分析使劲按复杂度和空间复杂度。

1.实验问题分析

程序是通过利用二叉树结构实现哈夫曼编码和译码，并且程序需具有以下要求：

（1）初始化：能够让用户输入字符和相应字符的频度来初始化，并建立哈夫曼树。

（2）建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码进行输出，打印哈夫曼编码表。

（3）译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

运用哈夫曼算法的相关知识解决问题。以用户输入的字符作为需要编码的字符集合，每个字符对应的频度则作为该字符的权值，构造一棵哈夫曼编码树，规定哈弗曼编码树的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0和1的序列为需要加密字符的编码。

2.数据的存储结构设计：

（1）采用静态的三叉链表存放。

算法思想：头指针数组存储哈夫曼编码串，字符型指针用来存放临时的编码串；从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中。重复，直到所有的叶子节点都被编码完。

  伪代码：

1.用户输入需要编译的字符和该字符的权值;

2.构造哈夫曼算法。设计一个数组H保存哈夫曼树中各结点的信息;

3.数组H初始化，将所有结点的孩子域和双亲域的值初始化为-1;

4.数组H的前n个元素的权值给定值;

5.调用select函数选择权值最小的根结点进行合并，其下标分别为i1，i2;

6.将二叉树i1，i2合并为一棵新的二叉树;

7.共进行n-1次合并，直到剩下一棵二叉树，这棵二叉树就是哈夫曼树;

时间复杂度：

1.Select函数，时间复杂度O(n);

2.Reverse函数，时间复杂度O(n);

3.HuffmanTree函数，构造哈夫曼树，时间复杂度O(n!);

4.CreateCodeTable函数，构造和输出哈夫曼编码表，时间复杂度O(n);

5.Decode函数，解码，时间复杂度O(n)。

代码的实现如下：