哈夫曼编码的JAVA实现课程设计.docVIP

哈夫曼编码的JAVA实现课程设计 目 录 摘 要 2 一、问题综述 2 二、求解方法介绍 3 三、实验步骤及结果分析 4 四、程序设计源代码 5 参考文献 8 摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本， 哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据，具体的方法是： 1.1 建立哈夫曼树 把N 个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼树。 1.1.1 由N 个权值分别作N 棵树的根结点而形成一个森林。 1.1.2 从中选择两棵根值最小的树T1 和T2 组成一棵以结点T 为根结点的增长树，根结点T = T1 + T2 ,即新树的根值为原来两棵树的根值之和，而T1 和T2 分别为增长树的左右子树。 1.1.3 把这棵新树T 加入到森林中，把原来的两棵树T1 和T2 从森林中删除。 1.1.4 重复1.1.2～1.1.3 步，直到合并成一棵树为止。 1.2 生成各字符的哈夫曼编码 在上面形成的哈夫曼树中，各个字符的权值结点都是叶子结点，从叶子结点开始向根有哪些信誉好的足球投注网站，如果是双亲的左分支，则用“0”标记，右分支用“1”标记，从叶子结点到根结点所经过的分支编码“0”、“1”的组合序列就是各字符的哈夫曼编码。 2 构造哈夫曼树的算法 1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示： 图1 构造哈夫曼树的过程示例 二、求解方法介绍 以往的哈夫曼编码程序实现都是利用PASCAL 或C 语言描述的，而这两门语言都有相应的指针类型来解决，实现起来较为容易，但是，JAVA语言是面向对象的编程语言，没有提供指针类型，所以在实现上应该结合JAVA 的应用环境，采用静态的方法解决。同时，JAVA 语言是具有平台无关性的网络编程语言，用JAVA 语言实现哈夫曼编码不论在教学中或是在实际应用中都有一定的意义。 本程序是用哈夫曼树来实现哈夫曼编码的功能，根据输入的报文进行分析，建立哈夫曼树。统计输入字符串的长度，并对每个字符的频度进行计算。对每个字符及相应的频度作为叶结点建立哈夫曼树。哈夫曼树的建立过程采用把结点看作树每次选最小的两个建立树，并把他们的频度相加，再继续选取最小的两个数建立，直到所有的结点建立完，才形成完整的哈夫曼树。接下来是对没个结点进行编码，从第一个结点开始看它的双亲，若它双亲做左孩子则记0，若是右孩子则记1，依次往上推，直到哈夫曼的根结点为止。记录编码打印出来。 为了体现程序中各个功能的独立性，结合JAVA 语言的编程要求，对程序中所用到的类和方法进行说明： 1 公共类Tree：组成哈夫曼树的最小单元。其成员变量有： lchild：最小单元的左孩子。 rchild：最小单元的右孩子。 parents：最小单元的双亲。 2 公共类Huffman：描述哈夫曼编码的整个过程,其成员变量有： 2.1 numsMo：储存要进行编码的一组数。 2.2 nums：临时储存要进行编码的这组数，会随着后面的调用而变化。 2.3 trees：储存哈夫曼树，由若干最小单元构成。 2.4 temp：中间变量，是字符串类型。 3 核心方法及流程 3.1　main 方法：用于程序的执行入口。其中定义了一个Huff 类实体，调用方法start() 完成数组初始排序，实现哈夫曼编码等一系列的操作。 3.2 addNum 方法：用于方法初始化给定的要进行编码的数组，数组通过控制台键盘录入。 3.3 minTo 方法：在一组数中选择最小的两个，按递增顺序返回。 3.4 compareNum 方法：是公共类Huffman的核心算法之一，该方法是将一组树形成哈夫曼树，左孩子为较小值。 3.5 print 方法：是公共类Huffman的核心算法之一，该方法利用递归打印出编码。其流程图如下： 三、实验步骤及结果分析 测试数据： 0.01 0.03 0.07