tributes-dr什么意思
北京邮电大学电信工程学院
2008
级数据结构实验报告
实验名称：
实验三
树
学生姓名：
班
级：
班内序号：
学
号：
日
期：
20
013
年
11
月
26
日
1
．实验要求
实验目的
通过选择下面两个题目之一进行实现，掌握如下内容：
掌握二叉树基本操作的实现方法
了解赫夫曼树的思想和相关概念
学习使用二叉树解决实际问题的能力
实验内容
利用二叉树结构实现赫夫曼
编
/
解码器。
基本要求：
1.
初始化
(Init)
：
能够对输入的任意长度的字符串
s
进行统计，
统计每个字符的频度，
< br>并建
立赫夫曼树
2.
建立编码表
(CreateTable)
：利用已经建好的赫夫曼树进行编码，并将每个字符的
编码输
出。
3.
编码
(
Encoding)
：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4.
译码
(Decoding)
：利用已经建好的赫夫曼树对编码后的字
符串进行译码，并输出译码结
果。
5.
打印
(
Print)
：以直观的方式打印赫夫曼树（选作）
6.
计算输入的字符串编码前和编码
后的长度，并进行分析，讨论赫夫曼编码的压缩效果。
2.
程序分析
哈夫曼树结点的储存结构除了二叉树所有的双亲域
parents
< br>，
左子树域
lchild
，
右子树域
rchild
。
< br>还需要有字符域
word
，权重域
weight
，编码域
code
。其
中由于编码是一串由
0
和
1
组成的
字符串，所以
code
是一个字符数组。
进行哈夫曼编码首先要对用户输入的信
息进行统计，将每个字符作为哈夫曼树的叶子结点。
统计每个字符出现的次数
（频度）
作为叶子的权重，
统计次数可以根据每个
字符不同的
ASCII
码。并根据叶子结点的权重建立一个哈夫
曼树。
建立每个叶子的编码从根结点开始，规定通往左子树路
径记为
0
，通往右子树路径记为
1.<
/p>
由于编码要求从根结点开始，
所以需要前序遍历哈夫曼树，
故编码过程是以前序遍历二叉树
第
1
页
北京邮电大学电信工程学院
为基础的
。同时注意递归函数中能否直接对结点的编码域进行操作。
编
码信息只要遍历字符串中每个字符，
从哈夫曼树中找到相应的叶子结点，
取得相应的编码。
最后再将所有找到的编码连接起来即可。
译码则是将编码串从左到右诸位判别，
直到确定一个字符
。
这可以用生成哈夫曼树的逆过程
实现。由于每个字符的编码各
不相同，且编码也是个字符串，所以只要遍历编码串，从哈夫
曼树中找到相应的叶子结点
，取得相应的字符再将找到的字符连接起来即可。
2.1
存储结构
哈夫曼树结点储存结构
word
哈夫曼树顺序存储结构
0
1
2
3
4
word
A
B
C
0
0
weight
35
25
15
40
75
lchild
-1
-1
-1
0
3
parents
3
3
4
4
-1
rchild
-1
-1
-1
1
2
weight
parent
LChild
RChild
2.2
关键算法分析
1
、统计字符的频度
自然语言描述：
1)
取出字符串中的一个字符
2)
遍历所有初始化的哈夫曼树结点
3)
如果结点中有记录代表的字符且
字符等于取出的字符，
说明该字符的叶子存在，
则将该
结点的权加一。
4)
如果所有结点均没有记录字符与取出字符一致，
说明该字符的叶
子不存在，
则将结点的
字符记为取出字符，并将权重设为
1.
5)
重复（
1
）
（
2
）
（
3
）
（
4
）步骤，如此遍历字符串中的所有字符。<
/p>
伪代码：
(int
i=0;i<
字符长度
;i++)
1.1for (int
j=0;j<
字符长度
;j++)
1.1.1 if
(WordStr[i]==HuffTree[j].word)
1.1.1.1
权重
++
1.1.1.2 break;
1.1.2
否则取字符域为空的结点
1.1.2.1 HuffTree[j].word=WordStr[i];
1.1.2.2 HuffTree[j].weight=1;
1.1.2.3
叶子数
++;
1.1.2.4 break;
结束
时间复杂度
O(n
< br>2
),
空间复杂度
S(0)
2
、构造哈夫曼树
第
2
页