1、“數據結構課設哈夫曼編譯碼器學 號: 姓 名: 提交日期: 成 績:實驗名稱 哈夫曼編/譯碼器的實現二、實驗要求【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳來數據預先編碼，在接收端將傳來的數據進行譯碼(復原)。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/譯碼系統。【基本要求】一個完整的系統應具有以下功能：(1)1 :初始化(Initialization)。從終端讀入字符集大小 n ,以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件h

2、fmTree中。(2)E ：編碼(Encoding)。利用已建好的哈夫曼樹(如不在內存，則從文件hfmTree中讀人)， 對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。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 Huffman 創立的， 是二叉樹的一種特殊轉化形式。編碼的原理是：將使用次數多的

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

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

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

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

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

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

12、曼樹的所有結點。詳細定義如下： #define Leafnum 27 #define Hufnum 2*Leafnum typedef 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頻度57631514851802381

14、81161需要定義全局數組來存放這些字符名稱和對應頻度：char ch口 = '0','','A','B','C','D','E','F','G','H',T,'J','K,'L','M',N,'O','P','Q','R,S,'r,'U',V,W,'X','Y',Z;f

15、loat 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個結點（每個結點可以看做是一棵樹）構造出哈夫曼樹。4.2 哈夫曼編碼表的建立

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

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

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

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

20、code , Huftree tree , char 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;該函數帶三個參數，分別是已建立好的哈夫曼樹結點數組，哈夫曼編碼表數組和需

21、要進行譯碼的字符數組，該字符數組存放的即為由0、 1 組成的一串編碼，函數中設置字符類型指針 q 開始指向字符數組的第一個字符，若為0，則進入左孩子，否則進入右孩子，再執行q+,直到某結點的左右孩子下標值均為0的時候，此時的結點即為葉結點，于是輸出對應字符，再將起始結點設為根結點，重復上述過程，直到翻譯出所有字符。5、 測試結果5.1 哈夫曼樹輸出5.1 根據所給的27 個字符及使用頻度所建立的的哈夫曼樹結構輸出如圖汗 孩。 右0 : 5 為親 iRlxrx3 13 83 4 4 2嚏G8432201577 力裨 16123121451既名 ABCDEFGHIJ0 1 12345678911

22、螂子24,0 12 33 3 3 35 6?3 3 35 7 9 03 3 11514142434445467 8 9 0 1 24 4 4- 5 5 5 -S圖5.1哈夫曼樹輸出第一列是字符序號，也就是在建立的存儲結構數組tree中各結點的下標值，1到27對應的是葉結點；第二列是字符名稱， 每個葉結點對應一個字符；第三列是字符使用頻度，也 即葉結點的權值；后面三列則列出了每個結點雙親及左右孩子在結構數組中的下標值，雖然是以表格方式表示這棵樹，但從中可以體現出整個哈夫曼樹的樹形結構。5.2 哈夫曼編碼表輸出根據哈夫曼樹所建立的哈夫曼編碼表輸出如圖5.2 .1ill2由101834C000895

23、D1011S6E目1目7F110011aCiemi?H00811的1Him11Jiiosssim12K11Q80O1113L1011114110U18±5K011116O17P18Q11090010011920S001121I110122IIM用d用23U11Q9Q0024財11008125iiMnnntRf n圖5.2哈夫曼編碼表輸出哈夫曼編碼表第一列和第二列仍給出字符序號和字符名稱，第三列是字符編碼，即對應于各個字符的哈夫曼編碼。此表列出了所有27個字符和與其對應的哈夫曼編碼，每個哈夫曼編碼都存在編碼表結構數組中，這樣，對任意輸入的字符串（限定在大寫英文字符和空格） 進行哈夫曼編

