數(shù)據(jù)結(jié)構(gòu)哈夫曼編譯碼器

1、“數(shù)據(jù)結(jié)構(gòu)課設(shè)哈夫曼編譯碼器學(xué) 號(hào): 姓 名: 提交日期: 成 績(jī):實(shí)驗(yàn)名稱(chēng) 哈夫曼編/譯碼器的實(shí)現(xiàn)二、實(shí)驗(yàn)要求【問(wèn)題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳來(lái)數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)?！净疽蟆恳粋€(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1)1 :初始化(Initialization)。從終端讀入字符集大小 n ,以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件h

2、fmTree中。(2)E ：編碼(Encoding)。利用已建好的哈夫曼樹(shù)(如不在內(nèi)存，則從文件hfmTree中讀人)， 對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。D:譯碼(Decoding)。利用已建好的哈夫曼樹(shù)將文件CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile 中。(4)P :打印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行 50個(gè) 代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件CodePrin中。(5)T :打印哈夫曼樹(shù)(Tree printing) 。將已在內(nèi)存中的哈夫曼樹(shù)以直觀(guān)的方式(樹(shù)或凹入表形式)顯示

3、在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中?！緶y(cè)試數(shù)據(jù)】(1)利用教科書(shū)例6-2中的數(shù)據(jù)調(diào)試程序。(2)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼："THIS PROGRAM IS MY FAVORITE”字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161需求分析Huffman 編碼是一種可變長(zhǎng)編碼方式，是由美國(guó)數(shù)學(xué)家David Huffman 創(chuàng)立的， 是二叉樹(shù)的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的

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

5、積稱(chēng)為該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度，樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和稱(chēng)為樹(shù)的帶權(quán)路徑長(zhǎng)度。通常記作：nWPL =wi lii1式中， n 表示樹(shù)中葉子結(jié)點(diǎn)的數(shù)目，wi 表示葉結(jié)點(diǎn)ki 的權(quán)， li 表示根結(jié)點(diǎn)到葉結(jié)點(diǎn)Ki之間的路徑長(zhǎng)度。在n個(gè)權(quán)值為w1,w2,wn的帶權(quán)葉結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，其帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)即為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)。3.1.2 哈夫曼算法給定 n 個(gè)帶權(quán)葉結(jié)點(diǎn)，如何構(gòu)造一棵n 個(gè)帶有給定權(quán)值的葉結(jié)點(diǎn)的二叉樹(shù)，使其帶權(quán)路徑長(zhǎng)度最?。抗蚵紫冉o出了構(gòu)造最有二叉樹(shù)的方法，故稱(chēng)其為哈夫曼算法，其基本的算法思想如下：將n個(gè)權(quán)值分別是w1,w2,wn的結(jié)點(diǎn)按權(quán)值遞增排列。將每

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

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

8、就譯出該葉子結(jié)點(diǎn)所代表字符。3.2 設(shè)計(jì)方案3.2.1 設(shè)計(jì)思路要編程實(shí)現(xiàn)該系統(tǒng)，需逐步實(shí)現(xiàn)：1. 哈夫曼樹(shù)的建立，即根據(jù)所給字符及對(duì)應(yīng)頻度構(gòu)造哈夫曼樹(shù)，哈夫曼樹(shù)構(gòu)造函數(shù)包括對(duì)哈夫曼樹(shù)的初始化、賦值和建立；2. 哈夫曼編碼表的建立，即編寫(xiě)程序?qū)崿F(xiàn)對(duì)所給字符進(jìn)行哈夫曼編碼，將每個(gè)字符的哈夫曼編碼存儲(chǔ)到一個(gè)位串?dāng)?shù)組中去；3. 打印輸出哈夫曼樹(shù)和哈夫曼編碼表，在終端上顯示出哈夫曼樹(shù)的結(jié)構(gòu)和各字符名稱(chēng)及對(duì)應(yīng)的哈夫曼編碼；4. 編碼，對(duì)輸入的字符串進(jìn)行哈夫曼編碼，將結(jié)果寫(xiě)入文件；5. 譯碼，將文件中的哈夫曼編碼按照編碼表翻譯成對(duì)應(yīng)字符串并顯示到終端上3.2.2設(shè)計(jì)流程圖給定字符串及對(duì)應(yīng)頻率也 一構(gòu)造哈夫

