14251102202陈晓俊哈夫曼树编码解码.doc.docVIP

课程设计 课程名称 数 据 结 构 班级与班级代码 14计算机2班，142511022 专 业 计 算 机 科 学 与 技 术 指导教师 罗 勇 学 号 14251102202 姓 名 陈晓俊 电子邮箱 827381654@ 提交日期 2016年6月29日 广东财经大学教务处 制 哈夫曼树编码解码 1．任务和要求 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。既然要设计哈夫曼树编码来进行通讯传输,那么就必须有一套哈夫曼树解码。通过对哈夫曼树编码解码的分析，此实验应该包含如下要求： （1）设计一组字符和字符出现的频率，即字符的权重，生成哈夫曼树； （2）利用哈夫曼树求出所对应的哈夫曼树编码； （3）打印所有字符以及所对应的哈夫曼编码，并显示平均编码长度； （4）利用哈夫曼树解码原理编写解码函数，由哈夫曼编码求解出所对应的字符； （5）显示所有哈夫曼编码及其所对应的字符； （6）对比分析编码解码的正确性； 2．总体设计 2.1系统功能模块图： 2.2哈夫曼树的特点： 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树，权值较大的结点离根较近。…wn}，构造n棵只有根节点的二叉树，这n棵二叉树构成一个森林F。 步骤2：在森林F中选择两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根节点的权值之和。 步骤3：在森林F中删除这两棵树，同时将新得到的二叉树放入到F中。 步骤4：重复步骤2和步骤3，知道F中只有一棵二叉树为止。 2.4哈夫曼树的编码相关性质： 性质1：哈夫曼编码是前缀编码 性质2：哈夫曼编码是最优前缀编码 2.5哈夫曼树的编码过程： 依次以叶子为出发点，向上回溯至根节点为止。回溯时走作分支则生成代码0，走右分支则生成代码1。 3.详细设计 3.1详细的涉及思路 （1） 采用的节点类型： 哈夫曼树的节点又四个类型，包括节点的权值weight、双亲节点parent、左孩子节点lchild、右孩子节点rchild。 采用的逻辑结构： 哈夫曼树为最优二叉树，其采用的逻辑结构为树状结构。 采用的存储结构： 由于哈夫曼树中没有度为1的节点，则一棵有n个节点的哈夫曼树共有2n-1个节点，可以存储在一个大小为2n-1的一维数组中。树中没个节点还要包含其双亲信息和孩子节点的信息，因此，每个节点的存储结构如下表一所示，哈夫曼树的结构体如下面所示的结构体。 weight parent lchild rchild //---哈夫曼树的存储表示--- typedef struct{ char data[5]; //定义节点值 double weight; //节点的权重 int parent,lchild,rchild; //定义哈夫曼树的双亲节点、左右孩子节点 }HTNode，*HuffmanTree;//动态分配数组存储哈夫曼树 采用的算法： 本系统采用的算法为哈夫曼算法。 3.2哈夫曼树编码解码详细的构造过程 （1）设计如下字符权重表（即26字权重表） 字符 a b c d e f g h i j 权重 12 13 23 15 67 24 36 90 100 19 字符 k l m n o p q r s t 权重 39 139 234 35 78 89 57 145 890 29 字符 u v w x y z 权重 70 123 456 11 89 111 （2）根据字符权重表，利用哈夫曼算法构造哈夫曼数。下面取图三表格中的前面10个字符权重进行构造哈夫曼树的思路说明。注：全部字符的构造与实现将在程序中体现！ 步骤1：根据给定的10个字符权值，构造10棵只有根节点的二叉树，这10棵二叉树构成一个森林F。 步骤2：在森林F中选择两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根节点的权值之和。如下图a 步骤3：在森林F中删除这两棵树，同时将新得到的二叉树放入到F中。如下图b 步骤4：重复步骤2和步骤3，知道F中只有一棵二叉树为止。最后得到如图四的哈夫曼树。 （3）哈夫曼树编码原理及其算法： 哈夫曼编码是指利用哈夫曼树求得的用于通信的二进制编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树