《哈夫曼编码的JAVA实现课程设计》由会员分享，可在线阅读，更多相关《哈夫曼编码的JAVA实现课程设计（8页珍藏版）》请在金锄头文库上搜索。
1、哈夫曼编码的JAVA实现课程设计目录摘 要 2一、问题综述 2二、求解方法介绍 3三、实验步骤及结果分析 4四、程序设计源代码 5参考文献 8摘要利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降 低传输成本，试用 java 语言设计一个哈夫曼编码系统。通过本课程设计，应使 学生掌握哈夫曼编码的特点、储存方法和基本原理，培养学生利用 java 语言正 确编写程序及调试程序的能力，运用数据结构知识解决实际问题的能力。关键字：哈夫曼编码 JAVA 语言 类 方法一、问题综述1 哈夫曼编码的算法思想 哈夫曼编码也称前缀编码，它是根据每个字符出现的频率而进行编码的，要 求任一字符的编码
2、都不是其它任意字符编码的前缀且字符编码的总长度为最短。 它主要应用于通信及数据的传送以及对信息的压缩处理等方面。哈夫曼编码的基 础是依据字符出现的频率值而构造一棵哈夫曼树，从而实现最短的编码表示最常 用的数据块或出现频率最高的数据，具体的方法是：1.1 建立哈夫曼树把N个字符出现的频率值作为字符的权值，然后依据下列步骤建立哈夫曼 树。1.1.1由N个权值分别作N棵树的根结点而形成一个森林。1.1.2从中选择两棵根值最小的树T1和T2组成一棵以结点T为根结点的 增长树，根结点T = TL + T2，即新树的根值为原来两棵树的根值之和，而T1和 T2 分别为增长树的左右子树。1.1.3把这棵新树T
3、加入到森林中，把原来的两棵树T1和T2从森林中删 除。1.1.4重复1.1.21.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中选取
4、两棵根结点权值最小的树作为新构造的二叉树的左右子树，新 二叉树的根结点的权值为其左右子树的根结点的权值之和。3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F 中。4）重复2）和3）,直到集合F中只有一棵二叉树为止。例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图 所示：图1 构造哈夫曼树的过程示例二、求解方法介绍以往的哈夫曼编码程序实现都是利用PASCAL或C语言描述的，而这两门语 言都有相应的指针类型来解决，实现起来较为容易，但是，JAVA语言是面向对象 的编程语言，没有提供指针类型，所以在实现上应该结合JAVA的应用环境，采 用静态的方法解决。
5、同时，JAVA语言是具有平台无关性的网络编程语言，用JAVA 语言实现哈夫曼编码不论在教学中或是在实际应用中都有一定的意义。本程序是用哈夫曼树来实现哈夫曼编码的功能，根据输入的报文进行分析， 建立哈夫曼树。统计输入字符串的长度，并对每个字符的频度进行计算。对每个 字符及相应的频度作为叶结点建立哈夫曼树。哈夫曼树的建立过程采用把结点看 作树每次选最小的两个建立树，并把他们的频度相加，再继续选取最小的两个数 建立，直到所有的结点建立完，才形成完整的哈夫曼树。接下来是对没个结点进 行编码，从第一个结点开始看它的双亲，若它双亲做左孩子则记0，若是右孩子 则记1，依次往上推，直到哈夫曼的根结点为止。记录
6、编码打印出来。为了体现程序中各个功能的独立性，结合JAVA语言的编程要求，对程序中 所用到的类和方法进行说明：1公共类Tree :组成哈夫曼树的最小单元。其成员变量有：1.1 lchild ：最小单元的左孩子。1.2 rchild:最小单元的右孩子。1.3 parents：最小单元的双亲。2公共类Huffman :描述哈夫曼编码的整个过程，其成员变量有：2.1 numsMo：储存要进行编码的一组数。2.2 nums :临时储存要进行编码的这组数，会随着后面的调用而变化。2.3 trees:储存哈夫曼树，由若干最小单元构成。2.4 temp :中间变量，是字符串类型。3 核心方法及流程3.1 m
7、ain 方法：用于程序的执行入口。其中定义了一个 Huff 类实体，调 用方法st ar t()完成数组初始排序，实现哈夫曼编码等一系列的操作。3.2 addNum 方法：用于方法初始化给定的要进行编码的数组，数组通过控 制台键盘录入。3.3 minTo 方法：在一组数中选择最小的两个，按递增顺序返回。3.4 compareNum方法：是公共类Huffman的核心算法之一，该方法是将一组 树形成哈夫曼树，左孩子为较小值。3.5 print方法：是公共类Huffman的核心算法之一，该方法利用递归打印 出编码。其流程图如下：三、实验步骤及结果分析测试数据：0.01 0.03 0.07 0.13
8、0.19 0.26 0.31程序运行：请输入一组数，中间用空格分隔：0.01 0.03 0.07 0.13 0.19 0.26 0.31输出结果为：0.0101000 码长： 50.0301001 码长： 50.070101 码长： 40.13011 码长： 30.1900 码长： 20.2610 码长： 20.3111 码长： 2心得体会：在本次的课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇 到了很多麻烦及困难。我的调试及其中的错误和我最终找出错误，修改为正确的 能够执行的程序中，通过分析，我学到了：在递归调用方法时最好不要有返回值， 否则会使程序变得逻辑混乱，复杂难懂；当从叶
9、结点向上编码时，根据本程序的 特点会有可能重复的tree，所以要分成同tree和不同tree进行不同的逻辑编程。通过本次的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及 哈夫曼编码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码 的知识，真正学会了一种算法。当求解一个算法时，不是拿到问题就不加思索地 做，而是首先要先对它有个大概的了解，接着再详细地分析每一不怎么做，无论 自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。四、程序设计源代码import java.util.ArrayList; import java.util.List;import
10、java.util.Scanner;public class Huffman private List nums; private List numsMo; private List trees; private String temp;public Huffman() nums = new ArrayList(); numsMo = new ArrayList(); trees = new ArrayList(); temp=;public void addNums() / 给定一组数System. out .println(请输入一组数，中间用空格分隔：);Scanner sca = ne
11、w Scanner(System. in);String str = sca.nextLine();String strs = str.split( );for (int i = 0; i strs.length; i+) nums.add(Double. parseDouble(strsi); numsMo.add(Double. parseDouble(strsi);publicvoidcompareNum(Listnums,Listtrees)/ 递归算法double min = new double2;if(nums.size()1)min = minTwo(nums);Tree t
12、= new Tree(min0,min1,min0+min1); nums.remove(Double. valueOf(min0); nums.remove(Double. valueOf(min1); nums.add(min0+min1);trees.add(t); compareNum(nums,trees);public void print(double num) / 递归打印编码for(Tree t : trees)if(num = t.getRchild() temp = 1+temp; print(t.getParents(); break;else if(num = t.g
13、etLchild()temp = 0+temp;print(t.getParents();break;public void write(double d)temp = ;System.out.print(d+ : ); print(d);System.out.print(temp);System, out.println (” 码长：+temp.length();public double minTwo(List nums) / 在一组数中选则最小的两个，按递增排序返回Double temp = 0.0;for ( int j = 0; j 2; j+) for (int i = 1; i
14、nums.size(); i+) if (nums.get(i - 1) 1)double mins = minTwo(numsMo); if(mins0!=mins1)numsMo.remove(Double. valueOf(mins0); write(mins0);if(! numsMo.isEmpty()write(numsMo.get(0);public static void main(String args) new Huffman().start();参考文献1（美）Stuart Reges,（美）Marty Stepp著 陈志等译，java程序设计教程，机械工业 出版社,20082 （英）David J.C.Mackay著肖明波，席斌，许芳，王建新译，信息论、推理与 学习算法，高等教育出版社， 2006