9、曼樹(shù)創(chuàng)建哈夫曼編碼表一 U輸入字符口編碼并寫(xiě)入文件codefile讀取codefile文件并譯碼- n -數(shù)據(jù)輸出顯示結(jié)束圖2.1總流程圖1 .定義哈夫曼結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)和哈夫曼編碼存儲(chǔ)結(jié)構(gòu)，之后定義一個(gè)結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)數(shù)組 用來(lái)存放結(jié)點(diǎn)信息，和定義一個(gè)編碼存儲(chǔ)結(jié)構(gòu)數(shù)組用來(lái)存放字符的哈夫曼編碼，同 時(shí)定義全局?jǐn)?shù)組存放字符和它的使用頻度。2 .先將已建立好的二叉樹(shù)初始化，再對(duì)其中的葉結(jié)點(diǎn)其賦予字符名和對(duì)應(yīng)使用頻度作 為結(jié)點(diǎn)名和結(jié)點(diǎn)權(quán)值，最后通過(guò)哈夫曼算法構(gòu)造哈夫曼樹(shù)，同時(shí)在屏幕輸出哈夫曼 樹(shù)。3 .通過(guò)已建立好的哈夫曼樹(shù)再對(duì)字符進(jìn)行二進(jìn)制編碼，編碼結(jié)束后，對(duì)應(yīng)每個(gè)字符都 有一個(gè)二進(jìn)制編碼，此編碼即為哈夫

10、曼編碼，將字符及其哈夫曼編碼存放到哈夫曼 編碼存儲(chǔ)結(jié)構(gòu)體數(shù)組中去，構(gòu)成哈夫曼編碼表，同時(shí)在屏幕上輸出哈夫曼編碼表。4 .編碼函數(shù)執(zhí)行，即對(duì)輸入的字符串根據(jù)哈夫曼編碼表進(jìn)行編碼，將字符串的二進(jìn)制 編碼存放到一個(gè)字符數(shù)組中去。5 .建立文件，將字符數(shù)組中的二進(jìn)制編碼寫(xiě)入文件，這需要定義輸出流類(lèi)的對(duì)象并與 文件關(guān)聯(lián)，通過(guò)操作對(duì)象來(lái)操作文件的數(shù)據(jù)寫(xiě)入。6 .將文件中的二進(jìn)制編碼進(jìn)行譯碼，這需要定義輸入流類(lèi)的對(duì)象并與文件關(guān)聯(lián)，將文 件中的編碼讀取到另一字符數(shù)組中去，調(diào)用譯碼函數(shù)進(jìn)行譯碼。7 . 結(jié)束。四、詳細(xì)設(shè)計(jì).ucreattreehuffman creatcodehuffman writecodeh

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

12、曼樹(shù)的所有結(jié)點(diǎn)。詳細(xì)定義如下： #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表示結(jié)點(diǎn)數(shù)據(jù)的名稱(chēng)（即字符名稱(chēng)），weight表示結(jié)點(diǎn)的權(quán)值（即字符使用頻度），lchild 、rchild 分別是結(jié)點(diǎn)的左、右孩子在數(shù)組中的下標(biāo)值，葉結(jié)點(diǎn)的左右孩子的 下標(biāo)值均為0; parent表示結(jié)點(diǎn)雙親在數(shù)組

