Java哈夫曼編碼譯碼器

1、課程設(shè)計(jì)（論文）任務(wù)書 學(xué)院 專業(yè) 班課程名稱 面向?qū)ο蠹夹g(shù)課程設(shè)計(jì) 題 目 哈夫曼編碼/譯碼器 任務(wù)起止日期： 2010 年12 月 06日 2010 年12月 24 日 學(xué) 生 姓 名 學(xué) 號(hào) 指 導(dǎo) 教 師 教研室主任 年 月 日審查課程設(shè)計(jì)（論文）任務(wù)一、課題內(nèi)容1問(wèn)題描述利用哈夫曼編碼進(jìn)行數(shù)據(jù)通信可以大大提高信道利用率，縮短數(shù)據(jù)傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（還原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。2基本要求一個(gè)完整的編/譯碼系統(tǒng)應(yīng)具有以下功能：(1)建立哈夫曼樹

2、（Create）。從鍵盤輸入字符集中的所有字符及其對(duì)應(yīng)的頻率值，建立哈夫曼樹。(2)輸出編碼表（Table）。利用已建好的哈夫曼樹，列出字符集中的所有字符及其對(duì)應(yīng)的哈夫曼編碼。(3)編碼（Coding）。利用已建好的哈夫曼樹，對(duì)從鍵盤輸入的正文串進(jìn)行編碼，并在屏幕上顯示結(jié)果。(4)譯碼（Decoding）。利用已建好的哈夫曼樹，對(duì)從鍵盤輸入的0、1代碼串進(jìn)行譯碼，并在屏幕上顯示結(jié)果。3 測(cè)試數(shù)據(jù)(1)利用下表中給出的字母/頻率數(shù)據(jù)調(diào)試程序。字母CDEFKLUZ頻率324212024742372（2）用下表中給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“I love

3、 you Loo”字母頻率字母頻率A77O67B17P20C32Q5D42R59E120S67F24T85G17U37H50V12I76W22J4X4K7Y22L42Z2M24(空格)186N674通過(guò)對(duì)本課題的實(shí)踐以期使學(xué)生程序編寫能力得到較大提高。二、課題要求1. 使用Java完成本課題的程序設(shè)計(jì)，至少定義2個(gè)類；2. 程序中必須有界面設(shè)計(jì)和事件處理，必要時(shí)要做容錯(cuò)處理（異常處理）；3. 程序必須得到合理結(jié)果，并對(duì)所得結(jié)果做必要的分析；4. 設(shè)計(jì)論文正文篇幅不少于3000字；5. 提交的所有材料必須符合長(zhǎng)沙理工大學(xué)課程設(shè)計(jì)管理規(guī)定（長(zhǎng)理工大教20058號(hào)）的要求。三、課題完成后應(yīng)提交的材料

4、1. 課程設(shè)計(jì)（論文）按以下排列順序裝訂成冊(cè)(1) 封面（統(tǒng)一到學(xué)校教材中心領(lǐng)取，并詳細(xì)填寫） (2) 任務(wù)書(3) 中文摘要(4) 英文摘要 (5) 目錄 (6) 正文 (7) 參考文獻(xiàn)(8) 附件（源程序打印件）2.裝訂成冊(cè)的論文裝入資料袋 資料袋統(tǒng)一到學(xué)校教材中心領(lǐng)取，并詳細(xì)填寫四、主要參考文獻(xiàn)（由指導(dǎo)教師選定）1 印旻Java與面向?qū)ο蟪绦蛟O(shè)計(jì)教程北京：高等教育出版社，1999.112 東方人華Java 2 范例入門與提高北京：清華大學(xué)出版社，2003.83 楊庚、王汝傳.面向?qū)ο蟪绦蛟O(shè)計(jì)與C+語(yǔ)言.北京：人民郵電出版社，2002.74 希爾德（美）.Java編程起步.北京：人民郵電出

5、版社，2001.55 羅省賢.Java程序設(shè)計(jì)教程（第五版）.北京：電子工業(yè)出版社，2007.16 張琛恩.面向?qū)ο蟮脑O(shè)計(jì)與模式.北京：電子工業(yè)出版社，2004.1注：1. 此任務(wù)書由指導(dǎo)教師填寫。如不夠填寫，可另加頁(yè)。2. 此任務(wù)書最遲必須在課程設(shè)計(jì)（論文）開始前下達(dá)給學(xué)生。學(xué)生送交全部材料日期 學(xué)生（簽名） 指導(dǎo)教師驗(yàn)收（簽名） 摘要Huffman編碼是一種可變長(zhǎng)編碼方式，是二叉樹的一種特殊轉(zhuǎn)化形式。它的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長(zhǎng)度較短的編碼，而使用次數(shù)少的可以使用較長(zhǎng)的編碼，并且保持編碼的唯一可解性。本文根據(jù)Huffman編碼原理，在詳細(xì)設(shè)計(jì)中，根據(jù)權(quán)值和最小的根本原則，我們輸入

