Java哈夫曼编码译码器.doc

《Java哈夫曼编码译码器.doc》由会员分享，可在线阅读，更多相关《Java哈夫曼编码译码器.doc（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-作者xxxx-日期xxxxJava哈夫曼编码译码器【精品文档】 课程设计（论文）任务书 学院 专业 班课程名称 面向对象技术课程设计 题 目 哈夫曼编码/译码器 任务起止日期： 2010 年12 月 06日 2010 年12月 24 日 学 生 姓 名 学 号 指 导 教 师 教研室主任 年 月 日审查课程设计（论文）任务一、课题内容1问题描述利用哈夫曼编码进行数据通信可以大大提高信道利用率，缩短数据传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（还原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

2、2基本要求一个完整的编/译码系统应具有以下功能：(1)建立哈夫曼树（Create）。从键盘输入字符集中的所有字符及其对应的频率值，建立哈夫曼树。(2)输出编码表（Table）。利用已建好的哈夫曼树，列出字符集中的所有字符及其对应的哈夫曼编码。(3)编码（Coding）。利用已建好的哈夫曼树，对从键盘输入的正文串进行编码，并在屏幕上显示结果。(4)译码（Decoding）。利用已建好的哈夫曼树，对从键盘输入的0、1代码串进行译码，并在屏幕上显示结果。3 测试数据(1)利用下表中给出的字母/频率数据调试程序。字母CDEFKLUZ频率324212024742372（2）用下表中给出的字符集和频度的实

3、际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“I love you Loo”字母频率字母频率A77O67B17P20C32Q5D42R59E120S67F24T85G17U37H50V12I76W22J4X4K7Y22L42Z2M24(空格)186N674通过对本课题的实践以期使学生程序编写能力得到较大提高。二、课题要求1. 使用Java完成本课题的程序设计，至少定义2个类；2. 程序中必须有界面设计和事件处理，必要时要做容错处理（异常处理）；3. 程序必须得到合理结果，并对所得结果做必要的分析；4. 设计论文正文篇幅不少于3000字；5. 提交的所有材料必须符合长沙理工大学课程设计管

4、理规定（长理工大教20058号）的要求。三、课题完成后应提交的材料1. 课程设计（论文）按以下排列顺序装订成册(1) 封面（统一到学校教材中心领取，并详细填写） (2) 任务书(3) 中文摘要(4) 英文摘要 (5) 目录 (6) 正文 (7) 参考文献(8) 附件（源程序打印件） 资料袋统一到学校教材中心领取，并详细填写四、主要参考文献（由指导教师选定）注：1. 此任务书由指导教师填写。如不够填写，可另加页。2. 此任务书最迟必须在课程设计（论文）开始前下达给学生。学生送交全部材料日期 学生（签名） 指导教师验收（签名） 摘要Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式

5、。它的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。本文根据Huffman编码原理，在详细设计中，根据权值和最小的根本原则，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点Node类，算法SuanFa类以及主类JieMian类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。在完成Huffman编码后，我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较，译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。在编码和译码

6、的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译码系统。关键词：Huffman编码树；最优二叉树；编码；译码AbstractHuffman coding is a encoding of variable length and a special transformation form of the binary tree. Its principle is: the code that be used more often will be changed into the code of shorter length

7、s, while the codes that be used less often can be transformed into the code of longer lengths and the unique solution of coding will be kept. According to the theory of Huffman coding, firstly we enter the character set which will be used to coding and their weights. Secondly, according to the funda

8、nmental principle that the sum of the weights needs to be the smallest , the program designs Huffman tree in accordance with these class which are initialized in the outline such as class Node,class SuanFa,and class JieMian. At last, the computer will output Huffman coding on user interface.And then

9、, we use the Huffman coding tree to decoding after the completion of Huffman coding tree.Here are difference with encoding process. We will compare the binary string that the user input with the character set one by one during the processs of decoding .And then, the cycle of the next character encod

10、ing will continue which is based on the completion of translation of a character. It will be finished until all the binary code is translated.During the process of coding and decoding, we encounter many problems, such as the problem on arithmetic and grammar. However, we try our best to solve these

