1、哈夫曼編碼的JAVA實現課程設計目 錄摘要2一、問題綜述2二、求解方法介紹3三、實驗步驟及結果分析4四、程序設計源代碼5參考文獻8摘要利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本，試用java語言設計一個哈夫曼編碼系統。通過本課程設計，應使學生掌握哈夫曼編碼的特點、儲存方法和基本原理，培養學生利用java語言正確編寫程序及調試程序的能力，運用數據結構知識解決實際問題的能力。關鍵字：哈夫曼編碼 JAVA語言 類 方法一、問題綜述1 哈夫曼編碼的算法思想哈夫曼編碼也稱前綴編碼，它是根據每個字符出現的頻率而進行編碼的，要求任一字符的編碼都不是其它任意字符編碼的前綴且字

2、符編碼的總長度為最短。它主要應用于通信及數據的傳送以及對信息的壓縮處理等方面。哈夫曼編碼的基礎是依據字符出現的頻率值而構造一棵哈夫曼樹，從而實現最短的編碼表示最常用的數據塊或出現頻率最高的數據，具體的方法是：1.1建立哈夫曼樹把N 個字符出現的頻率值作為字符的權值,然后依據下列步驟建立哈夫曼樹。1.1.1由N 個權值分別作N 棵樹的根結點而形成一個森林。1.1.2 從中選擇兩棵根值最小的樹T1 和T2 組成一棵以結點T 為根結點的增長樹，根結點T = T1 + T2 ,即新樹的根值為原來兩棵樹的根值之和，而T1 和T2 分別為增長樹的左右子樹。1.1.3 把這棵新樹T 加入到森林中，把原來的兩

3、棵樹T1 和T2 從森林中刪除。1.1.4 重復1.1.21.1.3 步，直到合并成一棵樹為止。1.2 生成各字符的哈夫曼編碼在上面形成的哈夫曼樹中，各個字符的權值結點都是葉子結點，從葉子結點開始向根搜索，如果是雙親的左分支，則用“0”標記，右分支用“1”標記，從葉子結點到根結點所經過的分支編碼“0”、“1”的組合序列就是各字符的哈夫曼編碼。2 構造哈夫曼樹的算法1）對給定的n個權值W1,W2,W3,.,Wi,.,Wn構成n棵二叉樹的初始集合F=T1,T2,T3,.,Ti,., Tn，其中每棵二叉樹Ti中只有一個權值為Wi的根結點，它的左右子樹均為空。2）在F中選取兩棵根結點權值最小的樹作為新

4、構造的二叉樹的左右子樹，新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。3）從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。4）重復2）和3），直到集合F中只有一棵二叉樹為止。例如，對于4個權值為1、3、5、7的節點構造一棵哈夫曼樹，其構造過程如下圖所示：圖1 構造哈夫曼樹的過程示例二、求解方法介紹以往的哈夫曼編碼程序實現都是利用PASCAL 或C 語言描述的，而這兩門語言都有相應的指針類型來解決，實現起來較為容易，但是，JAVA語言是面向對象的編程語言，沒有提供指針類型，所以在實現上應該結合JAVA 的應用環境，采用靜態的方法解決。同時，JAVA 語言是具有平臺無關

5、性的網絡編程語言，用JAVA 語言實現哈夫曼編碼不論在教學中或是在實際應用中都有一定的意義。本程序是用哈夫曼樹來實現哈夫曼編碼的功能，根據輸入的報文進行分析，建立哈夫曼樹。統計輸入字符串的長度，并對每個字符的頻度進行計算。對每個字符及相應的頻度作為葉結點建立哈夫曼樹。哈夫曼樹的建立過程采用把結點看作樹每次選最小的兩個建立樹，并把他們的頻度相加，再繼續選取最小的兩個數建立，直到所有的結點建立完，才形成完整的哈夫曼樹。接下來是對沒個結點進行編碼，從第一個結點開始看它的雙親，若它雙親做左孩子則記0，若是右孩子則記1，依次往上推，直到哈夫曼的根結點為止。記錄編碼打印出來。為了體現程序中各個功能的獨立性