13、中的位置。它的主要作用有兩點(diǎn)：第一，區(qū)分根 結(jié)點(diǎn)和非根結(jié)點(diǎn)；第二，使得查找某個(gè)結(jié)點(diǎn)的雙親變的更為簡(jiǎn)單。若parent=0 ,則該結(jié)點(diǎn)是樹(shù)的根結(jié)點(diǎn)，否則為非根結(jié)點(diǎn)。因?yàn)榘焉种械膬煽枚鏄?shù)合并成一棵二叉樹(shù)時(shí)，必須從森林的所有結(jié)點(diǎn)中選取兩個(gè)根結(jié)點(diǎn)的權(quán)值為最小的結(jié)點(diǎn)，此時(shí)就是根據(jù)parent來(lái)區(qū)分根與非根結(jié)點(diǎn)的。4.1.2 建立哈夫曼樹(shù)本設(shè)計(jì)只對(duì)26個(gè)英文大寫(xiě)字符及空格進(jìn)行了哈夫曼編碼，各字符及對(duì)應(yīng)使用頻度如下 表所示：表4.1字符及其使用頻度字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381

14、81161需要定義全局?jǐn)?shù)組來(lái)存放這些字符名稱(chēng)和對(duì)應(yīng)頻度：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 ;定義函數(shù)CreatTreeHuffman ,其中包括對(duì)已建立好的哈夫曼樹(shù)的初始化，即將結(jié)點(diǎn)數(shù) 據(jù)名稱(chēng)初始化為'0 ',將結(jié)點(diǎn)權(quán)值、結(jié)點(diǎn)雙親及左右孩子的下標(biāo)值都初始化為0;對(duì)已初始化的哈夫曼樹(shù)賦值，將全局?jǐn)?shù)組ch中存放的字符名稱(chēng)賦到葉結(jié)點(diǎn)的name上，將全局?jǐn)?shù)組w中存放的字符使用頻度賦到葉結(jié)點(diǎn)的weight上；最后根據(jù)哈夫曼算法對(duì)27個(gè)結(jié)點(diǎn)（每個(gè)結(jié)點(diǎn)可以看做是一棵樹(shù)）構(gòu)造出哈夫曼樹(shù)。4.2 哈夫曼編碼表的建立

16、4.2.1 哈夫曼編碼表的存儲(chǔ)結(jié)構(gòu)利用哈夫曼樹(shù)對(duì)字符進(jìn)行哈夫曼編碼，實(shí)際上就是求出從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑。由于 采用帶雙親的孩子鏈表作為存儲(chǔ)結(jié)構(gòu)，因此，對(duì)于輸入的每個(gè)字符，可以從哈夫曼樹(shù)的葉結(jié) 點(diǎn)出發(fā)，沿結(jié)點(diǎn)的雙親鏈回溯到根結(jié)點(diǎn)，在這個(gè)過(guò)程中，每回溯一步都會(huì)經(jīng)過(guò)哈夫曼樹(shù)的一 個(gè)分支，從而得到一個(gè)哈夫曼編碼。因此，可設(shè)置一個(gè)位串?dāng)?shù)組 bits ,將生成的代碼序列從 后到前依次存放到數(shù)組 bits中。哈夫曼編碼表存儲(chǔ)結(jié)構(gòu)定義如下：typedef struct Cnodechar bitsLeafnum+1;int start;char ch;hufcode;由于葉子結(jié)點(diǎn)總數(shù)即字符個(gè)數(shù)為L(zhǎng)eafnu

17、m,故不等長(zhǎng)編碼的長(zhǎng)度不會(huì)超過(guò)Leafnum,再加上結(jié)束符號(hào)0 ，位串?dāng)?shù)組 bits 的大小應(yīng)為L(zhǎng)eafnum+1 ，整型變量start 用來(lái)指示編碼在數(shù)組中的起始位置，當(dāng)某個(gè)字符編碼完成時(shí)，從變量的start 處開(kāi)始將編碼復(fù)制到該字符對(duì)應(yīng)的數(shù)組bits 中去即可。4.2.2 建立哈夫曼編碼表建立哈夫曼編碼表即建立一個(gè)表格用來(lái)存儲(chǔ)每個(gè)字符名稱(chēng)和對(duì)應(yīng)的哈夫曼編碼，此過(guò)程建立在已經(jīng)構(gòu)造好的哈夫曼樹(shù)上，從葉結(jié)點(diǎn)開(kāi)始，沿著雙親鏈向上，記錄沿途經(jīng)過(guò)分支上的二進(jìn)制編碼，直到到達(dá)根結(jié)點(diǎn)，于是對(duì)應(yīng)每一個(gè)字符都有一個(gè)二進(jìn)制串，即它的哈夫曼編碼，用上面定義的哈夫曼編碼表存儲(chǔ)結(jié)構(gòu)數(shù)組存放起來(lái)，即存在位串?dāng)?shù)組bits

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

