实验四哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容[ 问题描述 ] 已知 n 个字符在原文中出现的频率,求它们的哈夫曼编码。[ 基本要求 ]1. 初始化:从键盘读入n 个字符,以及它们的权值,建立Huffman 树。(具体算法可参见教材P147 的算法 6.12)2. 编码:根据建立的Huffman 树,求每个字符的Huffman编码。对给定的待编码字符序列进行编码。[ 选作内容 ] 1. 译码:利用已经建立好的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; //...