哈夫曼編碼的java實(shí)現(xiàn)課程設(shè)計(jì)

1、<p>　　哈夫曼編碼的JAVA實(shí)現(xiàn)課程設(shè)計(jì)</p><p><b>　　目 錄</b></p><p><b>　　摘 要2</b></p><p><b>　　一、問題綜述2</b></p><p>　　二、求解方法介紹3</p><p&

2、gt;　　三、實(shí)驗(yàn)步驟及結(jié)果分析4</p><p>　　四、程序設(shè)計(jì)源代碼5</p><p><b>　　參考文獻(xiàn)8</b></p><p><b>　　摘要</b></p><p>　　利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本，試用java語言設(shè)計(jì)一個(gè)哈夫

3、曼編碼系統(tǒng)。通過本課程設(shè)計(jì)，應(yīng)使學(xué)生掌握哈夫曼編碼的特點(diǎn)、儲(chǔ)存方法和基本原理，培養(yǎng)學(xué)生利用java語言正確編寫程序及調(diào)試程序的能力，運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問題的能力。</p><p>　　關(guān)鍵字：哈夫曼編碼 JAVA語言 類 方法</p><p><b>　　一、問題綜述</b></p><p>　　1 哈夫曼編碼的算法思想</p>

4、;<p>　　哈夫曼編碼也稱前綴編碼，它是根據(jù)每個(gè)字符出現(xiàn)的頻率而進(jìn)行編碼的，要求任一字符的編碼都不是其它任意字符編碼的前綴且字符編碼的總長度為最短。它主要應(yīng)用于通信及數(shù)據(jù)的傳送以及對(duì)信息的壓縮處理等方面。哈夫曼編碼的基礎(chǔ)是依據(jù)字符出現(xiàn)的頻率值而構(gòu)造一棵哈夫曼樹，從而實(shí)現(xiàn)最短的編碼表示最常用的數(shù)據(jù)塊或出現(xiàn)頻率最高的數(shù)據(jù)，具體的方法是：</p><p>　　1.1 建立哈夫曼樹</p>

5、<p>　　把N 個(gè)字符出現(xiàn)的頻率值作為字符的權(quán)值,然后依據(jù)下列步驟建立哈夫曼樹。</p><p>　　1.1.1 由N 個(gè)權(quán)值分別作N 棵樹的根結(jié)點(diǎn)而形成一個(gè)森林。</p><p>　　1.1.2 從中選擇兩棵根值最小的樹T1 和T2 組成一棵以結(jié)點(diǎn)T 為根結(jié)點(diǎn)的增長樹，根結(jié)點(diǎn)T = T1 + T2 ,即新樹的根值為原來兩棵樹的根值之和，而T1 和T2 分別為增長樹的左右子樹。

6、</p><p>　　1.1.3 把這棵新樹T 加入到森林中，把原來的兩棵樹T1 和T2 從森林中刪除。</p><p>　　1.1.4 重復(fù)1.1.2～1.1.3 步，直到合并成一棵樹為止。</p><p>　　1.2 生成各字符的哈夫曼編碼</p><p>　　在上面形成的哈夫曼樹中，各個(gè)字符的權(quán)值結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，從葉子結(jié)點(diǎn)開始向根搜索

7、，如果是雙親的左分支，則用“0”標(biāo)記，右分支用“1”標(biāo)記，從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)所經(jīng)過的分支編碼“0”、“1”的組合序列就是各字符的哈夫曼編碼。</p><p>　　2 構(gòu)造哈夫曼樹的算法</p><p>　　1）對(duì)給定的n個(gè)權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉樹Ti中只有一個(gè)權(quán)值為Wi

8、的根結(jié)點(diǎn)，它的左右子樹均為空。</p><p>　　2）在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。</p><p>　　3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。</p><p>　　4）重復(fù)2）和3），直到集合F中只有一棵二叉樹為止。</p>&l

9、t;p>　　例如，對(duì)于4個(gè)權(quán)值為1、3、5、7的節(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，其構(gòu)造過程如下圖所示：</p><p>　　圖1 構(gòu)造哈夫曼樹的過程示例</p><p><b>　　二、求解方法介紹</b></p><p>　　以往的哈夫曼編碼程序?qū)崿F(xiàn)都是利用PASCAL 或C 語言描述的，而這兩門語言都有相應(yīng)的指針類型來解決，實(shí)現(xiàn)起來較為容易，但

