綜合訓(xùn)練_利用哈夫曼樹進(jìn)行編碼與解碼

1、數(shù)據(jù)結(jié)構(gòu)綜 合 訓(xùn) 練 報(bào) 告題 目利用哈夫曼樹進(jìn)行編碼與解碼班 級姓 名時 間2015年12 月7日利用哈夫曼樹進(jìn)行編碼與解碼一、目的和要求：使學(xué)生理解哈夫曼樹的概念、掌握哈夫曼樹的建立以及利用利用哈夫曼樹進(jìn)行哈夫曼編碼的算法思想。要求：1、使用文件流方式。2、要求提供編碼和解碼兩種方式3、能夠打開input.txt文件，統(tǒng)計(jì)其中字符出現(xiàn)的頻率，并以此進(jìn)行哈夫曼編碼，并將編碼后的結(jié)果輸出到output.txt文件中。4、能夠根據(jù)3中得到的字符編碼，將output.txt文件中的碼文進(jìn)行解碼，并將解碼后的結(jié)果輸出到input.txt文件中。二、概要設(shè)計(jì)：。該程序共有五個模塊組成：1. 統(tǒng)計(jì)字母

2、種類和個數(shù)模塊2. 哈弗曼樹的建立模塊3. 建立哈夫曼編碼的功能模塊4. 密文的輸出模塊。5.將密文轉(zhuǎn)化為原文模塊。各模塊之間無直接調(diào)用關(guān)系，但模塊三和模塊五調(diào)用了模塊二的結(jié)果，模塊二、三、四都調(diào)用了模塊一的結(jié)果。（1）統(tǒng)計(jì)字母種類和個數(shù)模塊 此模塊的功能是統(tǒng)計(jì)出字符串S中出現(xiàn)的字符infoi.ch，以及該字符的個數(shù)infoi.num。該模塊先把S的第一個字符存放在info0.ch中，并將info0.num置為1。然后進(jìn)行v次循環(huán)，每第k次循環(huán)將字符Sk分別于info結(jié)構(gòu)體中的infoi.ch元素進(jìn)行對比，若相等，則infoi.num+1,否則的話在info中新增加一個元素，將num元素置為1

3、。（2）哈弗曼樹的建立模塊 1、該模塊首先建立n棵二叉樹的森林并賦值。2、然后在森林中選出兩棵根節(jié)點(diǎn)的權(quán)值最小的樹作為一棵新樹的左右子樹，最小的作為左子樹，次小的作為右子樹，且置新樹的根節(jié)點(diǎn)的權(quán)值為其左右子樹上根節(jié)點(diǎn)的權(quán)值之和。3、然后從森林中刪除構(gòu)成新樹的那兩棵樹，同時把新樹加入森林中。重復(fù)二、三步驟知道最后剩下一棵樹為止。(3) 建立哈夫曼編碼的功能模塊該模塊運(yùn)用了遞歸的思想，將該二叉樹中每個分枝結(jié)點(diǎn)的左、右分支分別用0和1編碼，從樹根結(jié)點(diǎn)到每個葉子節(jié)點(diǎn)的路徑上所經(jīng)分支的0、1編碼序列等于該葉子節(jié)點(diǎn)的二進(jìn)制編碼(4)密文的輸出模塊。 對S中的每個字符，在info結(jié)構(gòu)體數(shù)組中尋找與之對應(yīng)的字