11、problems through constant analysis and debugging.Eventually, we achieve the goal that establish a complete system on coding and decoding successfully.Key Words：Huffman coding tree；optimal binary tree；coding；decoding【精品文档】目录一、需求分析1二、概要设计2222三、详细设计66四、设计和调试分析15五、用户手册16六、测试结果20七、参考文献八、附录哈夫曼编码/译码器一需求分析1

12、.举例说明，先前快速远距离通信的主要手段是电报，即将需要传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现此处较多的字符尽可能短的编码，以减少数据传输经费。哈夫曼树就是根据此原理设计出来的一种存储结构。2.本程序要做的哈夫曼编码译码器的主要功能是：运用二叉树来设计二进制的前缀编码。根据用户给出字符集中的所有字符及其出现的频率（即为此字符的权值），建立哈夫曼编码树，然后利用哈夫曼编码树将输入的字符串编码成相应的哈夫曼编码；反之，根据哈夫曼译码原理将用户所输入的0/1代码串编译成相应的字符串。由此，让用户方便地实现电文词句

13、的Huffman编码及译码。3.构成哈夫曼编码树的合法字符：字母（忽略大小写）和空格。4.演示程序以人机对话方式执行。5演示程序中，当用户输入错误时，系统会输出相应的提示。6程序执行的命令包括：（1）建树并输出编码表（2）编码（3） 译码（4） 清空二概要设计开发平台：Microsoft Windows7旗舰版JDK（1）建树并输出编码表：根据用户在“字符”文本域输入的字符集和在“权值”文本域输入的权值建立哈夫曼编码树，并在“结果”文本域中输出哈夫曼编码树中的每个字符及其对应的Huffman编码；（2）编码：利用建立好的哈夫曼编码树对用户在“词句”文本域中输入的电文字符进行编码，在“结果”中显

14、示编码结果；（3）译码：利用建立好的哈夫曼编码树对用户在“编码”文本域中输入的0/1代码串进行译码，在“结果”中显示译码结果；（4）清空：清空已建立的哈夫曼编码树，重新操作。本程序定义了三个类，分别实现树的节点操作，编码译码的算法实现，以及界面和事件处理，主要属性及算法如下：（1）类名：Node功能：作为节点类，实现节点的基本操作主要属性private int weight;/节点权值private char name;/节点字符名称private int left;/左孩子节点位置private int right;/右孩子节点位置private int parent;/父节点位置priva

15、te String code;/节点对应的编码主要方法public Node() /构造方法初始化public Node(int weight,char name) /带参数的构造方法，可初始化权值和字符名称public int getWeight() /获取节点权值public void setWeight(int weight) /设置节点权值public char getName()/获取节点字符名称public void setName(char name)/设置节点字符名称public int getLeft()/获得节点左孩子的位置值public void setLeft(int

16、left)/设置节点左孩子的位置值public int getRight()/获得节点右孩子的位置值public void setRight(int right)/设置右孩子的位置值public int getParent()/获得父节点的位置值public void setParent(int parent) /设置父节点的位置值public String getCode()/获得节点的编码public void setCode(String code)/设置节点的编码public boolean isLeaf() /判断节点是否为叶子节点（2）类名：SuanFa功能：算法类，实现哈夫曼编码

17、树的构造，编码和译码等操作主要属性private List nodes;/定义Node类型的动态数组nodes存放Huffman编码树主要方法public List getNodes()public void setNodes(List nodes)public SuanFa(List nodes) /构造方法public int getRoot() /获取已经构造好的huffman编码树的根节点public int selectMinNode() /选择权值最小节点，保存其下标，并统计剩余的没有进树的节点数public void JianShu() /建立哈夫曼树public String

18、getCode(int i) /获得节点的单个编码public void bianMa1() /从叶子到根对字符集中各个字符进行编码public String bianMa2(String names) /编码方法, 对输入的词句字符进行编码public String jieMa(String codes) /译码方法(3)类名：JieMian（主类）功能：设置界面及其相关操作和监听者设置主要属性private static final long serialVersionUID = 1L;private TextArea textName;/字符文本域private TextArea tex