19、 ofs ，定義 ofs 的同時(shí)將其與文件codefile 關(guān)聯(lián)，于是，就可以通過(guò)操作ofs 來(lái)實(shí)現(xiàn)文件數(shù)據(jù)的寫(xiě)入，即將字符數(shù)組Huffmancode 中的二進(jìn)制編碼寫(xiě)入文件。 14.5 譯碼譯碼的過(guò)程與編碼的過(guò)程相反，先將codefile 文件中的二進(jìn)制編碼讀出來(lái)，這時(shí)在主函數(shù)中也定義一個(gè)輸入流類(lèi)ifstream 的對(duì)象 ifs ， 同時(shí)將它與文件codefile 關(guān)聯(lián)， 通過(guò) ifs讀取 codefile 文件中的二進(jìn)制編碼，存放到數(shù)組buffer 中，再通過(guò)譯碼函數(shù)進(jìn)行譯碼，TranscodeHuffman 譯碼函數(shù)定義如下：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;該函數(shù)帶三個(gè)參數(shù)，分別是已建立好的哈夫曼樹(shù)結(jié)點(diǎn)數(shù)組，哈夫曼編碼表數(shù)組和需

21、要進(jìn)行譯碼的字符數(shù)組，該字符數(shù)組存放的即為由0、 1 組成的一串編碼，函數(shù)中設(shè)置字符類(lèi)型指針 q 開(kāi)始指向字符數(shù)組的第一個(gè)字符，若為0，則進(jìn)入左孩子，否則進(jìn)入右孩子，再執(zhí)行q+,直到某結(jié)點(diǎn)的左右孩子下標(biāo)值均為0的時(shí)候，此時(shí)的結(jié)點(diǎn)即為葉結(jié)點(diǎn)，于是輸出對(duì)應(yīng)字符，再將起始結(jié)點(diǎn)設(shè)為根結(jié)點(diǎn)，重復(fù)上述過(guò)程，直到翻譯出所有字符。5、 測(cè)試結(jié)果5.1 哈夫曼樹(shù)輸出5.1 根據(jù)所給的27 個(gè)字符及使用頻度所建立的的哈夫曼樹(shù)結(jié)構(gòu)輸出如圖汗 孩。 右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哈夫曼樹(shù)輸出第一列是字符序號(hào)，也就是在建立的存儲(chǔ)結(jié)構(gòu)數(shù)組tree中各結(jié)點(diǎn)的下標(biāo)值，1到27對(duì)應(yīng)的是葉結(jié)點(diǎn)；第二列是字符名稱(chēng)， 每個(gè)葉結(jié)點(diǎn)對(duì)應(yīng)一個(gè)字符；第三列是字符使用頻度，也 即葉結(jié)點(diǎn)的權(quán)值；后面三列則列出了每個(gè)結(jié)點(diǎn)雙親及左右孩子在結(jié)構(gòu)數(shù)組中的下標(biāo)值，雖然是以表格方式表示這棵樹(shù)，但從中可以體現(xiàn)出整個(gè)哈夫曼樹(shù)的樹(shù)形結(jié)構(gòu)。5.2 哈夫曼編碼表輸出根據(jù)哈夫曼樹(shù)所建立的哈夫曼編碼表輸出如圖5.2 .1ill2由101834C000895

