赫夫曼树实验代码(绝对正确的).doc

《赫夫曼树实验代码(绝对正确的).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、河北大学专业：数电信息年级：09姓名：学号：20099999简单哈夫曼编/译码的设计与实现一、实验目的和要求（1）掌握树的有关操作算法（2）熟悉树的基本存储方法二、实验内容和原理定义哈夫曼树的存储结构；输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。三、算法描述及实验步骤1．算法描述(1).建立哈夫曼树的算法定义各节点类型其中应包含两类数据一是权重域weight；一是指针域而指针域中应该包括指向左右孩子和指向双亲的指针这里分别用lchild、rdhild和parent来表示因此

2、可用静态三叉链表来实现，在实际构造中由于是叶子节点来构造新的根节点其构造过程中仅与叶子节点的权重有关而与其数据域无关所以构造过程中不用考虑其数值域，并且在链表中从叶子开始存放，让后不断的将两颗最小权值的子树合并为一颗权值为其和的较大的子树，逐步生成各自内部节点直到树根。(2).哈夫曼编码的算法将建立的哈夫曼树从每个叶子节点开始沿着双亲域回到根节点，梅走一步进行编码得到一位编码值；由于每个叶子节点的哈夫曼编码是从根节点到相应的叶子的路径的各个分支的代码组成的0和1序列，所以先得到了低位编码后得到高位编码因此

3、可用一维数组从后向前来存放各位编码值，并用start来记录编码的起始位置。2．算法流程图构建哈夫曼树算法流程I

4、=-1&&ht[j].weight

5、#include#definemax

6、value10000//定义最大权值常量#definemaxnodenumber100//定义节点最大数#definemaxbit10//定义哈弗曼编码最大长度typedefstruct//定义新数据类型即节点结构{intweight;//权重域intparent,lchild,rchild;//指针域}htnode;//节点类型标识符//typedefhtnode*huffmanstree;//定义哈弗曼数类型htnodeht[maxnodenumber];//定义三叉链表存储数组typedefstru

7、ct//定义保存一个叶子节点哈弗曼编码的结构{intbit[maxbit];//定义一维数组为编码域intstart;//定义位置域}hcnodetype;//定义编码类型htnode*creatstree(intn)//huffmanstreecreatstree(intn)//建立哈夫曼树算法实现函数{inti,j,m1,m2,k1,k2;//局部变量for(i=0;i<2*n-1;i++)//初始化各节点{ht[i].weight=0;//权重初始化为0ht[i].parent=-1;//根节点和给

8、左右孩子初始化为-1ht[i].lchild=-1;ht[i].rchild=-1;}for(i=0;i