6、，結合JAVA 語言的編程要求，對程序中所用到的類和方法進行說明： 1 公共類Tree：組成哈夫曼樹的最小單元。其成員變量有：1.1 lchild：最小單元的左孩子。1.2 rchild：最小單元的右孩子。1.3 parents：最小單元的雙親。2 公共類Huffman：描述哈夫曼編碼的整個過程,其成員變量有： 2.1 numsMo：儲存要進行編碼的一組數。 2.2 nums：臨時儲存要進行編碼的這組數，會隨著后面的調用而變化。 2.3 trees：儲存哈夫曼樹，由若干最小單元構成。 2.4 temp：中間變量，是字符串類型。3 核心方法及流程 3.1main 方法：用于程序的執行入口。其中定

7、義了一個Huff 類實體，調用方法start()完成數組初始排序，實現哈夫曼編碼等一系列的操作。3.2 addNum 方法：用于方法初始化給定的要進行編碼的數組，數組通過控制臺鍵盤錄入。3.3 minTo 方法：在一組數中選擇最小的兩個，按遞增順序返回。3.4 compareNum 方法：是公共類Huffman的核心算法之一，該方法是將一組樹形成哈夫曼樹，左孩子為較小值。3.5 print 方法：是公共類Huffman的核心算法之一，該方法利用遞歸打印出編碼。其流程圖如下：三、實驗步驟及結果分析測試數據：0.01 0.03 0.07 0.13 0.19 0.26 0.31程序運行：請輸入一組數

8、，中間用空格分隔：0.01 0.03 0.07 0.13 0.19 0.26 0.31輸出結果為：0.01 : 01000 碼長：50.03 : 01001 碼長：50.07 : 0101 碼長：40.13 : 011 碼長：30.19 : 00 碼長：20.26 : 10 碼長：20.31 : 11 碼長：2心得體會： 在本次的課程設計中，就在編寫好源代碼后的調試中出現了不少的錯誤，遇到了很多麻煩及困難。我的調試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執行的程序中，通過分析，我學到了：在遞歸調用方法時最好不要有返回值，否則會使程序變得邏輯混亂，復雜難懂；當從葉結點向上編碼時，根據本程序

9、的特點會有可能重復的tree，所以要分成同tree和不同tree進行不同的邏輯編程。 通過本次的課程設計，我學習了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼的算法有了更加深刻的了解，更鞏固了課堂中學習有關于哈夫曼編碼的知識，真正學會了一種算法。當求解一個算法時，不是拿到問題就不加思索地做，而是首先要先對它有個大概的了解，接著再詳細地分析每一不怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。四、程序設計源代碼import java.util.ArrayList;import java.util.List;import java.util.Scanner;

10、publicclass Huffman private List<Double> nums;private List<Double> numsMo;private List<Tree> trees;private String temp;public Huffman() nums = new ArrayList<Double>();numsMo = new ArrayList<Double>();trees = new ArrayList<Tree>();temp=""publicvoid addNum

11、s() / 給定一組數System.out.println("請輸入一組數，中間用空格分隔：");Scanner sca = new Scanner(System.in);String str = sca.nextLine();String strs = str.split(" ");for (int i = 0; i < strs.length; i+) nums.add(Double.parseDouble(strsi);numsMo.add(Double.parseDouble(strsi);publicvoid compareNum(Lis

12、t<Double> nums,List<Tree> trees) / 遞歸算法double min = newdouble2;if(nums.size()>1)min = minTwo(nums);Tree t = new Tree(min0,min1,min0+min1);nums.remove(Double.valueOf(min0);nums.remove(Double.valueOf(min1);nums.add(min0+min1);trees.add(t);compareNum(nums,trees);publicvoid print(double n

13、um) / 遞歸打印編碼for(Tree t : trees)if(num = t.getRchild()temp = 1+temp;print(t.getParents();break;elseif(num = t.getLchild()temp = 0+temp;print(t.getParents();break;publicvoid write(double d)temp = ""System.out.print(d+" : ");print(d);System.out.print(temp);System.out.println("

14、碼長："+temp.length();publicdouble minTwo(List<Double> nums) / 在一組數中選則最小的兩個，按遞增排序返回Double temp = 0.0;for (int j = 0; j < 2; j+) for (int i = 1; i < nums.size(); i+) if (nums.get(i - 1) < nums.get(i) temp = nums.get(i);nums.set(i, nums.get(i - 1);nums.set(i - 1, temp);double n = nums.get(nums.size()-1),nums.get(nums.size()-2);return n;publicvoid start()addNums();compareNum(nums,trees);while(numsMo.size()>1)double mins = minTwo(numsMo);if(mins0!=mins1)numsMo.remove(Double.valueOf(mins0);wri