北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称：实验三题目2哈夫曼树 学生姓名： 班级： 班内序号： 学号： 日期：
1．实验要求
实验目的：
? 熟悉C++语言的基本编程方法，掌握集成编译环境的测试方法 ? 学习指针、模板类、异常处理的使用 ? 掌握线性表的操作实现方法
? 培养使用线性表解决实际问题的能力
实验内容：
利用二叉树结构实现赫夫曼编/解码器。 基本要求：
1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的
频度，并建立赫夫曼树
2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符
的编码输出。
3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串
输出。
4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输
出译码结果。
5、 打印(Print)：以直观的方式打印赫夫曼树（选作）
6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压
缩效果。
测试数据：
I love data Structure, I love Computer。I will try my best to study data Structure.
提示：
1、用户界面可以设计为“菜单”方式：能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。
第1页
北京邮电大学信息与通信工程学院
2. 程序分析
2.1 存储结构
二叉树：
示意图： root
lchild parent rchild
（静态三叉链表存储）
0 1 2 3 4 5 6 （a）初始化哈夫曼树
weight 2 3 6 9 LChild -1 -1 -1 -1 -1 -1 -1 RChild -1 -1 -1 -1 -1 -1 -1 parent -1 -1 -1 -1 -1 -1 -1 第2页
北京邮电大学信息与通信工程学院
0 1 2 3 4 5 6 weight 2 3 6 9 5 11 20 LChild -1 -1 -1 -1 0 4 3 RChild -1 -1 -1 -1 1 2 5 parent 4 4 5 6 5 6 -1 （b）创建好的哈夫曼树
哈夫曼编码的存储结构
20 0 1
11 A
0 1 5 B 0 1 Z C
0 1 2 3 data Z C B A code 100 101 11 0 2.2 关键算法分析
1 初始化 算法步骤：
①统计字符串字符综述并申请动态数组存储字符串； ②对所存储字符串进行排序； ③统计不同字符的个数； ④释放动态内存空间； ⑤创建哈夫曼数的数组； ⑥创建哈夫曼编码表。
源代码：
void Huffman::Init(char *s) {
int n=0;
while (*(s+n)!='\\0') { n++;//统计字符串字符数 }
第3页
北邮数据结构实验三题目2哈夫曼树
