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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、<p>　　三、實驗步驟及結(jié)果分析</p><p><b>　　測試數(shù)據(jù)：</b></p><p>　　0.01 0.03 0.07 0.13 0.19 0.26 0.31</p><p><b>　　程序運行：</b></p><p>　　請輸入一組數(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>　　心得體會：</b></p><p>　　在本次的課程設(shè)計中，

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

20、求哈夫曼樹及哈夫曼編碼的算法有了更加深刻的了解，更鞏固了課堂中學習有關(guān)于哈夫曼編碼的知識，真正學會了一種算法。當求解一個算法時，不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一不怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。</p><p><b>　　四、程序設(shè)計源代碼</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("請輸入一組數(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ù)中選則最小的兩個，按遞增排序返回</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>　　參考文獻</b></p><p>　　1(美)Stuart Reges，(美)Marty Stepp著 陳志等譯，java程序設(shè)計教程，機械工業(yè)出版社,2008</p><p&g