6、要編碼的字符集及其它的權(quán)值，再根據(jù)在概要設(shè)計(jì)中提到的節(jié)點(diǎn)Node類，算法SuanFa類以及主類JieMian類，建立哈夫曼樹，并進(jìn)行編碼，最后輸出哈夫曼編碼。在完成Huffman編碼后，我們利用其構(gòu)建的哈夫曼編碼樹來(lái)進(jìn)行譯碼。與編碼過(guò)程不同，譯碼過(guò)程中，我們將用戶輸入的二進(jìn)制代碼串依次與字符集中的每個(gè)字符的編碼進(jìn)行比較，譯出一個(gè)字符后，循環(huán)比較下一個(gè)字符的編碼，直到所有二進(jìn)制碼全部譯出為止。在編碼和譯碼的過(guò)程中，我們遇到很多問(wèn)題，諸如算法、語(yǔ)法問(wèn)題，但我們都通過(guò)不斷的分析，和調(diào)試將這些問(wèn)題一一解決，最終建立了一個(gè)完整的編/譯碼系統(tǒng)。關(guān)鍵詞：Huffman編碼樹；最優(yōu)二叉樹；編碼；譯碼Abstr

7、actHuffman 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 lengths, while the codes that be used less often can be transformed into the code of longer lengths and

8、 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 fundanmental principle that the sum of the weights needs to be the smallest , the program designs Huff

9、man 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, we use the Huffman coding tree to decoding after the completion of Huffman coding tree.Here are

10、 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 encoding will continue which is based on the completion of translation of a character. It will be fini

11、shed 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 problems through constant analysis and debugging.Eventually, we achieve the goal that establish a

12、 complete system on coding and decoding successfully.Key Words：Huffman coding tree；optimal binary tree；coding；decoding目錄一、需求分析1二、概要設(shè)計(jì)22.1開發(fā)環(huán)境22.2程序執(zhí)行的命令操作22.3自定義類說(shuō)明2三、詳細(xì)設(shè)計(jì)63.1哈夫曼編碼/譯碼模擬器程序的Java類說(shuō)明6四、設(shè)計(jì)和調(diào)試分析15五、用戶手冊(cè)16六、測(cè)試結(jié)果20七、參考文獻(xiàn)八、附錄哈夫曼編碼/譯碼器一需求分析1.舉例說(shuō)明，先前快速遠(yuǎn)距離通信的主要手段是電報(bào)，即將需要傳送的文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串。在

13、傳送電文時(shí)，希望總長(zhǎng)盡可能的短，如果對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，且讓電文中出現(xiàn)此處較多的字符盡可能短的編碼，以減少數(shù)據(jù)傳輸經(jīng)費(fèi)。哈夫曼樹就是根據(jù)此原理設(shè)計(jì)出來(lái)的一種存儲(chǔ)結(jié)構(gòu)。2.本程序要做的哈夫曼編碼譯碼器的主要功能是：運(yùn)用二叉樹來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼。根據(jù)用戶給出字符集中的所有字符及其出現(xiàn)的頻率（即為此字符的權(quán)值），建立哈夫曼編碼樹，然后利用哈夫曼編碼樹將輸入的字符串編碼成相應(yīng)的哈夫曼編碼；反之，根據(jù)哈夫曼譯碼原理將用戶所輸入的0/1代碼串編譯成相應(yīng)的字符串。由此，讓用戶方便地實(shí)現(xiàn)電文詞句的Huffman編碼及譯碼。3.構(gòu)成哈夫曼編碼樹的合法字符：字母（忽略大小寫）和空格。4.演示程序以人

14、機(jī)對(duì)話方式執(zhí)行。5演示程序中，當(dāng)用戶輸入錯(cuò)誤時(shí)，系統(tǒng)會(huì)輸出相應(yīng)的提示。6程序執(zhí)行的命令包括：（1）建樹并輸出編碼表（2）編碼（3） 譯碼（4） 清空二概要設(shè)計(jì)2.1開發(fā)環(huán)境開發(fā)平臺(tái)：Microsoft Windows7旗艦版開發(fā)工具：MyEclipse8.5JDK2.2程序執(zhí)行的命令操作（1）建樹并輸出編碼表：根據(jù)用戶在“字符”文本域輸入的字符集和在“權(quán)值”文本域輸入的權(quán)值建立哈夫曼編碼樹，并在“結(jié)果”文本域中輸出哈夫曼編碼樹中的每個(gè)字符及其對(duì)應(yīng)的Huffman編碼；（2）編碼：利用建立好的哈夫曼編碼樹對(duì)用戶在“詞句”文本域中輸入的電文字符進(jìn)行編碼，在“結(jié)果”中顯示編碼結(jié)果；（3）譯碼：利用建

