哈夫曼编码的java实现课程设计

《哈夫曼编码的java实现课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、哈夫曼编码的JAVA实现课程设计目录摘要2一、问题综述2二、求解方法介绍3三、实验步骤及结果分析4四、程序设计源代码5参考文献88摘要利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试用java语言设计一个哈夫曼编码系统。通过本课程设计，应使学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用java语言正确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。关键字：哈夫曼编码JAVA语言类方法一、问题综述1哈夫曼编码的算法思想哈夫曼编码也称前缀编码，它是根据每个字符出现的频率

2、而进行编码的，要求任一字符的编码都不是其它任意字符编码的前缀且字符编码的总长度为最短。它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常用的数据块或出现频率最高的数据，具体的方法是：1.1建立哈夫曼树把N个字符出现的频率值作为字符的权值,然后依据下列步骤建立哈夫曼树。1.1.1由N个权值分别作N棵树的根结点而形成一个森林。1.1.2从中选择两棵根值最小的树T1和T2组成一棵以结点T为根结点的增长树，根结点T=T1+T2,即新树的根值为

3、原来两棵树的根值之和，而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}

4、构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。4）重复2）和3），直到集合F中只有一棵二叉树为止。8例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示：图1构造哈夫曼树的过程示例二、求解方法介绍以往的哈夫曼编

5、码程序实现都是利用PASCAL或C语言描述的，而这两门语言都有相应的指针类型来解决，实现起来较为容易，但是，JAVA语言是面向对象的编程语言，没有提供指针类型，所以在实现上应该结合JAVA的应用环境，采用静态的方法解决。同时，JAVA语言是具有平台无关性的网络编程语言，用JAVA语言实现哈夫曼编码不论在教学中或是在实际应用中都有一定的意义。本程序是用哈夫曼树来实现哈夫曼编码的功能，根据输入的报文进行分析，建立哈夫曼树。统计输入字符串的长度，并对每个字符的频度进行计算。对每个字符及相应的频度作为叶结点建立哈夫曼树。哈夫曼树的

6、建立过程采用把结点看作树每次选最小的两个建立树，并把他们的频度相加，再继续选取最小的两个数建立，直到所有的结点建立完，才形成完整的哈夫曼树。接下来是对没个结点进行编码，从第一个结点开始看它的双亲，若它双亲做左孩子则记0，若是右孩子则记1，依次往上推，直到哈夫曼的根结点为止。记录编码打印出来。为了体现程序中各个功能的独立性，结合JAVA语言的编程要求，对程序中所用到的类和方法进行说明：1公共类Tree：组成哈夫曼树的最小单元。其成员变量有：1.1lchild：最小单元的左孩子。1.2rchild：最小单元的右孩子。1.3pa

7、rents：最小单元的双亲。2公共类Huffman：描述哈夫曼编码的整个过程,其成员变量有：2.1numsMo：储存要进行编码的一组数。2.2nums：临时储存要进行编码的这组数，会随着后面的调用而变化。2.3trees：储存哈夫曼树，由若干最小单元构成。2.4temp：中间变量，是字符串类型。3核心方法及流程3.1　main方法：用于程序的执行入口。其中定义了一个Huff类实体，调用方法start()完成数组初始排序，实现哈夫曼编码等一系列的操作。83.2addNum方法：用于方法初始化给定的要进行编码的数组，数组通过控

8、制台键盘录入。3.3minTo方法：在一组数中选择最小的两个，按递增顺序返回。3.4compareNum方法：是公共类Huffman的核心算法之一，该方法是将一组树形成哈夫曼树，左孩子为较小值。3.5print方法：是公共类Huffman的核心算法之一，该方法利用递归打印出编码。其流程图如下：三、实验步