23、D1011S6E目1目7F110011aCiemi?H00811的1Him11Jiiosssim12K11Q80O1113L1011114110U18±5K011116O17P18Q11090010011920S001121I110122IIM用d用23U11Q9Q0024財(cái)11008125iiMnnntRf n圖5.2哈夫曼編碼表輸出哈夫曼編碼表第一列和第二列仍給出字符序號(hào)和字符名稱(chēng)，第三列是字符編碼，即對(duì)應(yīng)于各個(gè)字符的哈夫曼編碼。此表列出了所有27個(gè)字符和與其對(duì)應(yīng)的哈夫曼編碼，每個(gè)哈夫曼編碼都存在編碼表結(jié)構(gòu)數(shù)組中，這樣，對(duì)任意輸入的字符串（限定在大寫(xiě)英文字符和空格） 進(jìn)行哈夫曼編

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

25、10111111100111 01Q11000001S0imi06116110101 08踴門(mén)文件中代碼譯碼為：THIS PROJECT IS MV FfilfORIIEPress a.ny key to cont Inue圖4.3字符串編碼和譯碼結(jié)果輸出主函數(shù)執(zhí)行時(shí)，先調(diào)用 CreatTreeHuffman 和CreatcodeHuffman 兩函數(shù)建立哈夫曼樹(shù)和 哈夫曼編碼表，對(duì)應(yīng)也輸出顯示它們。于是再進(jìn)入功能執(zhí)行部分，即函數(shù)WritecodeHuffman , 在窗口中顯示“請(qǐng)輸入字符串：”，于是手動(dòng)輸入任意大寫(xiě)英文字符或空格，即可將它的哈夫曼編碼顯不' 出來(lái)。5.4 文件讀寫(xiě)本

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

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

28、實(shí)現(xiàn)了數(shù)據(jù)傳輸?shù)倪^(guò)程。而在這個(gè)過(guò)程中，我開(kāi)始進(jìn)展十分緩慢，主要是因?yàn)槭状谓佑|有關(guān)程序?qū)崿F(xiàn)編碼的問(wèn)題，對(duì)樹(shù)形結(jié)構(gòu)也不怎么了解，于是在第一步構(gòu)造哈夫曼樹(shù)的時(shí)候就花了很長(zhǎng)時(shí)間來(lái)理解哈夫曼算法，哈夫曼樹(shù)構(gòu)造函數(shù)里面設(shè)置了很多變量，那個(gè)核心部分怎么也看不懂，我?guī)е苫蟮貙⒋a全都打出來(lái)，運(yùn)行成功后我對(duì)著結(jié)果一步一步列出其中的過(guò)程，在循環(huán)中確定每一次各變量的值，對(duì)照著事先畫(huà)好的哈夫曼樹(shù)仔細(xì)看了看，終于了解了各變量的作用，哈夫曼樹(shù)構(gòu)造的原理大致也就清楚了，于是后面的哈夫曼編碼表結(jié)構(gòu)，哈夫曼譯碼過(guò)程也迎刃而解，整個(gè)過(guò)程的原理就把握住了。在上機(jī)調(diào)試的時(shí)候，也屢次出行過(guò)錯(cuò)誤，例如對(duì)字符進(jìn)行哈夫曼編碼的時(shí)候，是從哈

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

30、附錄：源代碼#include <iostream>#include <fstream>using namespace std;#define leafnum 27#define hufnum 2*leafnum#define maxdouble 9999.9typedef char datatype;typedef struct tnode/哈夫曼樹(shù)結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)datatype name;double weight;int lchild, rchild, parent;huftree;typedef struct cnode/哈夫曼編碼表結(jié)構(gòu)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) /建立哈夫曼樹(shù)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 << " 請(qǐng)輸入字符串:" << 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) /輸出哈夫曼樹(shù)int i;cout << " 根據(jù)字符的使用概率所建立的哈夫曼數(shù)為:"<<endl;cout << " 字符序號(hào)字符名稱(chēng)字符頻率雙親位置左孩子 右孩子 "<<endl;for (i = 1; i < hufnum; i+)cout << " " << i << "t