15、立好的哈夫曼編碼樹對(duì)用戶在“編碼”文本域中輸入的0/1代碼串進(jìn)行譯碼，在“結(jié)果”中顯示譯碼結(jié)果；（4）清空：清空已建立的哈夫曼編碼樹，重新操作。2.3自定義類說(shuō)明本程序定義了三個(gè)類，分別實(shí)現(xiàn)樹的節(jié)點(diǎn)操作，編碼譯碼的算法實(shí)現(xiàn)，以及界面和事件處理，主要屬性及算法如下：（1）類名：Node功能：作為節(jié)點(diǎn)類，實(shí)現(xiàn)節(jié)點(diǎn)的基本操作主要屬性private int weight;/節(jié)點(diǎn)權(quán)值private char name;/節(jié)點(diǎn)字符名稱private int left;/左孩子節(jié)點(diǎn)位置private int right;/右孩子節(jié)點(diǎn)位置private int parent;/父節(jié)點(diǎn)位置private Str

16、ing code;/節(jié)點(diǎn)對(duì)應(yīng)的編碼主要方法public Node() /構(gòu)造方法初始化public Node(int weight,char name) /帶參數(shù)的構(gòu)造方法，可初始化權(quán)值和字符名稱public int getWeight() /獲取節(jié)點(diǎn)權(quán)值public void setWeight(int weight) /設(shè)置節(jié)點(diǎn)權(quán)值public char getName()/獲取節(jié)點(diǎn)字符名稱public void setName(char name)/設(shè)置節(jié)點(diǎn)字符名稱public int getLeft()/獲得節(jié)點(diǎn)左孩子的位置值public void setLeft(int left)/

17、設(shè)置節(jié)點(diǎn)左孩子的位置值public int getRight()/獲得節(jié)點(diǎn)右孩子的位置值public void setRight(int right)/設(shè)置右孩子的位置值public int getParent()/獲得父節(jié)點(diǎn)的位置值public void setParent(int parent) /設(shè)置父節(jié)點(diǎn)的位置值public String getCode()/獲得節(jié)點(diǎn)的編碼public void setCode(String code)/設(shè)置節(jié)點(diǎn)的編碼public boolean isLeaf() /判斷節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)（2）類名：SuanFa功能：算法類，實(shí)現(xiàn)哈夫曼編碼樹的構(gòu)造，編

18、碼和譯碼等操作主要屬性private List<Node> nodes;/定義Node類型的動(dòng)態(tài)數(shù)組nodes存放Huffman編碼樹主要方法public List<Node> getNodes()public void setNodes(List<Node> nodes)public SuanFa(List<Node> nodes) /構(gòu)造方法public int getRoot() /獲取已經(jīng)構(gòu)造好的huffman編碼樹的根節(jié)點(diǎn)public int selectMinNode() /選擇權(quán)值最小節(jié)點(diǎn)，保存其下標(biāo)，并統(tǒng)計(jì)剩余的沒(méi)有進(jìn)樹的節(jié)點(diǎn)數(shù)p

19、ublic void JianShu() /建立哈夫曼樹public String getCode(int i) /獲得節(jié)點(diǎn)的單個(gè)編碼public void bianMa1() /從葉子到根對(duì)字符集中各個(gè)字符進(jìn)行編碼public String bianMa2(String names) /編碼方法, 對(duì)輸入的詞句字符進(jìn)行編碼public String jieMa(String codes) /譯碼方法(3)類名：JieMian（主類）功能：設(shè)置界面及其相關(guān)操作和監(jiān)聽者設(shè)置主要屬性private static final long serialVersionUID = 1L;private Te

20、xtArea textName;/字符文本域private TextArea textWeight; /權(quán)值文本域private TextArea textResult; /結(jié)果文本域private SuanFa suanFa;/算法類對(duì)象suanFaprivate TextArea textArea;標(biāo)簽及按鈕：private Label label;/字符、詞句標(biāo)簽private Label label_1;/權(quán)值、編碼標(biāo)簽private Button button;/建樹按鈕private Button button_4;/清空按鈕private Button button_2;/編碼按

