实验二 哈夫曼树及哈夫曼编码译码的实现.doc

实验二:哈夫曼树及哈夫曼编码译码的实现(验证性、4学时)
实验目的和要求
构建哈夫曼树及哈夫曼编码,输出哈夫曼树及哈夫曼编码,完成编码与译码的算法。
(1)掌握树的有关操作算法
(2)熟悉树的基本存储方法
(3)学习利用树求解实际问题
实验内容和原理
定义哈夫曼树的存储结构;输入要编码的字符权重,根据权重建立哈夫曼树,并进行编码,最后输出哈夫曼编码。
实验环境
硬件:(1)学生用微机(2)多媒体教室或远程教学(3)局域网环境
软件:(1)Windows XP中文操作系统(2)Turbo C
算法描述及实验步骤
算法描述
建立叶子结点——由于每个叶子结点都有一个权重值,构造哈夫曼树的过程中每个分枝节点的权重值等于两个孩子结点权重值的和,所以应该有一个权重域和指向左右孩子的两个指针域;
另外在建成哈夫曼树之后,为了求得每个叶子结点的哈夫曼编码,需要走一条从叶子结点到根结点的路径,而译码的过程是从根结点出发到叶子的不断匹配的过程,所以既需要知道孩子结点的信息,也需要知道双亲结点的信息,应该再有一个指向双亲结点的指针域。
构建哈夫曼编码——在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点,每回退一步走过哈夫曼树的一个分枝得到一个哈夫曼编码值;由于每个叶子结点的哈夫曼编码是从根就诶点到相应叶子结点的路径上各分枝代码所组成的0、1序列,所以先得到的分枝代码为说求编码的低位码而后得到的为高位码。
算法流程图
构建哈夫曼树算法流程
哈夫曼编码算法流程
代码
#include<>
#define maxvalue 10000//定义最大权值常量
#define maxnodenumber 100//定义结点最大数目常量
typedef struct
{int weight;
int parent,lchild,rchild;
}htnode;
typedef htnode *huffmantree;//定义哈夫曼树类型
htnode ht[maxnodenumber]; //定义静态三叉链表存储区数组
#define maxbit 10//定义哈夫曼编码的最大长度
typedef struct//定义保存一个叶子结点哈夫曼编码的结构
{int bit[maxbit];//哈夫曼编码域为一维数组
int start;//开始位置域为整型
}hcodetype;//定义哈夫曼编码类型
hcodetype cd[maxnodenumber];//定义存放哈夫曼编码的数组cd
void crthuffmantree(int n);//建立哈夫曼树
void gethuffmancode(int n);//哈夫曼编码
void main ()
{
int nodenum;
printf("inputnodenum:");
scanf("%d",&nodenum);
crthuffmantree(nodenum);
gethuffmancode(nodenum);
}
void crthuffmantree(int n)//该算法对n个叶子结点建立哈夫曼树,权重值由键盘逐个输入
{int i,j,m1,m2,k1,k2;//定义局部变量
for(i=