19、tWeight; /权值文本域private TextArea textResult; /结果文本域private SuanFa suanFa;/算法类对象suanFaprivate TextArea textArea;标签及按钮：private Label label;/字符、词句标签private Label label_1;/权值、编码标签private Button button;/建树按钮private Button button_4;/清空按钮private Button button_2;/编码按钮private Button button_3;/译码按钮主要方法public v

20、oid init()/界面操作及监听者设置三 详细设计（1）节点类Node类的设计及功能描述：A属性设计：构造哈夫曼编码树需要考虑节点结构问题，编码和译码过程中，对二叉树的建立以及查找操作要求Node类中的节点结构包含六个属性，分别用于存放节点权值，节点字符，左孩子节点的位置下标，右孩子节点的位置下标，父节点的位置下标以及该节点对应的编码。B方法设计：节点类的方法主要用于对节点属性值的操作。在主类中通过调用节点对象的方法，完成对节点对象属性值的操作。主要操作分别有构造方法对属性值初始化，获取各个属性值操作，改变各属性值操作。由于查找二叉树的过程中需要判断是否到达叶子节点，所以必不可少的还有判断

21、该节点是否为叶子节点的操作。class Node /节点类private int weight;/weight存放节点权值private char name;/name存放节点字符private int left;/存放左孩子节点位置下标private int right;/右孩子节点位置下标private int parent;/父节点位置下标private String code;/节点对应的编码public Node() /无参构造方法初始化初始化左右孩子属性，权值属性及父节点属性public Node(int weight,char name) /带参数的构造方法，可利用参数初始化权值

22、和字符名称this.weight=weight;this.name=name;剩余属性初始化；public int getWeight() 返回节点权值 public void setWeight(int weight) 设置节点权值 public char getName() 返回节点字符 public void setName(char name) 设置节点字符public int getLeft() 返回节点左孩子位置下标public void setLeft(int left) 设置节点左孩子位置下标public int getRight() 返回节点右孩子位置下标public voi

23、d setRight(int right) 设置节点右孩子位置下标public int getParent() 返回父节点位置下标public void setParent(int parent) 返设置父节点位置下标public String getCode() 返回节点编码public void setCode(String code) 设置节点编码public boolean isLeaf()/判断节点是否为叶子节点if(left!=-1|right!=-1)若节点存在左右孩子，则返回falseelse否则返回true（2）算法类SuanFa类的设计及功能描述：A属性设计：以Node类类

24、型，定义动态数组nodes，数组下标即为节点的位置，整个数组用于建立和存放Huffman编码树。private List nodes;/定义Node类型的动态数组 nodes存放Huffman编码树 B方法设计：程序运行时的要求建立Huffman编码树，建树过程中需反复从剩余节点中选取权值最小的节点加入到编码树中，因此设计public int selectMinNode()方法选择权值最小节点，保存其下标，并统计剩余的没有进树的节点数。通过建树方法public void JianShu()循环调用selectMinNode()方法，完成从叶子节点到根节点的建树过程。建立编码树后，由public

25、 void bianMa1()方法从叶子节点到根节点对字符集中各字符的编码，由 public String bianMa2(String names)方法对输入的词句字符查找编码表进行编码，public String jieMa(String codes)方法对输入的0/1码串，利用编码表从根节点到叶子节点进行译码。编码和译码的结果都可在结果文本域中输出显示。SuanFa类中主要方法的算法伪代码：class SuanFa private List nodes;/定义Node类型的动态数组 nodes存放编码树public SuanFa(List nodes) /构造函数 继承父类构造函数，并初