21、鈕private Button button_3;/譯碼按鈕主要方法public void init()/界面操作及監(jiān)聽者設(shè)置三 詳細(xì)設(shè)計(jì)3.1哈夫曼編碼/譯碼模擬器程序的Java類說(shuō)明（1）節(jié)點(diǎn)類Node類的設(shè)計(jì)及功能描述：A屬性設(shè)計(jì)：構(gòu)造哈夫曼編碼樹需要考慮節(jié)點(diǎn)結(jié)構(gòu)問(wèn)題，編碼和譯碼過(guò)程中，對(duì)二叉樹的建立以及查找操作要求Node類中的節(jié)點(diǎn)結(jié)構(gòu)包含六個(gè)屬性，分別用于存放節(jié)點(diǎn)權(quán)值，節(jié)點(diǎn)字符，左孩子節(jié)點(diǎn)的位置下標(biāo)，右孩子節(jié)點(diǎn)的位置下標(biāo)，父節(jié)點(diǎn)的位置下標(biāo)以及該節(jié)點(diǎn)對(duì)應(yīng)的編碼。B方法設(shè)計(jì)：節(jié)點(diǎn)類的方法主要用于對(duì)節(jié)點(diǎn)屬性值的操作。在主類中通過(guò)調(diào)用節(jié)點(diǎn)對(duì)象的方法，完成對(duì)節(jié)點(diǎn)對(duì)象屬性值的操作。主要操作分別有

22、構(gòu)造方法對(duì)屬性值初始化，獲取各個(gè)屬性值操作，改變各屬性值操作。由于查找二叉樹的過(guò)程中需要判斷是否到達(dá)葉子節(jié)點(diǎn)，所以必不可少的還有判斷該節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)的操作。class Node /節(jié)點(diǎn)類private int weight;/weight存放節(jié)點(diǎn)權(quán)值private char name;/name存放節(jié)點(diǎn)字符private int left;/存放左孩子節(jié)點(diǎn)位置下標(biāo)private int right;/右孩子節(jié)點(diǎn)位置下標(biāo)private int parent;/父節(jié)點(diǎn)位置下標(biāo)private String code;/節(jié)點(diǎn)對(duì)應(yīng)的編碼public Node() /無(wú)參構(gòu)造方法初始化初始化左右孩子屬

23、性，權(quán)值屬性及父節(jié)點(diǎn)屬性public Node(int weight,char name) /帶參數(shù)的構(gòu)造方法，可利用參數(shù)初始化權(quán)值和字符名稱this.weight=weight;=name;剩余屬性初始化；public int getWeight() 返回節(jié)點(diǎn)權(quán)值 public void setWeight(int weight) 設(shè)置節(jié)點(diǎn)權(quán)值 public char getName() 返回節(jié)點(diǎn)字符 public void setName(char name) 設(shè)置節(jié)點(diǎn)字符public int getLeft() 返回節(jié)點(diǎn)左孩子位置下標(biāo)public void setLef

24、t(int left) 設(shè)置節(jié)點(diǎn)左孩子位置下標(biāo)public int getRight() 返回節(jié)點(diǎn)右孩子位置下標(biāo)public void setRight(int right) 設(shè)置節(jié)點(diǎn)右孩子位置下標(biāo)public int getParent() 返回父節(jié)點(diǎn)位置下標(biāo)public void setParent(int parent) 返設(shè)置父節(jié)點(diǎn)位置下標(biāo)public String getCode() 返回節(jié)點(diǎn)編碼public void setCode(String code) 設(shè)置節(jié)點(diǎn)編碼public boolean isLeaf()/判斷節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)if(left!=-1|right!=-1

25、)若節(jié)點(diǎn)存在左右孩子，則返回falseelse否則返回true（2）算法類SuanFa類的設(shè)計(jì)及功能描述：A屬性設(shè)計(jì)：以Node類類型，定義動(dòng)態(tài)數(shù)組nodes，數(shù)組下標(biāo)即為節(jié)點(diǎn)的位置，整個(gè)數(shù)組用于建立和存放Huffman編碼樹。private List<Node> nodes;/定義Node類型的動(dòng)態(tài)數(shù)組 nodes存放Huffman編碼樹 B方法設(shè)計(jì)：程序運(yùn)行時(shí)的要求建立Huffman編碼樹，建樹過(guò)程中需反復(fù)從剩余節(jié)點(diǎn)中選取權(quán)值最小的節(jié)點(diǎn)加入到編碼樹中，因此設(shè)計(jì)public int selectMinNode()方法選擇權(quán)值最小節(jié)點(diǎn)，保存其下標(biāo)，并統(tǒng)計(jì)剩余的沒(méi)有進(jìn)樹的節(jié)點(diǎn)數(shù)。通過(guò)

26、建樹方法public void JianShu()循環(huán)調(diào)用selectMinNode()方法，完成從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的建樹過(guò)程。建立編碼樹后，由public void bianMa1()方法從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)對(duì)字符集中各字符的編碼，由 public String bianMa2(String names)方法對(duì)輸入的詞句字符查找編碼表進(jìn)行編碼，public String jieMa(String codes)方法對(duì)輸入的0/1碼串，利用編碼表從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)進(jìn)行譯碼。編碼和譯碼的結(jié)果都可在結(jié)果文本域中輸出顯示。SuanFa類中主要方法的算法偽代碼：class SuanFa private L

