数据结构课程设计报告题目哈夫曼树及其应用
学生姓名
学号
班级10211116
指导教师
2012年6月3日
f目录
1、需求分析说明3
2、总体设计4
3、详细设计5
4、实现部分7
5、程序测试9
6、总结10
f一需求分析说明
设计目的
熟悉树的各种存储结构及其特点。
掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。
设计内容
数据的读入存储生成文件将键盘输入的信息存入指定的文件中设计一程序求解此问题哈夫曼Huffma
编码原理是一种利用二叉树实现的编码原理
哈夫曼Huffma
编码是1952年为文本文件而建立是一种统计编码。属于无损压缩编码。
哈夫曼编码的码长是变化的对于出现频率高的信息编码的长度较短而对于出现频率低的信息编码长度较长。这样处理全部信息的总码长一定小于实际信息的符号长度。
锻炼我们的编码能力真正理解数据结构的编码思想并且锻炼我们的动手能力和成员间的配合提高程序编写能力。
在信息传递时希望长度能尽可能短即采用最短码。哈夫曼编码的应用就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。
f1初始化提示初始化界面→提示各字符及其权值将存放在hfmTree中→以字母出现次数为权值建立哈弗曼树→弹出选择菜单进行进一步操作
2编码弹出编码界面→读取文件→提示输入要编码的字符串→对文本进行哈弗曼编码并输出编码→保存编码文件
3译码弹出译码界面→利用建立好的哈弗曼树进行译码→将译码输出→保存译码文件
f三详细设计
1数据结构设计
i
cludeiostreamh包含的库函数
i
cludestri
gh
i
cludeioma
iph
co
sti
t
6叶子数目
co
sti
tm2
1森林中树的棵树
co
sti
tc4
classtree
public
chardata
i
tweight权值
i
tpare
t双亲
i
tlchrch左右孩子
voidcreathafuma
tree建立哈夫曼树
voideditcode编码函数
voidtra
codecharbi
tmax译码函数
2算法设计
哈夫曼树编码算法
输入字符权值算法输入一些字符然后再输入相对应数量的权值建哈夫曼树然后进行编码并得到相对应的哈夫曼编码。
voidtreeeditcode编码
i
tijkfcou
t0
i
tcode
1c1
fori1i
i
forj1jcj
codeij2
fori1i
i
k1
jhftreeipare
t
fi
whilej0
ifhftreejlchf
codeik0
else
codeik1
jhftreejpare
t
ffhftreefpare
t

coute
dl
fori1i
i
cout