10、是，JAVA語言是面向?qū)ο蟮木幊陶Z言，沒有提供指針類型，所以在實(shí)現(xiàn)上應(yīng)該結(jié)合JAVA 的應(yīng)用環(huán)境，采用靜態(tài)的方法解決。同時(shí)，JAVA 語言是具有平臺(tái)無關(guān)性的網(wǎng)絡(luò)編程語言，用JAVA 語言實(shí)現(xiàn)哈夫曼編碼不論在教學(xué)中或是在實(shí)際應(yīng)用中都有一定的意義。</p><p>　　本程序是用哈夫曼樹來實(shí)現(xiàn)哈夫曼編碼的功能，根據(jù)輸入的報(bào)文進(jìn)行分析，建立哈夫曼樹。統(tǒng)計(jì)輸入字符串的長度，并對(duì)每個(gè)字符的頻度進(jìn)行計(jì)算。對(duì)每個(gè)字符及相應(yīng)的頻

11、度作為葉結(jié)點(diǎn)建立哈夫曼樹。哈夫曼樹的建立過程采用把結(jié)點(diǎn)看作樹每次選最小的兩個(gè)建立樹，并把他們的頻度相加，再繼續(xù)選取最小的兩個(gè)數(shù)建立，直到所有的結(jié)點(diǎn)建立完，才形成完整的哈夫曼樹。接下來是對(duì)沒個(gè)結(jié)點(diǎn)進(jìn)行編碼，從第一個(gè)結(jié)點(diǎn)開始看它的雙親，若它雙親做左孩子則記0，若是右孩子則記1，依次往上推，直到哈夫曼的根結(jié)點(diǎn)為止。記錄編碼打印出來。</p><p>　　為了體現(xiàn)程序中各個(gè)功能的獨(dú)立性，結(jié)合JAVA 語言的編程要求，對(duì)程

12、序中所用到的類和方法進(jìn)行說明：</p><p>　　1 公共類Tree：組成哈夫曼樹的最小單元。其成員變量有：</p><p>　　lchild：最小單元的左孩子。</p><p>　　rchild：最小單元的右孩子。</p><p>　　parents：最小單元的雙親。</p><p>　　2 公共類Huffman：

13、描述哈夫曼編碼的整個(gè)過程,其成員變量有：</p><p>　　2.1 numsMo：儲(chǔ)存要進(jìn)行編碼的一組數(shù)。</p><p>　　2.2 nums：臨時(shí)儲(chǔ)存要進(jìn)行編碼的這組數(shù)，會(huì)隨著后面的調(diào)用而變化。</p><p>　　2.3 trees：儲(chǔ)存哈夫曼樹，由若干最小單元構(gòu)成。</p><p>　　2.4 temp：中間變量，是字符串類型。&l

14、t;/p><p><b>　　3 核心方法及流程</b></p><p>　　3.1　main 方法：用于程序的執(zhí)行入口。其中定義了一個(gè)Huff 類實(shí)體，調(diào)用方法start() 完成數(shù)組初始排序，實(shí)現(xiàn)哈夫曼編碼等一系列的操作。</p><p>　　3.2 addNum 方法：用于方法初始化給定的要進(jìn)行編碼的數(shù)組，數(shù)組通過控制臺(tái)鍵盤錄入。</p

15、><p>　　3.3 minTo 方法：在一組數(shù)中選擇最小的兩個(gè)，按遞增順序返回。</p><p>　　3.4 compareNum 方法：是公共類Huffman的核心算法之一，該方法是將一組樹形成哈夫曼樹，左孩子為較小值。</p><p>　　3.5 print 方法：是公共類Huffman的核心算法之一，該方法利用遞歸打印出編碼。其流程圖如下：</p>

16、<p>　　三、實(shí)驗(yàn)步驟及結(jié)果分析</p><p><b>　　測(cè)試數(shù)據(jù)：</b></p><p>　　0.01 0.03 0.07 0.13 0.19 0.26 0.31</p><p><b>　　程序運(yùn)行：</b></p><p>　　請(qǐng)輸入一組數(shù)，中間用空格分隔：</p&g

17、t;<p>　　0.03 0.07 0.13 0.19 0.26 0.31</p><p><b>　　輸出結(jié)果為：</b></p><p>　　0.01 : 01000 碼長：5</p><p>　　0.03 : 01001 碼長：5</p><p>　　0.07 : 0101 碼長：4</p>

18、;<p>　　0.13 : 011 碼長：3</p><p>　　0.19 : 00 碼長：2</p><p>　　0.26 : 10 碼長：2</p><p>　　0.31 : 11 碼長：2</p><p><b>　　心得體會(huì)：</b></p><p>　　在本次的課程設(shè)計(jì)中，

19、就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難。我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了：在遞歸調(diào)用方法時(shí)最好不要有返回值，否則會(huì)使程序變得邏輯混亂，復(fù)雜難懂；當(dāng)從葉結(jié)點(diǎn)向上編碼時(shí)，根據(jù)本程序的特點(diǎn)會(huì)有可能重復(fù)的tree，所以要分成同tree和不同tree進(jìn)行不同的邏輯編程。</p><p>　　通過本次的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒懂的知識(shí)，并對(duì)