27、ist<Node> nodes;/定義Node類型的動(dòng)態(tài)數(shù)組 nodes存放編碼樹public SuanFa(List<Node> nodes) /構(gòu)造函數(shù) 繼承父類構(gòu)造函數(shù)，并初始化nodes數(shù)組public int getRoot()/獲取已經(jīng)構(gòu)造好的huffman編碼樹的根節(jié)點(diǎn)for(從nodes數(shù)組第一到最后一個(gè)元素) 若第i個(gè)元素節(jié)點(diǎn)的父節(jié)點(diǎn)域值為-1；則index用i賦值；return index;/返回根節(jié)點(diǎn)public int selectMinNode()/選擇權(quán)值最小節(jié)點(diǎn)，保存其下標(biāo)，并統(tǒng)計(jì)剩余的沒(méi)有進(jìn)樹的節(jié)點(diǎn)數(shù)int index=-1;/index

28、存放權(quán)值最小節(jié)點(diǎn)的下標(biāo)值if(null!=nodes&&nodes.size()!=0)/如果數(shù)組非空，則選取權(quán)值最小的節(jié)點(diǎn)for(int i=0;i<nodes.size();i+)/從nodes數(shù)組1到最后一個(gè)節(jié)點(diǎn)循環(huán)查找權(quán)值最小的節(jié)點(diǎn)if(nodes.get(i).getParent()=-1)count+;/節(jié)點(diǎn)的父節(jié)點(diǎn)域?yàn)?1，說(shuō)明該節(jié)點(diǎn)未被選取if(node=null)node=nodes.get(i);index=i;else if(node.getWeight()>nodes.get(i).getWeight()用node記錄權(quán)值最小的節(jié)點(diǎn)，inde

29、x記錄其下標(biāo)return new intindex,count;/返回權(quán)值最小節(jié)點(diǎn)的下標(biāo)和未進(jìn)樹的節(jié)點(diǎn)數(shù)public void JianShu()/建立哈夫曼編碼樹int min=selectMinNode();/選取權(quán)值最小的節(jié)點(diǎn)while(min1>1|sum%2!=0) /每?jī)蓚€(gè)節(jié)點(diǎn)生成一個(gè)新的節(jié)點(diǎn)if(sum%2=0)取到第一個(gè)節(jié)點(diǎn)時(shí)，新建一個(gè)父節(jié)點(diǎn)else 當(dāng)取到第二個(gè)節(jié)點(diǎn)時(shí)，將其權(quán)值加到新建的父節(jié)點(diǎn)中newNode.setWeight(newNode.getWeight()+node.getWeight();min=selectMinNode();/繼續(xù)選取下一個(gè)權(quán)值最小的節(jié)

30、點(diǎn)public String getCode(int i)/獲得節(jié)點(diǎn)的單個(gè)編碼Node pNode=nodes.get(nodes.get(i).getParent();判斷，若此節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子則返回0否則為1；public void bianMa1()/從葉子到根對(duì)字符集中各個(gè)字符進(jìn)行編碼for(int i=0;i<nodes.size();i+)if(nodes.get(i).isLeaf()/若節(jié)點(diǎn)i為葉子，則獲取其編碼while(parent!=-1)/該節(jié)點(diǎn)i不是根節(jié)點(diǎn)，則循環(huán)記錄0/1碼串，從葉子到根編碼nodes.get(i).setCode(code);/存放節(jié)點(diǎn)

31、i的編碼public String bianMa2(String names)/編碼方法對(duì)輸入的詞句字符進(jìn)行編碼for(int i=0;i<names.length();i+)/從詞句中第一個(gè)字符開始編碼for(int j=0;j<nodes.size();j+)查找編碼表中是否存在該字符/若在編碼表中找到該字符icodes+=nodes.get(j).getCode();/則在codes中記錄其編碼break;/跳出內(nèi)循環(huán)，繼續(xù)查找下一個(gè)字符的編碼else if(j=nodes.size()-1) /若找不到該字符，則返回操作提示語(yǔ)return names.charAt(i)+&

32、quot;沒(méi)在編碼表中！請(qǐng)重新操作！"return codes;/返回詞句編碼結(jié)果public String jieMa(String codes)/譯碼方法for(int i=0,j=root;i<codes.length();i+)/從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)進(jìn)行譯碼if(codes.charAt(i)='0')/若編碼為0，二叉樹向左查找j=nodes.get(j).getLeft();else if(codes.charAt(i)='1')/編碼為1，二叉樹向右查找else/編碼含有非0，1字符，則輸出提示語(yǔ)return "編碼有誤，請(qǐng)

33、檢查后重新輸入！"若節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則譯碼成功；j=root; /j用根節(jié)點(diǎn)位置賦值，繼續(xù)下一個(gè)譯碼return names;/返回譯碼結(jié)果（3）主類JieMian類的設(shè)計(jì)及功能描述：屬性設(shè)計(jì)：JieMian類主要作用是對(duì)界面的設(shè)計(jì)，以及設(shè)計(jì)監(jiān)聽者對(duì)各種事件進(jìn)行響應(yīng)和處理。主要界面組件有字符標(biāo)簽，權(quán)值標(biāo)簽，字符輸入文本框，權(quán)值輸入文本框，結(jié)果輸出文本框，建樹并輸出編碼表按鈕，編碼按鈕，譯碼按鈕，清空按鈕。方法設(shè)計(jì)：在public void init()方法中，對(duì)建樹并輸出編碼表按鈕，編碼按鈕，譯碼按鈕和清空按鈕分別設(shè)置ActionListener()監(jiān)聽者，監(jiān)聽按鈕點(diǎn)擊事件，并分別對(duì)

34、不同情況作出響應(yīng)的異常處理。init方法偽碼如下：public void init() button = new Button("u5EFAu6811u5E76u8F93u51FAu7F16u7801u8868");button.addActionListener(new ActionListener()/設(shè)置建樹按鈕監(jiān)聽者public void actionPerformed(ActionEvent e) /點(diǎn)擊按鈕事件響應(yīng)trytextResult.setText("");/清空結(jié)果文本框獲取節(jié)點(diǎn)字符，及其權(quán)值；若字符文本域?yàn)榭眨瑒t提示請(qǐng)輸入字符，返

35、回空值；若權(quán)值文本域?yàn)榭眨瑒t提示請(qǐng)輸入對(duì)應(yīng)權(quán)值，返回空；for(int i=0;i<strNames.length();i+)/檢查輸入字符集是否有重復(fù)for(int j=i+1;j<strNames.length();j+)若有重復(fù)字符，則輸出提示語(yǔ)textResult.setText("字符不能重復(fù)，（忽略大小寫）");return;如果字符和權(quán)值不完全對(duì)應(yīng)，提示重新輸入textResult.setText("字符和權(quán)值不能完全對(duì)應(yīng)！請(qǐng)檢查后重新輸入！");return;int weightsOfNum=new intweights.le

36、ngth;/定義整型數(shù)組weightsOfNum，存放權(quán)值；for(int i=0;i<weights.length;i+)/將權(quán)值字符串轉(zhuǎn)化為整型權(quán)值存放于weightsOfNum中weightsOfNumi=Integer.parseInt(weightsi);suanFa=new SuanFa(nodes);/新建SuanFa類對(duì)象suanFasuanFa.JianShu();/調(diào)用suanFa對(duì)象的 JianShu方法，建立huffman編碼樹suanFa.bianMa1();/調(diào)用biamMa1方法，對(duì)字符集各字符編碼for(int i=0;i<suanFa.getNod

37、es().size();i+)if(suanFa.getNodes().get(i).isLeaf()設(shè)置字符集及其對(duì)應(yīng)的編碼，存放于字符串biao中輸出字符集及其對(duì)應(yīng)的編碼于結(jié)果文本域中；label.setText("詞句:");/哈夫曼樹建立成功后，更改標(biāo)簽label_1.setText("編碼：");button_2.setEnabled(true);/編碼按鈕設(shè)為可用狀態(tài)button_3.setEnabled(true);/譯碼按鈕設(shè)為可用狀態(tài)button.setEnabled(false);/建樹按鈕設(shè)為不可用狀態(tài)catch(Exception

38、 ee)/捕捉編碼樹建立過(guò)程中所有非法數(shù)據(jù)輸入異常textResult.setText("處理數(shù)據(jù)發(fā)生異常，請(qǐng)檢查數(shù)據(jù)輸入是否合法！"););button_2.addActionListener(new ActionListener() /設(shè)置編碼按鈕的監(jiān)聽者public void actionPerformed(ActionEvent e) 若輸入詞句為空，則提示輸入詞句；String result=suanFa.bianMa2(ciJu);/調(diào)用對(duì)象的bianMa2方法對(duì)詞句進(jìn)行編碼并寫入結(jié)果文本域中);button_3.addActionListener(new Ac

39、tionListener() /設(shè)置譯碼按鈕監(jiān)聽者public void actionPerformed(ActionEvent e) 若輸入編碼為空，則提示輸入編碼；textResult.setText(suanFa.jieMa(codes););button_4.addActionListener(new ActionListener() /設(shè)置清空按鈕監(jiān)聽者public void actionPerformed(ActionEvent e) 所有標(biāo)簽及文本域重置空值；建樹按鈕設(shè)為可用，編碼按鈕和譯碼按鈕設(shè)為不可用label.setText("字符:");/更改標(biāo)簽初始

40、值為字符label_1.setText("權(quán)值：");/更改標(biāo)簽1初始值為權(quán)值suanFa對(duì)象重置空值；);textArea.setForeground(Color.RED);/提示語(yǔ)文本框字體紅色textArea.setBackground(Color.WHITE);/背景顏色設(shè)為白色textArea.setText("輸入時(shí)的注意事項(xiàng)文字");textArea.setBounds(496, 31, 120, 343);add(textArea);四 設(shè)計(jì)和調(diào)試分析在實(shí)驗(yàn)調(diào)試過(guò)程中，碰到的問(wèn)題很多：一是語(yǔ)法相關(guān)的問(wèn)題，由于是上學(xué)期學(xué)的java面向?qū)ο蟪?/p>

41、序設(shè)計(jì)，很多語(yǔ)法規(guī)則記憶不是很深，不過(guò)通過(guò)查閱各種書籍文獻(xiàn)以及編譯器的編譯很容易就解決了。二是算法方面的問(wèn)題，寫selectMinNode()方法的時(shí)候，首先想到要用排序算法，考慮用冒泡排序的時(shí)候發(fā)現(xiàn)由于要交換結(jié)點(diǎn)在數(shù)組中的位置，而nodes結(jié)點(diǎn)數(shù)組為全局屬性，在很多其他方法中需要使用，這樣的話會(huì)破壞數(shù)據(jù)結(jié)構(gòu) 。最后考慮直接選出權(quán)值最小的元素，而要找出權(quán)值次小的元素，就要在第一次循環(huán)找出最小的元素時(shí)將其排除，因此想到通過(guò)判斷節(jié)點(diǎn)是否存在父節(jié)點(diǎn)，來(lái)判斷其是否已被選取，然后在建樹方法中通過(guò)while循環(huán)調(diào)用selectMinNode()方法，選出第一個(gè)權(quán)值最小節(jié)點(diǎn)時(shí)，生成一個(gè)父節(jié)點(diǎn)，選出權(quán)值次小節(jié)

42、點(diǎn)時(shí)，將已生成的父節(jié)點(diǎn)位置下標(biāo)賦值給其父節(jié)點(diǎn)域?yàn)椋@樣，每?jī)蓚€(gè)節(jié)點(diǎn)生成一個(gè)父節(jié)點(diǎn)，順利完成了哈夫曼編碼樹的建立。三是數(shù)組的內(nèi)存分配和越界的問(wèn)題。一開始把節(jié)點(diǎn)數(shù)組nodes設(shè)置為最大長(zhǎng)度為Max的定長(zhǎng)數(shù)組，后來(lái)發(fā)現(xiàn)在建樹過(guò)程中，nodes數(shù)組長(zhǎng)度需要隨著huffman樹的建立不斷增加父節(jié)點(diǎn)，調(diào)試過(guò)程中發(fā)生數(shù)組越界，為此糾結(jié)了很久。后來(lái)終于學(xué)會(huì)了利用List動(dòng)態(tài)數(shù)組，定義一個(gè)Node類類型的動(dòng)態(tài)數(shù)組nodes，在建立huffman編碼樹的過(guò)程中動(dòng)態(tài)建立節(jié)點(diǎn)，在nodes數(shù)組中成功建立了huffman編碼樹。此后，在編碼方法和譯碼方法中，通過(guò)huffman編碼樹，很容易完成了從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的編碼