24、碼時，只需逐個按照表格找到其對應編碼，再將它們存放到一起， 即可得到字符串的哈夫曼編碼。5.3 編碼和譯碼對任意字符串的編碼和譯碼運行如圖5.3 .27Z1100001011請輸入字行串工THIS PROJECT IS M¥ FfiUORITEhi字符串的哈夫曼編碼為二ii oi era Qi mm ii 1110061 owl Qi dAin moi RR00100(3001 leu 11ii ii 001mm門”文件中的代幣駁口下！110106010110001111110001 00010100111000010000103006011011110110611111110010

25、10111111100111 01Q11000001S0imi06116110101 08踴門文件中代碼譯碼為：THIS PROJECT IS MV FfilfORIIEPress a.ny key to cont Inue圖4.3字符串編碼和譯碼結果輸出主函數執行時，先調用 CreatTreeHuffman 和CreatcodeHuffman 兩函數建立哈夫曼樹和 哈夫曼編碼表，對應也輸出顯示它們。于是再進入功能執行部分，即函數WritecodeHuffman , 在窗口中顯示“請輸入字符串：”，于是手動輸入任意大寫英文字符或空格，即可將它的哈夫曼編碼顯不' 出來。5.4 文件讀寫本

26、程序還實現了文件的讀寫過程，即將輸入字符串的二進制編碼寫入文件codefile 中,也能讀出codefile 文件中的二進制編碼再進行譯碼便顯示到終端上，這個過程即可視為實 際生活中兩計算機之間模擬數據傳輸過程，將發送方的信息數據（字符串）進行哈夫曼編碼，得到二進制串，即文件寫入過程；接收方再將二進制串翻譯成信息，即文件讀取過程。codefile 文件打開如圖 5-4 .主函數中先創建一個文件名為”d:codefile.txt的文本文件，再定義一個文件輸出流類 ofstream 的對象 ofs ，并將其與文件codefile 關聯到一起，再將之前存放字符串哈夫曼編碼的數組寫入文件，隨后定義一個

27、文件輸入流類ifstream 的對象 ifs ，并將其與文件codefile 關聯，同時定義一個緩存字符數組buffer 用于存放從codefile 文件中讀取出來的二進制編碼，最后調用譯碼函數transcodehuffman 對 buffer 中的編碼進行譯碼，把譯出的字符顯示出來。6、 總結及調試分析本次課程設計涵蓋了對字符及其使用頻度構造哈夫曼樹和哈夫曼編碼表，再對輸入字符進行哈夫曼編碼，將編碼寫入文件進而讀取文件并譯碼等模塊功能，整個過程將結構體、指針、數組、語句循環選擇結構，鏈表，文件讀寫等知識聯系在一起，考察了我們運用C+詡言的能力以及對數據結構的理解，通過幾天的編寫和調試，基本上

28、實現了數據傳輸的過程。而在這個過程中，我開始進展十分緩慢，主要是因為首次接觸有關程序實現編碼的問題，對樹形結構也不怎么了解，于是在第一步構造哈夫曼樹的時候就花了很長時間來理解哈夫曼算法，哈夫曼樹構造函數里面設置了很多變量，那個核心部分怎么也看不懂，我帶著疑惑地將代碼全都打出來，運行成功后我對著結果一步一步列出其中的過程，在循環中確定每一次各變量的值，對照著事先畫好的哈夫曼樹仔細看了看，終于了解了各變量的作用，哈夫曼樹構造的原理大致也就清楚了，于是后面的哈夫曼編碼表結構，哈夫曼譯碼過程也迎刃而解，整個過程的原理就把握住了。在上機調試的時候，也屢次出行過錯誤，例如對字符進行哈夫曼編碼的時候，是從哈

29、夫曼樹的根結點開始沿雙親鏈往上回溯的，于是這樣得到的編碼實際上是反過來的，但用來存儲它們的位串數組也不一般，在編碼表結構里還定義了一個位置變量start ， 用以指示哈夫曼編碼在數組中的起始位置，start 是從最后一個開始指向的，即從后面開始存儲二進制編碼，于是從前面開始讀取就能獲得字符的哈夫曼編碼。通過這樣不斷的調試，我對整個結構的理解就越來越清楚，經過幾天的努力，一個小型的哈夫曼編譯碼系統就完成了。整個系統能實現對任意輸入的空格或26 個大寫英文字符進行哈弗曼編碼，再寫入文件，最后讀取文件并譯碼的功能。7、 參考文獻數據結構嚴蔚敏 吳偉民著清華大學出版社C+強序設計譚浩強著清華大學出版社

30、附錄：源代碼#include <iostream>#include <fstream>using namespace std;#define leafnum 27#define hufnum 2*leafnum#define maxdouble 9999.9typedef char datatype;typedef struct tnode/哈夫曼樹結點存儲結構datatype name;double weight;int lchild, rchild, parent;huftree;typedef struct cnode/哈夫曼編碼表結構char bitsleafn

31、um+1;int start;char ch;hufcode;hufcode codeleafnum+1;huftree treehufnum+1;char huffmancode1000;char ch = '0','','A','B','C','D','E','F','G','H','I','J','K','L','M','N','

32、;O','P','Q' ,'R','S','T','U','V','W','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;void creattreehuffman(huftree tree) /建立哈夫曼樹int i, j, p1, p2;double leas

33、t1, 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<=leafnum; 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.pa

34、rent=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;treep2.parent=i;treei.lchild=p1;treei.rchild=p2;treei.weight=treep1.weight+treep2.weight;treehufnum-1.parent=0;/建立void creatcodehuffman(hufcode code,

35、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.lchild=c)buf.bitsbuf.start='0'else buf.bitsbuf.start='1'c=p;p=treep.parent;codei=buf;void writecodehuffman(hufcode code, huftree tr

36、ee) /哈弗曼編碼int i, j, k, n=0;char c100;cout << " 請輸入字符串:" << endl;gets(c);cout << endl;cout << " 則字符串的哈夫曼編碼為:" << 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.b

37、itsk;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')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