20、求哈夫曼樹及哈夫曼編碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)了一種算法。當(dāng)求解一個(gè)算法時(shí)，不是拿到問題就不加思索地做，而是首先要先對(duì)它有個(gè)大概的了解，接著再詳細(xì)地分析每一不怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會(huì)順利地做出來。</p><p><b>　　四、程序設(shè)計(jì)源代碼</b></p><p>　

21、　import java.util.ArrayList;</p><p>　　import java.util.List;</p><p>　　import java.util.Scanner;</p><p>　　public class Huffman {</p><p>　　private List<Double> nums

22、;</p><p>　　private List<Double> numsMo;</p><p>　　private List<Tree> trees;</p><p>　　private String temp;</p><p>　　public Huffman() {</p><p>　　n

23、ums = new ArrayList<Double>();</p><p>　　numsMo = new ArrayList<Double>();</p><p>　　trees = new ArrayList<Tree>();</p><p><b>　　temp="";</b><

24、;/p><p><b>　　}</b></p><p>　　public void addNums() {// 給定一組數(shù)</p><p>　　System.out.println("請(qǐng)輸入一組數(shù)，中間用空格分隔：");</p><p>　　Scanner sca = new Scanner(System

25、.in);</p><p>　　String str = sca.nextLine();</p><p>　　String[] strs = str.split(" ");</p><p>　　for (int i = 0; i < strs.length; i++) {</p><p>　　nums.add(Dou

26、ble.parseDouble(strs[i]));</p><p>　　numsMo.add(Double.parseDouble(strs[i]));</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public void compareNum

27、(List<Double> nums,List<Tree> trees) {// 遞歸算法</p><p>　　double[] min = new double[2];</p><p>　　if(nums.size()>1){</p><p>　　min = minTwo(nums);</p><p>　　Tr

28、ee t = new Tree(min[0],min[1],min[0]+min[1]);</p><p>　　nums.remove(Double.valueOf(min[0]));</p><p>　　nums.remove(Double.valueOf(min[1]));</p><p>　　nums.add(min[0]+min[1]);</p>

29、<p>　　trees.add(t);</p><p>　　compareNum(nums,trees);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public void print(double num) {// 遞歸打印編

30、碼</p><p>　　for(Tree t : trees){</p><p>　　if(num == t.getRchild()){</p><p>　　temp = 1+temp;</p><p>　　print(t.getParents());</p><p><b>　　break;</b&g

31、t;</p><p>　　}else if(num == t.getLchild()){</p><p>　　temp = 0+temp;</p><p>　　print(t.getParents());</p><p><b>　　break;</b></p><p><b>　　}&

32、lt;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public void write(double d){</p><p>　　temp = "";</p><p>　　System.o

33、ut.print(d+" : ");</p><p><b>　　print(d);</b></p><p>　　System.out.print(temp);</p><p>　　System.out.println(" 碼長："+temp.length());</p><p>

34、<b>　　}</b></p><p>　　public double[] minTwo(List<Double> nums) {// 在一組數(shù)中選則最小的兩個(gè)，按遞增排序返回</p><p>　　Double temp = 0.0;</p><p>　　for (int j = 0; j < 2; j++) {</p&

35、gt;<p>　　for (int i = 1; i < nums.size(); i++) {</p><p>　　if (nums.get(i - 1) < nums.get(i)) {</p><p>　　temp = nums.get(i);</p><p>　　nums.set(i, nums.get(i - 1));</p

36、><p>　　nums.set(i - 1, temp);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　double[] n = {nums.get(nums.s

37、ize()-1),nums.get(nums.size()-2)};</p><p><b>　　return n;</b></p><p><b>　　}</b></p><p>　　public void start(){</p><p>　　addNums();</p><

38、p>　　compareNum(nums,trees);</p><p>　　while(numsMo.size()>1){</p><p>　　double[] mins = minTwo(numsMo);</p><p>　　if(mins[0]!=mins[1]){</p><p>　　numsMo.remove(Double

39、.valueOf(mins[0]));</p><p>　　write(mins[0]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(!numsMo.isEmpty()){</p><p>　　write(num

40、sMo.get(0));</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public static void main(String[] args){</p><p>　　new Huffman().start();</p><

41、;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　參考文獻(xiàn)</b></p><p>　　1(美)Stuart Reges，(美)Marty Stepp著 陳志等譯，java程序設(shè)計(jì)教程，機(jī)械工業(yè)出版社,2008</p><p&g