43、過(guò)程和從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的譯碼過(guò)程。最后， JieMian類中，設(shè)置了用戶輸入提示語(yǔ)，并在用戶非法輸入時(shí)，作出響應(yīng)的異常處理，并顯示操作提示語(yǔ)。在原有程序基礎(chǔ)上，將錄入的字符集中的字符全部轉(zhuǎn)換為大寫字母，允許用戶在輸入詞句進(jìn)行編碼時(shí)，將大小寫字母混合輸入，但大小寫字母做同樣處理。五 用戶手冊(cè)1.本程序的運(yùn)行環(huán)境為Microsoft Windows7操作系統(tǒng)，運(yùn)行123.html文件即可;2.進(jìn)入演示程序以后，首先顯示界面如下：建立huffman樹之前，編碼，譯碼按鈕不可用。圖5.13.根據(jù)注意文本提示，用戶輸入字符集中的字符，和字符對(duì)應(yīng)的權(quán)值，點(diǎn)擊建樹并輸出編碼表按鈕，則程序建立huffman

44、樹，并在結(jié)果中輸出字符集中各個(gè)字符對(duì)應(yīng)的編碼。輸入字符時(shí)，連續(xù)輸入不需分隔，輸入權(quán)值必須為整數(shù)并以逗號(hào)分隔，權(quán)值數(shù)目與字符數(shù)一致。操作完成后程序先結(jié)果如下：此時(shí)建樹并輸出編碼表按鈕不可用，編碼和譯碼按鈕可用。圖5.24.在詞句文本域中輸入要編進(jìn)行碼的電文詞句點(diǎn)擊編碼按鈕，則在結(jié)果中輸出詞句編碼。詞句中不能包含編碼字符之外的字符，否則提示重新輸入。圖5.35.在編碼文本域中輸入0/1編碼，點(diǎn)擊譯碼按鈕，則在結(jié)果中輸出編碼串的譯碼結(jié)果。圖5.46.用戶點(diǎn)擊清空按鈕，則清空文本域，重新建立huffman樹進(jìn)行編碼。8.如果用戶未按照注意提示語(yǔ)中的規(guī)則輸入信息則會(huì)輸出操作提示語(yǔ)。六 測(cè)試結(jié)果1. 利用

