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

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