Java哈夫曼编码译码器

哈夫曼编码/译码器课程设计（论文）任务书学院专业班课程名称面向对象技术课程设计题目哈夫曼编码/译码器任务起止日期：2010年12月06日～2010年12月24日学生姓名学号指导教师教研室主任年月日审查哈夫曼编码/译码器2课程设计（论文）任务一、课题内容1．[问题描述]利用哈夫曼编码进行数据通信可以大大提高信道利用率，缩短数据传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（还原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。2．[基本要求]一个完整的编/译码系统应具有以下功能：(1)建立哈夫曼树（Create）。从键盘输入字符集中的所有字符及其对应的频率值，建立哈夫曼树。(2)输出编码表（Table）。利用已建好的哈夫曼树，列出字符集中的所有字符及其对应的哈夫曼编码。(3)编码（Coding）。利用已建好的哈夫曼树，对从键盘输入的正文串进行编码，并在屏幕上显示结果。(4)译码（Decoding）。利用已建好的哈夫曼树，对从键盘输入的0、1代码串进行译码，并在屏幕上显示结果。3．[测试数据](1)利用下表中给出的字母/频率数据调试程序。字母CDEFKLUZ频率324212024742372（2）用下表中给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“IloveyouLoo”字母频率字母频率A77O67B17P20C32Q5D42R59E120S67F24T85G17U37H50V12I76W22J4X4哈夫曼编码/译码器3K7Y22L42Z2M24(空格)186N674．通过对本课题的实践以期使学生程序编写能力得到较大提高。二、课题要求1.使用Java完成本课题的程序设计，至少定义2个类；2.程序中必须有界面设计和事件处理，必要时要做容错处理（异常处理）；3.程序必须得到合理结果，并对所得结果做必要的分析；4.设计论文正文篇幅不少于3000字；5.提交的所有材料必须符合《长沙理工大学课程设计管理规定》（长理工大教[2005]8号）的要求。哈夫曼编码/译码器4三、课题完成后应提交的材料1.课程设计（论文）按以下排列顺序装订成册(1)封面（统一到学校教材中心领取，并详细填写）(2)任务书(3)中文摘要(4)英文摘要(5)目录(6)正文(7)参考文献(8)附件（源程序打印件）2.装订成册的论文装入资料袋资料袋统一到学校教材中心领取，并详细填写四、主要参考文献（由指导教师选定）[1]印旻．Java与面向对象程序设计教程．北京：高等教育出版社，1999.11[2]东方人华．Java2范例入门与提高．北京：清华大学出版社，2003.8[3]杨庚、王汝传.面向对象程序设计与C++语言.北京：人民邮电出版社，2002.7[4]希尔德（美）.Java编程起步.北京：人民邮电出版社，2001.5[5]罗省贤.Java程序设计教程（第五版）.北京：电子工业出版社，2007.1[6]张琛恩.面向对象的设计与模式.北京：电子工业出版社，2004.1注：1.此任务书由指导教师填写。如不够填写，可另加页。2.此任务书最迟必须在课程设计（论文）开始前下达给学生。哈夫曼编码/译码器5学生送交全部材料日期学生（签名）指导教师验收（签名）哈夫曼编码/译码器6摘要Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。它的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。本文根据Huffman编码原理，在详细设计中，根据权值和最小的根本原则，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点Node类，算法SuanFa类以及主类JieMian类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。在完成Huffman编码后，我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较，译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译码系统。关键词：Huffman编码树；最优二叉树；编码；译码哈夫曼编码/译码器7AbstractHuffmancodingisaencodingofvariablelengthandaspecialtransformationformofthebinarytree.Itsprincipleis:thecodethatbeusedmoreoftenwillbechangedintothecodeofshorterlengths,whilethecodesthatbeusedlessoftencanbetransformedintothecodeoflongerlengthsandtheuniquesolutionofcodingwillbekept.AccordingtothetheoryofHuffmancoding,firstlyweenterthecharactersetwhichwillbeusedtocodingandtheirweights.Secondly,accordingtothefundanmentalprinciplethatthesumoftheweightsneedstobethesmallest,theprogramdesignsHuffmantreeinaccordancewiththeseclasswhichareinitializedintheoutlinesuchasclassNode,classSuanFa,andclassJieMian.Atlast,thecomputerwilloutputHuffmancodingonuserinterface.Andthen,weusetheHuffmancodingtreetodecodingafterthecompletionofHuffmancodingtree.Herearedifferencewithencodingprocess.Wewillcomparethebinarystringthattheuserinputwiththecharactersetonebyoneduringtheprocesssofdecoding.Andthen,thecycleofthenextcharacterencodingwillcontinuewhichisbasedonthecompletionoftranslationofacharacter.Itwillbefinisheduntilallthebinarycodeistranslated.Duringtheprocessofcodinganddecoding,weencountermanyproblems,suchastheproblemonarithmeticandgrammar.However,wetryourbesttosolvetheseproblemsthroughconstantanalysisanddebugging.Eventually,weachievethegoalthatestablishacompletesystemoncodinganddecodingsuccessfully.KeyWords：Huffmancodingtree；optimalbinarytree；coding；decoding哈夫曼编码/译码器0目录一、需求分析………………………………………………………………………1二、概要设计………………………………………………………………………22.1开发环境……………………………………………………………………22.2程序执行的命令操作………………………………………………………22.3自定义类说明………………………………………………………………2三、详细设计………………………………………………………………………63.1哈夫曼编码/译码模拟器程序的Java类说明……………………………6四、设计和调试分析………………………………………………………………15五、用户手册………………………………………………………………………16六、测试结果………………………………………………………………………20七、参考文献八、附录哈夫曼编码/译码器1哈夫曼编码/译码器一．需求分析1.举例说明，先前快速远距离通信的主要手段是电报，即将需要传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现此处较多的字符尽可能短的编码，以减少数据传输经费。哈夫曼树就是根据此原理设计出来的一种存储结构。2.本程序要做的哈夫曼编码译码器的主要功能是：运用二叉树来设计二进制的前缀编码。根据用户给出字符集中的所有字符及其出现的频率（即为此字符的权值），建立哈夫曼编码树，然后利用哈夫曼编码树将输入的字符串编码成相应的哈夫曼编码；反之，根据哈夫曼译码原理将用户所输入的0/1代码串编译成相应的字符串。由此，让用户方便地实现电文词句的Huffman编码及译码。3.构成哈夫曼编码树的合法字符：字母（忽略大小写）和空格。4.演示程序以人机对话方式执行。5．演示程序中，当用户输入错误时，系统会输出相应的提示。6．程序执行的命令包括：（1）建树并输出编码表（2）编码（3）译码（4）清空哈夫曼编码/译码器2二．概要设计2.1开发环境开发平台：MicrosoftWindows7旗舰版开发工具：MyEclipse8.5JDK1.6.0_182.2程序执行的命令操作（1）建树并输出编码表：根据用户在“字符”文本域输入的字符集和在“权值”文本域输入的权值建立哈夫曼编码树，并在“结果”文本域中输出哈夫曼编码树中的每个字符及其对应的Huffman编码；（2）编码：利用建立好的哈夫曼编码树对用户在“词句”文本域中输入的电文字符进行编码，在“结果”中显示编码结果；（3）译码：利用建立好的哈夫曼编码树对用户在“编码”文本域中输入的0/1代码串进行译码，在“结果”中显示译码结果；（4）清空：清空已建立的哈夫曼编码树，重新操作。2.3自定义类说明本程序定义了三个类，分别实现树的节点操作，编码译码的算法实现，以及界面和事件处理，主要属性及算法如下：（1）类名：Node功能：作为节点类，实现节点的基本操作哈夫曼编码/译码器3主要属性privateintweight;//节点权值privatecharname;//节点字符名称privateintleft;//左孩子节点位置privateintright;//右孩子节点位置privateintparent;//父节点位置privateStringcode;//节点对应的编码主要方法publicNode()//构造方法初始化publicNode(intweight,charname)//带参数的构造方法，可初始化权值和字符名称publicintgetWeight()//获取节点权值publicvoidsetWeight(intweight)//设置节点权值publicchargetName()//获取节点字符名称publicvoidsetName(charname)//设置节点字符名称publicintgetLeft()//获得节点左孩子的位置值publicvoidsetLeft(intleft)//设置节点左孩子的位置值publicintgetRight()//获得节点右孩子的位置值publicvoidsetRight(intright)//设置右孩子的位置值publicintgetParent()//获得父节点的位置值publicvoidsetParent(intparent)//设置父节点的位置值publ