45、下表的8個(gè)字符及頻率建立哈夫曼編碼樹，操作結(jié)果如下：字母CDEFKLUZ頻率324212024742372圖6.1輸入詞句“ddefKUuc”，編碼結(jié)果如下：圖6.2輸入編碼字符之外的字符時(shí)，提示重新輸入：圖6.3輸入編碼“”進(jìn)行譯碼時(shí)，結(jié)果如下：圖6.4輸入非0/1碼串時(shí)，提示信息如下：圖6.52. 用下表中給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)報(bào)文:“I love you Loo” 的編碼和譯碼字母頻率字母頻率A77O67B17P20C32Q5D42R59E120S67F24T85G17U37H50V12I76W22J4X4K7Y22L42Z2M24(空格)186N67輸入字

46、符集中27個(gè)字符，建立哈夫曼編碼樹，測(cè)試結(jié)果如下：編碼結(jié)果較長(zhǎng)，拖動(dòng)水平滾動(dòng)條即可查看。編碼表結(jié)果為：A->1001 B->000011 C->01110 D->10101 E->001 F->110101 G->101000 H->11011 I->1000 J->00001001 K->0000101 L->11000 M->00000 N->0100 O->0101 P->101001 Q->11001001 R->0001 S->0110 T->1011 U->

47、01111 V->1100101 W->110011 X->11001000 Y->110100 Z->00001000 ->111圖6.6輸入“I love you Loo”時(shí)，編碼結(jié)果如下：圖6.7輸入0/1碼串“”時(shí)譯碼結(jié)果如下：圖6.8參考文獻(xiàn)1 印旻Java與面向?qū)ο蟪绦蛟O(shè)計(jì)教程北京：高等教育出版社，1999.112 東方人華Java 2 范例入門與提高北京：清華大學(xué)出版社，2003.83 楊庚、王汝傳.面向?qū)ο蟪绦蛟O(shè)計(jì)與C+語(yǔ)言.北京：人民郵電出版社，2002.74 希爾德（美）.Java編程起步.北京：人民郵電出版社，2001.55 羅省賢.J

