数据结构
实
验
报
告
实验名称哈夫曼树
学生姓名
班级2013211125班
班内序号14号
学号
日期2014年12月
f1实验目的和内容
利用二叉树结构实现哈夫曼编解码器。
基本要求
1、初始化I
it能够对输入的任意长度的字符串s进行统计统计每个字
符的频度
并建立哈夫曼树
2、建立编码表CreateTable利用已经建好的哈夫曼树进行编码并将每个
字符的编码输出。
3、编码E
codi
g根据编码表对输入的字符串进行编码并将编码后的字
符串输
出。
4、译码Decodi
g利用已经建好的哈夫曼树对编码后的字符串进行译码
并输出
译码结果。
5、打印Pri
t以直观的方式打印哈夫曼树选作
6、计算输入的字符串编码前和编码后的长度并进行分析讨论赫夫曼编
码的压
缩效果。
7、可采用二进制编码方式选作
测试数据
IlovedataStructureIloveComputer。IwilltrymybesttostudydataStructure
提示
1、用户界面可以设计为“菜单”方式能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度对没有出现的字符一
律不用编码
2程序分析
21存储结构
用struct结构类型来实现存储
树的结点类型
structHNode
f
i
tweight权值
i
tpare
t父节点
i
tlchild左孩子
i
trchild右孩子
structHCode实现编码的结构类型
chardata被编码的字符
charcode100字符对应的哈夫曼编码
22程序流程
f23关键算法分析
算法1voidHuffma
Cou
t
1算法功能对出现字符的和出现字符的统计构建权值结点初始化编码表
2算法基本思想对输入字符一个一个的统计并统计出现次数构建权值数组
3算法空间、时间复杂度分析空间复杂度O1要遍历一遍字符串时间复
杂度O
4代码逻辑
leaf0初始化叶子节点个数
i
tij0
i
ts1280用于存储出现的字符
fori0stri0i遍历输入的字符串
si
tstri统计每个字符出现次数
fori0i128i
ifsi0
datajchari给编码表的字符赋值
weightjsi构建权值数组
j
leafj叶子节点个数即字符个数
fori0ileafi
coutdatai