_陈晓俊_哈夫曼树编码解码

《_陈晓俊_哈夫曼树编码解码》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计课程名称数据结构班级与班级代码14计算机2班，142511022专业计算机科学与技术指导教师罗勇学号14251102202姓名陈晓俊电子邮箱827381654@qq.com提交日期2016年6月29日广东财经大学教务处制哈夫曼树编码解码1．任务和要求哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。既然要设计哈夫曼树编码来进行通讯传输,那么就必须有一套哈夫曼树解码。通过对哈夫曼树编码解码的分析，此实验应该包含如下要求：（1）设计一组字符和字符出现的频率，即字符的权重，生成哈夫曼树；（2）

2、利用哈夫曼树求出所对应的哈夫曼树编码；（3）打印所有字符以及所对应的哈夫曼编码，并显示平均编码长度；（4）利用哈夫曼树解码原理编写解码函数，由哈夫曼编码求解出所对应的字符；（5）显示所有哈夫曼编码及其所对应的字符；（6）对比分析编码解码的正确性；2．总体设计2.1系统功能模块图：图一初始化哈夫曼树构造哈夫曼编码构造哈夫曼树打印哈夫曼编码哈夫曼树译码打印哈夫曼树打印哈夫曼译码主函数292.2哈夫曼树的特点：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树，权值较大的结点离根较近。2.3哈夫曼树的构造过程：步骤1：根据给定的n个权值{w1,w2,…wn}，构造n棵只有根节点的

3、二叉树，这n棵二叉树构成一个森林F。步骤2：在森林F中选择两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根节点的权值之和。步骤3：在森林F中删除这两棵树，同时将新得到的二叉树放入到F中。步骤4：重复步骤2和步骤3，知道F中只有一棵二叉树为止。2.4哈夫曼树的编码相关性质：性质1：哈夫曼编码是前缀编码性质2：哈夫曼编码是最优前缀编码2.5哈夫曼树的编码过程：依次以叶子为出发点，向上回溯至根节点为止。回溯时走作分支则生成代码0，走右分支则生成代码1。3.详细设计3.1详细的涉及思路（1）采用的节点类型：哈夫曼树的节点又四个类型，包括节点的

4、权值weight、双亲节点parent、左孩子节点lchild、右孩子节点rchild。采用的逻辑结构：哈夫曼树为最优二叉树，其采用的逻辑结构为树状结构。采用的存储结构：由于哈夫曼树中没有度为1的节点，则一棵有n个节点的哈夫曼树共有2n-1个节点，可以存储在一个大小为2n-1的一维数组中。树中没个节点还要包含其双亲信息和孩子节点的信息，因此，每个节点的存储结构如下表一所示，哈夫曼树的结构体如下面所示的结构体。29表一weightparentlchildrchild//---哈夫曼树的存储表示---typedefstruct{chardata[5];//定义节点值doublewe

5、ight;//节点的权重intparent,lchild,rchild;//定义哈夫曼树的双亲节点、左右孩子节点}HTNode，*HuffmanTree;//动态分配数组存储哈夫曼树采用的算法：本系统采用的算法为哈夫曼算法。3.2哈夫曼树编码解码详细的构造过程（1）设计如下字符权重表（即26字权重表）表二字符abcdefghij权重121323156724369010019字符klmnopqrst权重391392343578895714589029字符uvwxyz权重701234561189111（2）根据字符权重表，利用哈夫曼算法构造哈夫曼数。下面取图三表格中的前面10个字符

6、权重进行构造哈夫曼树的思路说明。注：全部字符的构造与实现将在程序中体现！步骤1：根据给定的10个字符权值，构造10棵只有根节点的二叉树，这10棵二叉树构成一个森林F。121323156729森林F19100903624步骤2：在森林F中选择两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根节点的权值之和。如下图a251213图a步骤3：在森林F中删除这两棵树，同时将新得到的二叉树放入到F中。如下图b36246715232519100901312图b步骤4：重复步骤2和步骤3，知道F中只有一棵二叉树为止。最后得到如图四的哈夫曼树。29图四

7、1733992268390100126364759672324253412131519（3）哈夫曼树编码原理及其算法：哈夫曼编码是指利用哈夫曼树求得的用于通信的二进制编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，这就是哈夫曼编码原理。例如上图四的哈夫曼树的编码如下页图五所示，图五即为哈夫曼树的编码原理，编码是从叶子节点开始编起，往根节点回溯的过程。29