48、ava程序設(shè)計(jì)教程（第五版）.北京：電子工業(yè)出版社，2007.16 張琛恩.面向?qū)ο蟮脑O(shè)計(jì)與模式.北京：電子工業(yè)出版社，2004.1附錄源程序文件清單：/JieMian.java文件代碼import java.applet.Applet;import java.awt.Label;import java.awt.TextArea;import java.awt.Button;import java.awt.event.ActionListener;import java.awt.event.ActionEvent;import java.util.ArrayList;import java.u

49、til.List;import java.awt.Color;public class JieMian extends Appletpublic JieMian() private static final long serialVersionUID = 1L;private TextArea textName;private TextArea textWeight;private TextArea textResult;private SuanFa suanFa;private Label label;/字符、詞句標(biāo)簽private Label label_1;/權(quán)值、編碼標(biāo)簽private

50、 Button button;/建樹按鈕private Button button_4;/清空按鈕private Button button_2;/編碼按鈕private Button button_3;/譯碼按鈕private Label label_3;/標(biāo)題標(biāo)簽private TextArea textArea;public void init() setLayout(null);setSize(635,420);label = new Label("u5B57u7B26uFF1A");label.setBounds(27, 31, 55, 23);add(label

51、);/添加標(biāo)簽label_1 = new Label("u6743u503CuFF1A");label_1.setBounds(27, 139, 55, 23);add(label_1);textName= new TextArea();textName.setBounds(88, 31, 402, 95);add(textName);textWeight = new TextArea();textWeight.setBounds(88, 139, 402, 95);add(textWeight);button = new Button("u5EFAu6811u5E76u8F93u51FAu7F16u7801u8868");button.addActionListener(new ActionListener()/設(shè)置建樹按鈕監(jiān)聽者public void actionPerformed(ActionEvent e)