试验四--哈夫曼树与哈夫曼编码

实验四哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容[ 问题描述 ] 已知 n 个字符在原文中出现的频率，求它们的哈夫曼编码。[ 基本要求 ]1. 初始化：从键盘读入n 个字符，以及它们的权值，建立Huffman 树。（具体算法可参见教材P147 的算法 6.12）2. 编码：根据建立的Huffman 树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。[ 选作内容 ] １. 译码：利用已经建立好的Huffman 树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子， 直至叶结点， 便求得该子串相应的字符。4. 打印 Huffman 树。［测试数据 ］利用教材 P.148 例 6－2 中的数据调试程序。可设8 种符号分别为 A,B,C,D,E,F,G,H 。编/ 译码序列为“CFBABBFHGH”( 也可自己设定数据进行测试 ) 。三、算法设计1 、 主 要 思 想 ： ******************赫 夫 曼 树 的 构 造********************** (1) 由给定的 n 个权值 {w1, w2, ⋯, wn} ，构造具有 n 棵二叉树的森林F ={T1, T2, ⋯, Tn } ，其中每棵二叉树 Ti 只有一 个带权为 wi 的根结点 , 其左、右子树均为空。(2) 在 F 中选取两棵根结点的权值最小的二叉树, 作为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3) 在 F 中删去这两棵二叉树 , 把新的二叉树加入F。 (4) 重复 (2) 和(3), 直到 F 中仅剩下一棵树为止。 ****************************霍夫曼编码***************************** 主要用途是实现数据压缩。 由于赫夫曼树中没有度为1的节点，则一棵有 n 个叶子结点的赫夫曼树共有2n-1 个结点，可以存储在一个大小为 2n-1 的一维数组中。由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径； 而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既须知双亲的信息，又需知孩子结点的信息。2、 本程序包含三个模块1）主函数Int main() { 先输入结点总数；分别输入各个结点；调用建立哈夫曼树函数；调用编码函数读入建立的哈夫曼树进行编码} 3、元素类型、结点类型和指针类型typedef struct //定义新数据类型即结点结构{int weight; //权重域 int parent,lchild,rchild; //...