4、符infoj.ch,然后輸出infoj中保存的二進(jìn)制編碼infoj.a(5) 將密文轉(zhuǎn)化為原文模塊該模塊將樹根節(jié)點(diǎn)的指針賦給BTreeNode類型的指針p,對二進(jìn)制編碼數(shù)組code依次檢索，若為0，則將指針p賦值為p-left,否則賦值為p-right,然后判斷是否到達(dá)了葉子節(jié)點(diǎn)，若到達(dá)葉子節(jié)點(diǎn)，則輸出葉子節(jié)點(diǎn)里存儲的字符，重新將指針p賦值為樹根節(jié)點(diǎn)，接著進(jìn)行下去；若沒有到達(dá)，則繼續(xù)往下進(jìn)行，知道全部遍歷了code中的元素。四、算法描述：給出各模塊流程圖，不要附源代碼，可以對重點(diǎn)函數(shù)及結(jié)構(gòu)進(jìn)行說明。（1）統(tǒng)計(jì)字母種類和個數(shù)模塊k=1kvk=k+1 m=0m =ninfom.ch=skInfom

5、.num=infom.num+1m=m+1info+n.ch=sk,infon.num=1NYYYN（2）哈弗曼樹的建立模塊(k1初始指向森林中第一棵樹，k2初始指向森林中第二棵樹)i=1idata=ai.num; bi-zifu=ai.ch;bi-left=bi-right=NULL;i=i+1;i=1inj=k2i=i+1jdatadatak2=jj=j+1q=new BTreeNode;q-data=bk1-data+bk2-data;q-left=bk1; q-right=bk2;bk1=q; bk2=NULL;YNYYNYYN.(3) 建立哈夫曼編碼的功能模塊FBT!=NULLFBT

6、-left=NULL FBT-right=NULL將字符的編碼保存在infoj.a中，并輸出字符的編碼Infoj.alen=0;HuffManCoding(FBT-left,len+1);alen=1;HuffManCoding(FBT-right,len+1);YNY(4) 密文的輸出模塊。i=0ivj=0;i+jninfoj.ch=si輸出infoj.a;j+ENDNYYNY（5）將密文轉(zhuǎn)化為原文模塊（num為code數(shù)組中元素的個數(shù)）i=0ilefti=i+1p=p-righti=i+1p-left=NULL p-right=NULL輸出p-zifuP=hufftreeENDNYNY N

7、Y五、測試結(jié)果及分析：測試數(shù)據(jù)：在input.txt文本中輸入數(shù)據(jù)運(yùn)行程序得：密文為：再次將密文解密得時間復(fù)雜度：模塊一的時間復(fù)雜度為n(字符總個數(shù))*v（字符的種類）；模塊二的時間復(fù)雜度為n*n；模塊三的時間復(fù)雜度為2（n-1）*n；模塊四的時間復(fù)雜度為v* n*；模塊五的時間復(fù)雜度為num(0、1代碼的長度)調(diào)試時遇到的問題：1.當(dāng)S字符長度較短時運(yùn)行沒問題，然而較長時運(yùn)行錯誤，不能將密文再次轉(zhuǎn)化為原文。問題解決：code數(shù)組定義的長度為1000，本以為已經(jīng)足夠長了，其實(shí)不然，當(dāng)字符種類較多時候，每個字符的編碼長度會很長，因此超出了code數(shù)組的范圍而出錯，在將code數(shù)組長度改為2000時，問題便得到了解決。2.在模塊四將0、1代碼轉(zhuǎn)化為原文時，不能判斷到達(dá)的葉子節(jié)點(diǎn)處的字符，因而不能輸出。問題解決：在定義BTreeNode是增加了一個int zifu;變量，用于保存字符，從而便可輸出葉子節(jié)點(diǎn)處的字符。六、心得體會和參考資料 在編程序時，我又一次深深體會到了分塊編程的好處，分塊編程讓我始終有一個清晰的思路，把問題進(jìn)行了簡單化。經(jīng)過這次編程，我收獲了很多，在編程前，看到這個問題感到非常復(fù)雜，統(tǒng)計(jì)字符出現(xiàn)次數(shù)這個問題以前從未遇到過，似乎非常的困難。但是聯(lián)系以前學(xué)過的知識，運(yùn)用結(jié)構(gòu)體數(shù)組，便可以很好地解決問題。在解決了這個問題后，程序就完成一半了，因?yàn)橹灰{(diào)用在課堂上學(xué)的Cre