26、始化nodes数组public int getRoot()/获取已经构造好的huffman编码树的根节点for(从nodes数组第一到最后一个元素) 若第i个元素节点的父节点域值为-1；则index用i赋值；return index;/返回根节点public int selectMinNode()/选择权值最小节点，保存其下标，并统计剩余的没有进树的节点数int index=-1;/index存放权值最小节点的下标值if(null!=nodes&nodes.size()!=0)/如果数组非空，则选取权值最小的节点for(int i=0;inodes.get(i).getWeight()用nod

27、e记录权值最小的节点，index记录其下标return new intindex,count;/返回权值最小节点的下标和未进树的节点数public void JianShu()/建立哈夫曼编码树int min=selectMinNode();/选取权值最小的节点while(min11|sum%2!=0) /每两个节点生成一个新的节点if(sum%2=0)取到第一个节点时，新建一个父节点else 当取到第二个节点时，将其权值加到新建的父节点中newNode.setWeight(newNode.getWeight()+node.getWeight();min=selectMinNode();/继续

28、选取下一个权值最小的节点public String getCode(int i)/获得节点的单个编码Node pNode=nodes.get(nodes.get(i).getParent();判断，若此节点是其父节点的左孩子则返回0否则为1；public void bianMa1()/从叶子到根对字符集中各个字符进行编码for(int i=0;inodes.size();i+)if(nodes.get(i).isLeaf()/若节点i为叶子，则获取其编码while(parent!=-1)/该节点i不是根节点，则循环记录0/1码串，从叶子到根编码nodes.get(i).setCode(code

29、);/存放节点i的编码public String bianMa2(String names)/编码方法对输入的词句字符进行编码for(int i=0;inames.length();i+)/从词句中第一个字符开始编码for(int j=0;jnodes.size();j+)查找编码表中是否存在该字符/若在编码表中找到该字符icodes+=nodes.get(j).getCode();/则在codes中记录其编码break;/跳出内循环，继续查找下一个字符的编码else if(j=nodes.size()-1) /若找不到该字符，则返回操作提示语return names.charAt(i)+没在

30、编码表中！请重新操作！;return codes;/返回词句编码结果public String jieMa(String codes)/译码方法for(int i=0,j=root;icodes.length();i+)/从根节点到叶子节点进行译码if(codes.charAt(i)=0)/若编码为0，二叉树向左查找j=nodes.get(j).getLeft();else if(codes.charAt(i)=1)/编码为1，二叉树向右查找else/编码含有非0，1字符，则输出提示语return 编码有误，请检查后重新输入！;若节点为叶子节点，则译码成功；j=root; /j用根节点位置赋值

31、，继续下一个译码return names;/返回译码结果（3）主类JieMian类的设计及功能描述：属性设计：JieMian类主要作用是对界面的设计，以及设计监听者对各种事件进行响应和处理。主要界面组件有字符标签，权值标签，字符输入文本框，权值输入文本框，结果输出文本框，建树并输出编码表按钮，编码按钮，译码按钮，清空按钮。方法设计：在public void init()方法中，对建树并输出编码表按钮，编码按钮，译码按钮和清空按钮分别设置ActionListener()监听者，监听按钮点击事件，并分别对不同情况作出响应的异常处理。init方法伪码如下：public void init() but

32、ton = new Button(u5EFAu6811u5E76u8F93u51FAu7F16u7801u8868);button.addActionListener(new ActionListener()/设置建树按钮监听者public void actionPerformed(ActionEvent e) /点击按钮事件响应trytextResult.setText();/清空结果文本框获取节点字符，及其权值；若字符文本域为空，则提示请输入字符，返回空值；若权值文本域为空，则提示请输入对应权值，返回空；for(int i=0;istrNames.length();i+)/检查输入字符集是

33、否有重复for(int j=i+1;jstrNames.length();j+)若有重复字符，则输出提示语textResult.setText(字符不能重复，（忽略大小写）);return;如果字符和权值不完全对应，提示重新输入textResult.setText(字符和权值不能完全对应！请检查后重新输入！);return;int weightsOfNum=new intweights.length;/定义整型数组weightsOfNum，存放权值；for(int i=0;iweights.length;i+)/将权值字符串转化为整型权值存放于weightsOfNum中weightsOfNum

34、i=Integer.parseInt(weightsi);suanFa=new SuanFa(nodes);/新建SuanFa类对象suanFasuanFa.JianShu();/调用suanFa对象的 JianShu方法，建立huffman编码树suanFa.bianMa1();/调用biamMa1方法，对字符集各字符编码for(int i=0;isuanFa.getNodes().size();i+)if(suanFa.getNodes().get(i).isLeaf()设置字符集及其对应的编码，存放于字符串biao中输出字符集及其对应的编码于结果文本域中；label.setText(词句

35、:);/哈夫曼树建立成功后，更改标签label_1.setText(编码：);button_2.setEnabled(true);/编码按钮设为可用状态button_3.setEnabled(true);/译码按钮设为可用状态button.setEnabled(false);/建树按钮设为不可用状态catch(Exception ee)/捕捉编码树建立过程中所有非法数据输入异常textResult.setText(处理数据发生异常，请检查数据输入是否合法！););button_2.addActionListener(new ActionListener() /设置编码按钮的监听者public

36、void actionPerformed(ActionEvent e) 若输入词句为空，则提示输入词句；String result=suanFa.bianMa2(ciJu);/调用对象的bianMa2方法对词句进行编码并写入结果文本域中);button_3.addActionListener(new ActionListener() /设置译码按钮监听者public void actionPerformed(ActionEvent e) 若输入编码为空，则提示输入编码；textResult.setText(suanFa.jieMa(codes););button_4.addActionList

37、ener(new ActionListener() /设置清空按钮监听者public void actionPerformed(ActionEvent e) 所有标签及文本域重置空值；建树按钮设为可用，编码按钮和译码按钮设为不可用label.setText(字符:);/更改标签初始值为字符label_1.setText(权值：);/更改标签1初始值为权值suanFa对象重置空值；);textArea.setForeground(Color.RED);/提示语文本框字体红色textArea.setBackground(Color.WHITE);/背景颜色设为白色textArea.setText(

38、输入时的注意事项文字);textArea.setBounds(496, 31, 120, 343);add(textArea);四 设计和调试分析在实验调试过程中，碰到的问题很多：一是语法相关的问题，由于是上学期学的java面向对象程序设计，很多语法规则记忆不是很深，不过通过查阅各种书籍文献以及编译器的编译很容易就解决了。二是算法方面的问题，写selectMinNode()方法的时候，首先想到要用排序算法，考虑用冒泡排序的时候发现由于要交换结点在数组中的位置，而nodes结点数组为全局属性，在很多其他方法中需要使用，这样的话会破坏数据结构 。最后考虑直接选出权值最小的元素，而要找出权值次小的元

39、素，就要在第一次循环找出最小的元素时将其排除，因此想到通过判断节点是否存在父节点，来判断其是否已被选取，然后在建树方法中通过while循环调用selectMinNode()方法，选出第一个权值最小节点时，生成一个父节点，选出权值次小节点时，将已生成的父节点位置下标赋值给其父节点域为，这样，每两个节点生成一个父节点，顺利完成了哈夫曼编码树的建立。三是数组的内存分配和越界的问题。一开始把节点数组nodes设置为最大长度为Max的定长数组，后来发现在建树过程中，nodes数组长度需要随着huffman树的建立不断增加父节点，调试过程中发生数组越界，为此纠结了很久。后来终于学会了利用List动态数组，

40、定义一个Node类类型的动态数组nodes，在建立huffman编码树的过程中动态建立节点，在nodes数组中成功建立了huffman编码树。此后，在编码方法和译码方法中，通过huffman编码树，很容易完成了从叶子节点到根节点的编码过程和从根节点到叶子节点的译码过程。最后， JieMian类中，设置了用户输入提示语，并在用户非法输入时，作出响应的异常处理，并显示操作提示语。在原有程序基础上，将录入的字符集中的字符全部转换为大写字母，允许用户在输入词句进行编码时，将大小写字母混合输入，但大小写字母做同样处理。五 用户手册1.本程序的运行环境为Microsoft Windows7操作系统，运行123.html文件即可;2.进入演示程序以后，首先显示界面如下：建立huffman树之前，编码，译码按钮不可用。3.根据注意文本提示，用户输入字符集中的字符，和字符对应的权值，点击建树并输出编码表按钮，则程序建立huffman树，并在结果中输出字符集中各个字符对应的编码。输入字符时，连续输入不需分隔，输入权值