数据结构与算法课程设计报告书
题目：哈夫曼编码译码器
班级：
11091211
学号：1109121105
姓名：
田欢
指导教师：龚丹
周期：20111219至20111223
成绩：
年月日
f一、课程设计的目的与要求
（一）课程设计目的与任务（参考已发文档自行编辑，但不少于100字）设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直
到选择退出为止。利用哈夫曼树编码问题基本原理的应用，撑握对树的不同存储结构的定义和算法描述。学会构造哈夫曼树和哈夫曼编码等主要算法。（二）题目要求
1将权值数据存放在数据文件文件名为datatxt，位于执行程序的当前目录中2分别采用动态和静态存储结构3初始化：键盘输入字符集大小
、
个字符和
个权值，建立哈夫曼树；4编码：利用建好的哈夫曼树生成哈夫曼编码；5输出编码；6设字符集及频度如下表：字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161
二、设计正文
1系统分析（1）定义一个变量名为HTNode的结构体，用该结构体中的chardata、i
t
weight、i
tpare
t、i
tlchild、i
trchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht30存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCode类型变量的cdstartcd
存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd30的数组用于存放当前叶子结点hti的哈夫曼编码。
（2）编写CodeI
put
ht函数并在函数中设置一个fori0
循环，首先输入
个字符，再利用函数中的fori0
循环实现对这
个字符的权值的输入。
（3）编写CreateHTht
函数来构造一棵哈夫曼树，首先用一个fori02
1循环将所有2
1个结点的pare
t、lchild、rchild域均置初值为1；再用一个fori
2
1循环来构造哈夫曼树，在该循环中首先令l
ode和r
ode为最小权值的两个结点位置且其域值均为1，再用一个fork0i1k循环在数组ht30中寻找权值最小的两个结点并且只能在尚未构造二叉树的结点中查找，由于只能在尚未构造二叉树的结点中查找，因此在fork0ki1k循环中加入一个ifhtkpare
t1语句来判断结点l
ode和r
ode是否已经在二叉树中，如果结点l
ode和r
ode在二叉树中，则结点l
ode和r
ode的pare
t的值为其双亲结点在数组ht30中的序号就不会为1
f了，在查找到htl
ode和htr
ode后将他们作为hti的左右子树，htl
ode和htr
ode的双亲结点置为hti，且htiweighthtr