1、 東北大學秦皇島分校計算機與通信工程學院計算機科學與技術 數據結構課設哈夫曼編譯碼器學 號：姓 名：提交日期：成 績： 一、 實驗名稱哈夫曼編/譯碼器的實現二、 實驗要求【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳來數據預先編碼，在接收端將傳來的數據進行譯碼(復原)。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/譯碼系統。【基本要求】一個完整的系統應具有以下功能：(1)I：初始化(Initialization)。從終端讀入字符集大小n ,

2、 以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。(2)E：編碼(Encoding)。利用已建好的哈夫曼樹(如不在內存，則從文件hfmTree中讀人)，對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。(3)D: 譯碼(Decoding)。利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進行譯碼，結果存入文件TextFile中。(4)P：打印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行 50 個代碼。同時將此字符形式的編碼文件寫入文件 CodePrin 中。(5)T：打印哈夫曼樹(Tree printing)

3、。將已在內存中的哈夫曼樹以直觀的方式(樹或凹入表形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。【測試數據】(1)利用教科書例 6-2 中的數據調試程序。(2)用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹 , 并實現以下報文的編碼和譯碼："THIS PROGRAM IS MY FAVORITE"。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161三、 需求分析Huffman編碼是一種可變長編碼方式，是由美國數學家David

4、Huffman創立的，是二叉樹的一種特殊轉化形式。編碼的原理是：將使用次數多的代碼轉換成長度較短的代碼，而使用次數少的可以使用較長的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計的(字符的統計數字*字符的編碼長度)為最小，也就是權值(字符的統計數字*字符的編碼長度)的和最小。3.1設計簡介本設計是通過對給定字符及其使用頻度構造哈夫曼樹再根據哈夫曼樹進行哈夫曼編碼，在此之前，首先要理解哈夫曼樹、哈夫曼算法、哈夫曼編譯碼的概念和原理。3.1.1哈夫曼樹從樹的根結點到樹的每個結點的路徑長度之和即為該樹的路徑長度。而在實際應用中，常將樹的結點賦予一個有某種含義的數值，這個數值

5、就稱為結點的權。從樹的根結點到該結點之間的路徑長度與結點權的乘積稱為該結點的帶權路徑長度，樹中所有葉結點的帶權路徑長度之和稱為樹的帶權路徑長度。通常記作：WPL = 式中，n表示樹中葉子結點的數目，wi表示葉結點ki的權，li表示根結點到葉結點Ki之間的路徑長度。在n個權值為w1,w2,wn的帶權葉結點構成的所有二叉樹中，其帶權路徑長度WPL最小的二叉樹即為哈夫曼樹或最優二叉樹。3.1.2哈夫曼算法給定n個帶權葉結點，如何構造一棵n個帶有給定權值的葉結點的二叉樹，使其帶權路徑長度最小？哈夫曼首先給出了構造最有二叉樹的方法，故稱其為哈夫曼算法，其基本的算法思想如下：將n個權值分別是w1,w2,w

6、n的結點按權值遞增排列。將每個權值作為一個二叉樹，構成n棵二叉樹的森林F=T1,T2,Tn，其中每棵二叉樹都只有一個權值為wi的根結點，其左右子樹均為空。在森林F中選兩棵根結點權值最小的二叉樹，作為左右子樹構造一棵新的二叉樹，并使得新二叉樹根結點的權值為其左右子樹上根結點權值之和。在森林F中，刪除這兩棵樹，同時將新得到的二叉樹代替這兩棵樹加入到森林F中去，因此，森林F中二叉樹的個數比以前少一棵。對新的森林F重復和，直到森林中只有一棵樹為止。這棵樹就是哈夫曼樹。3.1.3哈夫曼編碼用哈夫曼樹得到的二進制前綴編碼就是哈夫曼編碼。具體做法是：對于給定的字符集C=c1,c2,cn及字符出現的頻率W=w

7、1,w2,wn，以c1,c2,cn作為葉結點，以w1,w2,wn作為該結點上的權，利用哈夫曼算法，構造一棵帶權路徑長度最小的的哈夫曼樹。然后對哈夫曼樹中每個分支結點的左右分支分別用0和1進行編碼，這樣從樹的根結點到每個葉結點之間，沿途路徑上0和1組成的編碼序列就是葉結點所代表字符的二進制編碼。3.1.4哈夫曼譯碼哈夫曼譯碼過程與編碼過程相反，譯碼過程就是分解電文中字符串的過程，具體步驟如下：首先輸入要一點問的二進制編碼，然后從哈夫曼樹的根結點出發，對于電文的二進制編碼，按照二進制位串中的0和1確定是進入左分支還是右分支：若編碼為0，則進入結點的左孩子，否則進入結點的右孩子，一旦到達葉結點，就譯

8、出該葉子結點所代表字符。3.2設計方案3.2.1設計思路要編程實現該系統，需逐步實現：1. 哈夫曼樹的建立，即根據所給字符及對應頻度構造哈夫曼樹，哈夫曼樹構造函數包括對哈夫曼樹的初始化、賦值和建立；2. 哈夫曼編碼表的建立，即編寫程序實現對所給字符進行哈夫曼編碼，將每個字符的哈夫曼編碼存儲到一個位串數組中去；3. 打印輸出哈夫曼樹和哈夫曼編碼表，在終端上顯示出哈夫曼樹的結構和各字符名稱及對應的哈夫曼編碼；4. 編碼，對輸入的字符串進行哈夫曼編碼，將結果寫入文件；5. 譯碼，將文件中的哈夫曼編碼按照編碼表翻譯成對應字符串并顯示到終端上3.2.2設計流程圖給定字符串及對應頻率結束創建哈夫曼編碼表輸

9、入字符讀取codefile文件并譯碼構造哈夫曼樹編碼并寫入文件codefile數據輸出顯示圖2.1 總流程圖1. 定義哈夫曼結點存儲結構和哈夫曼編碼存儲結構，之后定義一個結點存儲結構數組用來存放結點信息，和定義一個編碼存儲結構數組用來存放字符的哈夫曼編碼，同時定義全局數組存放字符和它的使用頻度。2. 先將已建立好的二叉樹初始化，再對其中的葉結點其賦予字符名和對應使用頻度作為結點名和結點權值，最后通過哈夫曼算法構造哈夫曼樹，同時在屏幕輸出哈夫曼樹。3. 通過已建立好的哈夫曼樹再對字符進行二進制編碼，編碼結束后，對應每個字符都有一個二進制編碼，此編碼即為哈夫曼編碼，將字符及其哈夫曼編碼存放到哈夫曼

10、編碼存儲結構體數組中去，構成哈夫曼編碼表，同時在屏幕上輸出哈夫曼編碼表。4. 編碼函數執行，即對輸入的字符串根據哈夫曼編碼表進行編碼，將字符串的二進制編碼存放到一個字符數組中去。5. 建立文件，將字符數組中的二進制編碼寫入文件，這需要定義輸出流類的對象并與文件關聯，通過操作對象來操作文件的數據寫入。6. 將文件中的二進制編碼進行譯碼，這需要定義輸入流類的對象并與文件關聯，將文件中的編碼讀取到另一字符數組中去，調用譯碼函數進行譯碼。7. 結束。四、 詳細設計 creattreehuffman creatcodehuffman writecodehuffmanmain transcodehuffm

11、an printtreehuffman printcodehuffman 4.1哈夫曼樹的建立4.1.1哈夫曼樹的存儲結構為了實現通過哈夫曼算法建立哈夫曼樹，首先要定義哈夫曼樹的存儲結構。由于構造哈夫曼樹之后，編碼時要從葉結點出發走一條從葉結點到根的路徑，而譯碼時要從根結點出發走一條從根到葉結點的路徑。對于每個結點而言，既需知道雙親的信息，又需知道孩子的信息。因此，可以使用帶雙親的孩子鏈表作為結點的存儲結構。由哈夫曼算法可知，如果哈夫曼有n個葉結點，則最終生成的哈夫曼樹共有2n-1個結點。因此，可以用一個長度為2n的一維數組存放哈夫曼樹的所有結點。詳細定義如下：#define Leafnum

12、27#define Hufnum 2*Leafnumtypedef char DataType;typedef struct Tnode DataType name;double weight;int lchild, rchild, parent;Huftree;Huftree TreeHufnum;其中，name表示結點數據的名稱（即字符名稱），weight表示結點的權值（即字符使用頻度），lchild、rchild分別是結點的左、右孩子在數組中的下標值，葉結點的左右孩子的下標值均為0；parent表示結點雙親在數組中的位置。它的主要作用有兩點：第一，區分根結點和非根結點；第二，使得查找某個

13、結點的雙親變的更為簡單。若parent=0，則該結點是樹的根結點，否則為非根結點。因為把森林中的兩棵二叉樹合并成一棵二叉樹時，必須從森林的所有結點中選取兩個根結點的權值為最小的結點，此時就是根據parent來區分根與非根結點的。4.1.2建立哈夫曼樹本設計只對26個英文大寫字符及空格進行了哈夫曼編碼，各字符及對應使用頻度如下表所示：表4.1 字符及其使用頻度字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161需要定義全局數組來存放這些字符名稱和對應頻度：char ch = 

14、9;0',' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W',

15、9;X','Y','Z'float w = 0,186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1;定義函數CreatTreeHuffman，其中包括對已建立好的哈夫曼樹的初始化，即將結點數據名稱初始化為0，將結點權值、結點雙親及左右孩子的下標值都初始化為0；對已初始化的哈夫曼樹賦值，將全局數組ch中存放的字符名稱賦到葉結點的name上，將全局數組w中存放的字符使用頻度賦到葉結點的weight上；最后根據哈夫曼算法對27個結點（每個結點可以看做是一棵樹）

16、構造出哈夫曼樹。4.2哈夫曼編碼表的建立4.2.1哈夫曼編碼表的存儲結構利用哈夫曼樹對字符進行哈夫曼編碼，實際上就是求出從根結點到葉結點的路徑。由于采用帶雙親的孩子鏈表作為存儲結構，因此，對于輸入的每個字符，可以從哈夫曼樹的葉結點出發，沿結點的雙親鏈回溯到根結點，在這個過程中，每回溯一步都會經過哈夫曼樹的一個分支，從而得到一個哈夫曼編碼。因此，可設置一個位串數組bits，將生成的代碼序列從后到前依次存放到數組bits中。哈夫曼編碼表存儲結構定義如下：typedef struct Cnode char bitsLeafnum+1;int start;char ch;hufcode;由于葉子結點總

17、數即字符個數為Leafnum，故不等長編碼的長度不會超過Leafnum，再加上結束符號0，位串數組bits的大小應為Leafnum+1，整型變量start用來指示編碼在數組中的起始位置，當某個字符編碼完成時，從變量的start處開始將編碼復制到該字符對應的數組bits中去即可。4.2.2建立哈夫曼編碼表建立哈夫曼編碼表即建立一個表格用來存儲每個字符名稱和對應的哈夫曼編碼，此過程建立在已經構造好的哈夫曼樹上，從葉結點開始，沿著雙親鏈向上，記錄沿途經過分支上的二進制編碼，直到到達根結點，于是對應每一個字符都有一個二進制串，即它的哈夫曼編碼，用上面定義的哈夫曼編碼表存儲結構數組存放起來，即存在位串數

18、組bits中。4.3編碼本程序的功能是能對從鍵盤輸入的任意有限長度的字符串（限定在大寫英文字符和空格）進行哈夫曼編碼，因此需要定義函數WritecodeHuffman來實現對輸入的字符串逐個進行編碼，此過程實質上是將字符與編碼表里的字符名稱相比較，當名稱一致時，就輸出對應字符的bits數組中的二進制編碼，然后依次輸出每個字符的哈夫曼編碼，將他們連續的顯示在屏幕上。4.4文件寫入由于要將這些二進制串寫入文件，所以事先再定義一個全局字符數組Huffmancode來存儲這些二進制串。在主函數先在某目錄下建立一個.txt文件，名為codefile，再定義了一個輸出流類ofstream的對象ofs，定義

19、ofs的同時將其與文件codefile關聯，于是，就可以通過操作ofs來實現文件數據的寫入，即將字符數組Huffmancode中的二進制編碼寫入文件。14.5譯碼譯碼的過程與編碼的過程相反，先將codefile文件中的二進制編碼讀出來，這時在主函數中也定義一個輸入流類ifstream的對象ifs，同時將它與文件codefile關聯，通過ifs讀取codefile文件中的二進制編碼，存放到數組buffer中，再通過譯碼函數進行譯碼， TranscodeHuffman譯碼函數定義如下：void TranscodeHuffman (Hufcode code , Huftree tree , char

20、 s ) int i;char *q=NULL;i=Hufnum-1; q=s;while (*q!='0')if (*q='0') i=treei.lchild;if (*q='1') i=treei.rchild;if (treei.lchild=0)&&(treei.rchild=0)cout << codei.ch;i = Hufnum - 1;q+;cout << endl;該函數帶三個參數，分別是已建立好的哈夫曼樹結點數組，哈夫曼編碼表數組和需要進行譯碼的字符數組，該字符數組存放的即為由0、1組

21、成的一串編碼，函數中設置字符類型指針q開始指向字符數組的第一個字符，若為0，則進入左孩子，否則進入右孩子，再執行q+，直到某結點的左右孩子下標值均為0的時候，此時的結點即為葉結點，于是輸出對應字符，再將起始結點設為根結點，重復上述過程，直到翻譯出所有字符。五、 測試結果5.1 哈夫曼樹輸出根據所給的27個字符及使用頻度所建立的的哈夫曼樹結構輸出如圖5.1圖5.1哈夫曼樹輸出第一列是字符序號，也就是在建立的存儲結構數組tree中各結點的下標值，1到27對應的是葉結點；第二列是字符名稱，每個葉結點對應一個字符；第三列是字符使用頻度，也即葉結點的權值；后面三列則列出了每個結點雙親及左右孩子在結構數組

22、中的下標值，雖然是以表格方式表示這棵樹，但從中可以體現出整個哈夫曼樹的樹形結構。5.2哈夫曼編碼表輸出根據哈夫曼樹所建立的哈夫曼編碼表輸出如圖5.2圖5.2 哈夫曼編碼表輸出哈夫曼編碼表第一列和第二列仍給出字符序號和字符名稱，第三列是字符編碼，即對應于各個字符的哈夫曼編碼。此表列出了所有27個字符和與其對應的哈夫曼編碼，每個哈夫曼編碼都存在編碼表結構數組中，這樣，對任意輸入的字符串（限定在大寫英文字符和空格）進行哈夫曼編碼時，只需逐個按照表格找到其對應編碼，再將它們存放到一起，即可得到字符串的哈夫曼編碼。5.3 編碼和譯碼對任意字符串的編碼和譯碼運行如圖5.3圖4.3 字符串編碼和譯碼結果輸出

23、主函數執行時，先調用CreatTreeHuffman和CreatcodeHuffman兩函數建立哈夫曼樹和哈夫曼編碼表，對應也輸出顯示它們。于是再進入功能執行部分，即函數WritecodeHuffman，在窗口中顯示“請輸入字符串：”，于是手動輸入任意大寫英文字符或空格，即可將它的哈夫曼編碼顯示出來。5.4 文件讀寫本程序還實現了文件的讀寫過程，即將輸入字符串的二進制編碼寫入文件codefile中，也能讀出codefile文件中的二進制編碼再進行譯碼便顯示到終端上，這個過程即可視為實際生活中兩計算機之間模擬數據傳輸過程，將發送方的信息數據（字符串）進行哈夫曼編碼，得到二進制串，即文件寫入過程；

24、接收方再將二進制串翻譯成信息，即文件讀取過程。codefile文件打開如圖5-4主函數中先創建一個文件名為”d:codefile.txt”的文本文件，再定義一個文件輸出流類ofstream的對象ofs，并將其與文件codefile關聯到一起，再將之前存放字符串哈夫曼編碼的數組寫入文件，隨后定義一個文件輸入流類ifstream的對象ifs，并將其與文件codefile關聯，同時定義一個緩存字符數組buffer用于存放從codefile文件中讀取出來的二進制編碼，最后調用譯碼函數transcodehuffman對buffer中的編碼進行譯碼，把譯出的字符顯示出來。六、 總結及調試分析本次課程設計涵

25、蓋了對字符及其使用頻度構造哈夫曼樹和哈夫曼編碼表，再對輸入字符進行哈夫曼編碼，將編碼寫入文件進而讀取文件并譯碼等模塊功能，整個過程將結構體、指針、數組、語句循環選擇結構，鏈表，文件讀寫等知識聯系在一起，考察了我們運用C+語言的能力以及對數據結構的理解，通過幾天的編寫和調試，基本上實現了數據傳輸的過程。而在這個過程中，我開始進展十分緩慢，主要是因為首次接觸有關程序實現編碼的問題，對樹形結構也不怎么了解，于是在第一步構造哈夫曼樹的時候就花了很長時間來理解哈夫曼算法，哈夫曼樹構造函數里面設置了很多變量，那個核心部分怎么也看不懂，我帶著疑惑地將代碼全都打出來，運行成功后我對著結果一步一步列出其中的過程

26、，在循環中確定每一次各變量的值，對照著事先畫好的哈夫曼樹仔細看了看，終于了解了各變量的作用，哈夫曼樹構造的原理大致也就清楚了，于是后面的哈夫曼編碼表結構，哈夫曼譯碼過程也迎刃而解，整個過程的原理就把握住了。在上機調試的時候，也屢次出行過錯誤，例如對字符進行哈夫曼編碼的時候，是從哈夫曼樹的根結點開始沿雙親鏈往上回溯的，于是這樣得到的編碼實際上是反過來的，但用來存儲它們的位串數組也不一般，在編碼表結構里還定義了一個位置變量start，用以指示哈夫曼編碼在數組中的起始位置，start是從最后一個開始指向的，即從后面開始存儲二進制編碼，于是從前面開始讀取就能獲得字符的哈夫曼編碼。通過這樣不斷的調試，我

27、對整個結構的理解就越來越清楚，經過幾天的努力，一個小型的哈夫曼編譯碼系統就完成了。整個系統能實現對任意輸入的空格或26個大寫英文字符進行哈弗曼編碼，再寫入文件，最后讀取文件并譯碼的功能。七、 參考文獻數據結構 嚴蔚敏 吳偉民著 清華大學出版社C+程序設計 譚浩強 著 清華大學出版社附錄：源代碼#include <iostream>#include <fstream>using namespace std;#define leafnum 27#define hufnum 2*leafnum#define maxdouble 9999.9typedef char datat

28、ype;typedef struct tnode / 哈夫曼樹結點存儲結構datatype name;double weight;int lchild, rchild, parent;huftree;typedef struct cnode / 哈夫曼編碼表結構char bitsleafnum+1;int start;char ch;hufcode;hufcode codeleafnum+1;huftree treehufnum+1;char huffmancode1000;char ch = '0',' ','A','B',&#

29、39;C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'float w = 0,186

30、,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1;void creattreehuffman(huftree tree) / 建立哈夫曼樹int i, j, p1, p2;double least1, least2;for (i=1; i<=hufnum; i+) = '0'treei.parent = 0;treei.lchild = 0;treei.rchild = 0;treei.weight = 0.0;for (i=1; i<=leafnu

31、m; i+) = chi;treei.weight = wi;for (i=leafnum+1; i<=hufnum; i+)p1=0; p2=0; least1=least2=maxdouble;for (j=1; j<i; j+)if (treej.parent=0)if (treej.weight<least1)least2=least1;least1=treej.weight;p2=p1;p1=j;elseif(treej.weight<least2)least2=treej.weight;p2=j;treep1.parent=i;treep

32、2.parent=i;treei.lchild=p1;treei.rchild=p2;treei.weight=treep1.weight+treep2.weight;treehufnum-1.parent=0;void creatcodehuffman(hufcode code, huftree tree) / 建立哈夫曼編碼int i, c, p;hufcode buf;for (i=1; i<=leafnum; i+)buf.ch=chi;buf.start=leafnum;c=i;p=treei.parent;while (p != 0)buf.start-;if (treep.

33、lchild=c)buf.bitsbuf.start='0'else buf.bitsbuf.start='1'c=p;p=treep.parent;codei=buf;void writecodehuffman(hufcode code, huftree tree) /哈弗曼編碼int i, j, k, n=0;char c100;cout << "請輸入字符串:" << endl;gets(c);cout << endl;cout << "則字符串的哈夫曼編碼為:" &l

34、t;< endl;for (i=0; i<strlen(c); i+)for (j=1; j<=leafnum; j+)if (ci=)for(k=codej.start; k<leafnum; k+)cout << codej.bitsk;huffmancoden = codej.bitsk;n+;void transcodehuffman(hufcode code, huftree tree, char s) / 哈夫曼譯碼int i;char *q=NULL;i=hufnum-1; q=s;while (*q!='0'

35、;)if (*q='0') i=treei.lchild;if (*q='1') i=treei.rchild;if (treei.lchild=0)&&(treei.rchild=0)cout << codei.ch;i = hufnum - 1;q+;cout << endl;void printtreehuffman(huftree tree) / 輸出哈夫曼樹int i;cout << "根據字符的使用概率所建立的哈夫曼數為:"<<endl;cout << "字符序號 字符名稱 字符頻率 雙親位置 左孩子 右孩子"<<endl;for (i = 1; i < hufnum; i+)cout << " " << i << "t " << <<"t"cout << treei.weight <