哈夫曼編碼譯碼器實驗評測報告

1、問題解讀與解題方法問題分析：設計一個哈夫曼編碼、譯碼系統(tǒng)。對一個 ASCII 編碼的文本文件中的字符進行哈夫曼編 碼，生成編碼文件；反過來，可將編碼文件譯碼還原為一個文本文件。（1）從文件中讀入任意一篇英文短文 文件為 ASCII 編碼，擴展名為 txt）；（2）統(tǒng)計并輸出不同字符在文章中出現(xiàn)的頻率空格、換行、標點等也按字符處理）；（3）根據(jù)字符頻率構造哈夫曼樹，并給出每個字符的哈夫曼編碼；（4）將文本文件利用哈夫曼樹進行編碼，存儲成壓縮文件編碼文件后綴名 .huf ）（5）用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率；（6） 進行譯碼，將 huf 文件譯碼為 ASCI

2、I 編碼的 txt 文件，與原 txt 文件進行比較。 根據(jù)上述過程可以知道該編碼譯碼器的關鍵在于字符統(tǒng)計和哈夫曼樹的創(chuàng)建以及解 碼。哈夫曼樹的理論創(chuàng)建過程如下：一、構成初始集合對給定的n個權值W1,W2,W3,.,Wi,.,Wn構成n棵二叉樹的初始集合 F=T1,T2,T3,.,Ti,.,Tn ，其中每棵二叉樹 Ti 中只有一個權值為 Wi 的根結點， 它的左右子樹均為空。二、選取左右子樹在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹，新二叉 樹的根結點的權值為其左右子樹的根結點的權值之和。三、刪除左右子樹從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。四、

3、重復二和三兩步，重復二和三兩步，直到集合F中只有一棵二叉樹為止。因此，有如下分析：1. 我們需要一個功能函數(shù)對 ASCII 碼的初始化并需要一個數(shù)組來保存它們；2. 定義代表森林的數(shù)組，在創(chuàng)建哈夫曼樹的過程當中保存被選中的字符，即給定報文中出現(xiàn)的字符 ,模擬哈夫曼樹選取和刪除左右子樹的過程；3. 自底而上地創(chuàng)建哈夫曼樹，保存根的地址和每個葉節(jié)點的地址，即字符的地址，然后自底而上檢索，首尾對換調整為哈夫曼樹實現(xiàn)哈弗曼編碼；4. 從哈弗曼編碼文件當中讀入字符，根據(jù)當前字符為0 或者 1 的狀況訪問左子樹或者右孩子，實現(xiàn)解碼；5. 使用文件讀寫操作哈夫曼編碼和解碼結果的寫入；解題方法：結構體、數(shù)組、

4、類的定義：1. 定義結構體類型的 signode 作為哈夫曼樹的節(jié)點，定義結構體類型的 hufnode 作為哈夫曼編碼對照表的節(jié)點，定義 HFM 類實現(xiàn)對哈夫曼樹的創(chuàng)建，利用其成員函 數(shù)完成哈夫曼編碼譯碼的工作。2. 定義 signode 類型的全局數(shù)組 SN256 為方便調用， 之后的 forest256 ，hufNode256 均為全局數(shù)組） , 保存 ASCII 編碼的字符，是否在文章中出現(xiàn) bool 類型）以及出現(xiàn)次數(shù) 初始化數(shù)組 SN；2. void compress( 輸出壓縮對比情況的信息。3. void exchange( 用兩層for循環(huán)實現(xiàn) hufNodei節(jié)點的成員哈夫曼

5、編碼數(shù)組code 前后元素的對換，因為在之前的編碼過程中因為是從葉節(jié)點追溯至根節(jié) 點，存入code數(shù)組的哈夫曼編碼與哈夫曼編碼的概念反向，故而要調整；4. signode * getroot( 返回哈夫曼樹的根節(jié)點指針；5. sig node * HFM:creat( 創(chuàng)建哈夫曼樹，首先用三個 for循環(huán)查看forest數(shù)組，找到權值最小的兩個字符，以 int 型的 min1,min2 記錄其下標，定義 signode * 類 型指針 pp 指向新生成 signode 節(jié)點，用指針操作使 pp 指向的節(jié)點的權值為 min1,min2 權值之和， pp 做孩子指向 forestmin1, 右孩子

6、指向 forestmin2 ， min1,min2的父指針指向pp，然后將pp存入mini的位置，min2之后的每一個節(jié) 點依次往前移一個位置，實現(xiàn)從forest數(shù)組中清除min1,min2并加入pp的操作；6. void HFM:hufcode( 哈夫曼編碼，用 for循環(huán)控制查看 hufNode數(shù)組，其初始化已在creat 將讀入的文章以哈夫曼編碼的形式存儲，其中 inf 為讀入文件的指針， outf 為寫入文件的指針 ,首先調用 rewind(inf 函數(shù)將光標放置在文章開頭，防止文件未關閉導致的錯誤，每讀一個 字符就用 for 循環(huán)在 hufNode 數(shù)組中查找，因為 hufNode

7、數(shù)組就是保存出現(xiàn)的字 符的，故一定可以找到，然后再用fputc函數(shù)將code數(shù)組的內容寫入文件，直至讀入文件結束；8. void HFM:inorder(signode * sig 迭代法遍歷樹，遍歷到 葉節(jié)點 時執(zhí)行hufNodecount+.sig=sig 語句實現(xiàn) hufNode 數(shù)組指向文章中出現(xiàn)的字符；9. int HFM:maxc( 計數(shù)變量，記錄哈夫曼編碼最大位數(shù)；10. void HFM:hufdecode(FILE* ipf,FILE* opf 解碼，從哈夫曼編碼到字符，輸 出到屏幕和指定的文件中；11. void input(FILE * f 初始讀入文章，保存出現(xiàn)的字符記

8、錄修改其權重；數(shù)據(jù)結構選擇與算法設計數(shù)據(jù)結構選擇：signode：struct signode/signode 節(jié)點，哈夫曼樹節(jié)點 /char c。/ 字符 /int weight。II權重/bool b。II文章中是否出現(xiàn)/sig node * pare nt。sig node * left。sig node * right。sig node(II初始化/c=NULL。b=false。weight=O。parent=left=right=NULL 。C weight b pare ntleftrightrrldstruct hufnodeII哈夫曼編碼對照表節(jié)點 IIsig node * s

9、ig。int code100。II保存哈夫曼編碼IIint size。bool b。hufnode(sig=NULL 。 size=0。b=true。 。M?igcode100sizeclass HFMII 哈夫曼類 IIprivate:sig node * root。II 哈夫曼樹根 IIsig node * pt。II編碼時做哨兵指針I(yè)Iint alleaf。public:HFM(int allroot=pt=NULL。alleaf=all。IIall 是森林中樹的個數(shù) IIHFM(sig node * getroot(return root 。 sig node * creat(。II

10、創(chuàng)建哈夫曼樹 IIvoid hufcode(。II 編碼 /void savewithhufcode(FILE * i nf,FILE * outf。 II 用哈弗曼編碼存儲文件/void hufdecode(FILE* ipf,FILE* opf 。II 解碼 IIvoid inorder(signode * sig 。int maxc(。II求取哈弗曼編碼最大長度II。Rootptalleafcreat(hufcode(savewithhufcode(i nf,outf設計n：rder(siggetroot(hufdecode(ipf,opfmaxc(測試結果Doc 窗口： 中工昇嚴 hr

11、t P hr-T 才F -4Vl- hL*ij T ?-Ieb*.g,hI.-(Trti.“hat i hAve doneHZ2uff5Dfaug；hulkgnEe出現(xiàn)字苻種央”ii10111011 iBieiiie0imiiMMHiMeMiiHii9i0iwii0tm99iiii*R1 R1 HUW1 H1111W1 HI 111 HU H11 HUI 11WK11WH HI W11B1 niilnmiwmmAiwiimwinmum 11 iHirwwi i iminniniiiHnBinnimniwiini wiivainnlUlUMftll 111i 1 illii 11101 HUlM

12、lilUklillliMAIkMilllMiiMilHIlo6l必 JMtieitttiOBiiiaiMOOiiiimeifiiieiiaittiMeiiiQaiiiiieitaiMitttiQtiiMiuimn ihihs mill tai liiaiaiiHMtiutmmiuHiiiaiMiaii iu“ i dc*eHVr；b4ljnsn0eUghu*+u- -nin lnstituc tens for 11 “ did not believe tha: to hiw Finally we. cerw KaOMCI Mily丄r, 2* bean tvnt of thein he va

13、ob&ndoxd. im been th followina his wucic he uitlke7|huilllilMM：iimiie：!：11B1Orh lltt 1 boy Eun,PAretGlull ofink inf& woldout of the oepl L 車百壬衣民紜和 Zf電J二古1：乍：132 Uh hi*. FliHhs1.lv or a lnta TJk city.L h&5 EWheii tlruAt In wwiImf lwir*H 陽 Ie hut ic i.“云.山-JH蠱i 臣戸匸*好眄 薔罟雷_ p n B - ;ZZ4lbIt FEjjf F虬対皚口

14、文件讀寫 部分）：3 pi -厲本丄-旦 LI更 蘭它訥 蘇:T) The li ttlr boy Bvan. Ji,vtd in institinl _ons fcr 11 yehth hcs * been front of iheir ptients : =n(i full of hope. He did no I bclLtvt That he was atandone ha* been thlnkirie parrT.rs would coccc t hi*. Finally dtx iavL fallcivinF； his irvEibe talked ut jf ihe tirph

15、arase &nd lute (tie city.OIQILLOQQIOOUIOOOIIILOIQIXLOQIIOOIJILIQ 1100 (JQlLLlllOlOlCaL 0)0001011101110111001101100101101001111010001101110111010111 ooiot)dii(y)ooi(KOi LdOiiflioictiiiMOi oonLiDiioioaiioocidaoiidci LJIUI 1.11._L11J_|.L.i_i. I .J1UL1 |_| LUJ.i.l i_i.ll_i.i. U |dj Jorjei hd ber. il.iTt

16、di.g rartri(s tjmild aec tb him. Finally me fal 1 nwin hi s w wi *., hr iaLLffid out of the arphaafle and into ibe ciy.總結程序分析：本次哈夫曼編碼譯碼器的課程實驗做得還算成功，不僅僅在于程序能夠正常運行，實 現(xiàn)應有的功能，關鍵在于過程，在于小組成員的分工合作和一起糾錯排錯的過程，在完成 程序的過程中才能真正理解面向對象和模塊化設計的思想，我們不僅僅是說要每人分幾個函數(shù)，關鍵在于這些函數(shù)代表的是一個個功能模塊，任何一個模塊出現(xiàn)問題或者模塊之間 的銜接出現(xiàn)問題都將導致程序運行的失

17、敗。哈夫曼編碼譯碼器課程實驗我主要負責完成編碼譯碼器數(shù)據(jù)結構和功能模塊框架的 設計，結構體和類的定義，以及 creat 函數(shù)， hufcode 函數(shù)， savewithhufcode 函數(shù)的實現(xiàn)。 在初始設計的時候，我體會到書寫流程圖的重要性，只有又一個清晰的設計思路才能事半 功倍，分工明確，避免無效勞動或者在錯誤的編程方向上走彎路，也讓大家明白自己在程 序設計中的位置和職責。初始的創(chuàng)建是哈夫曼編碼譯碼系統(tǒng)成功的關鍵，我在創(chuàng)建的過程當中多次使用樹的 先根，配合中根遍歷操作，輸出接點字符或者權重信息，作為檢驗，對驗證和糾錯起到了 非常大的作用。在適當?shù)牡胤秸{用它們，運行時可以看到驗證編寫程序的正

18、確性； 通過本次實驗，提高了自已調試程序的能力。充分體會到了在程序執(zhí)行時的提示性輸 出的重要性。編寫大一點的程序，應先寫出算法，再寫程序，一段一段調試；對于沒有實 現(xiàn)的操作用空操作代替，這樣容易找出錯誤所在。最忌諱將所有代碼寫完后再調試，這樣 若程序有錯誤，太難找。需要特別強調的是：1 感覺文件操作自己并不是很熟練，盡管在向顯示器輸出的時候并沒有什么錯誤但是讀寫文件的時候就沒那么順利了，比如說當編寫 savewithhufcode 函數(shù)時讀文 件，卻總不執(zhí)行，后來通過斷點測試發(fā)現(xiàn)每次 fgetc( 返回值總為 -1 ，于是我考 慮是否是文件沒有打開或者文件結束的緣故，后來想通了是之前打開的文件

19、光標 讀操作結束后仍在結尾故每次總返回 -1 ，故調用 rewind 函數(shù)將光標位置移動到文 章開始。2. 用哈夫曼編碼存儲文件的時候還應注意數(shù)字0,1與字符0,1 的不同，不應直接在fputc(函數(shù)中直接寫入0,1那么將會是寫入的文章中什么都沒有，因為0在ASCII碼中代表 NULL。3. 該程序函數(shù)清晰功能明確，程序具有通用性，對于不同的輸入文章都可進行處 理，因為采用哈夫曼編碼對照表，使得查看哈夫曼編碼是效率較高無需每次遍歷 哈夫曼樹。.cpp#include#include#include#include#includeHh1.h using namespace std。FILE *

20、f1=fopen(d:pra1.txt,rFILE * f2=fopen(d:pra2.txt,wFILE * f3=fopen(d:pra4.huf,w int main(init(SN/初始化字符數(shù)據(jù)庫 /input(f1/讀入初始文件的字符 /for(int i=0 。 foresti!=NULLi+coutc:weightendl/ 輸 出 字 符 及 出 現(xiàn) 次 數(shù) / cout 出 現(xiàn) 字 符 種 類count 。count=0。 huffman.hufcode(。exchange(。 /用哈夫曼編碼存儲原文件 / coutendl。cout1. 查看哈夫曼編碼 endl cout

21、2. 哈夫曼解碼 endl 。 cout3. 查看壓縮率 choice。 while(choice=1&choice switch(choice/創(chuàng)建哈夫曼樹實例 / huffman.creat(/哈夫曼編碼，此時為逆向 / 調整首尾對調哈夫曼編碼 /case 1:for(i=0。hufNodei.sig!=NULL。i+cout字符c的哈夫曼編碼:。輸出哈夫曼編碼/for(int j=0 。 jcouthufNodei.codej 。coutendl。coutvv最大歹U數(shù): 。 f2=fopen(d:pra2.txt,r 。huffman.hufdecode(f2,f3 。 cout。co

22、utendl。cout1. 查看哈夫曼編碼 endl 。cout2. 哈夫曼解碼 endl 。 cout3. 查看壓縮率 choice。cout* 謝謝使用 */signode 節(jié)點，哈夫曼樹節(jié)點 /字符 /權重 / 文章中是否出現(xiàn) /#include using namespace std。 struct signode char c。 int weight 。 bool b。 signode * parent。signode * left 。signode * right 。signode(/初始化 /c=NULL 。b=false。weight=0。parent=left=right=N

23、ULL 。signode SN256。signode * forest256 。/森林數(shù)組保存出現(xiàn)的字符 /int count=0 。/出現(xiàn)字符計數(shù) /float memo1=0,memo2=0/全局變量記錄讀入字符數(shù)和編碼的0 1 數(shù) /void init(signode * sig/SN 數(shù)組初始化，輸入常見字符/sig0.c=a。sig1.c=b。sig2.c=c sig3.c=d。 sig4.c=e。sig5.c=f 。sig6.c=g。 sig7.c=h sig8.c=i 。 sig9.c=j 。sig10.c=ksig11.c=lsig12.c=msig13.c=nsig14.c=

24、o。sig15.c=psig16.c=q sig17.c=r sig18.c=s。 sig19.c=t。sig20.c=usig21.c=v sig22.c=w sig23.c=x sig24.c=y。sig25.c=zsig26.c=Asig27.c=B sig28.c=C sig29.c=D sig30.c=E。sig31.c=Fsig32.c=Gsig33.c=H 。sig34.c=I。 sig35.c=J。sig36.c=Ksig37.c=L sig38.c=Msig39.c=Nsig40.c=O 。sig41.c=Psig42.c=Qsig43.c=R 。sig44.c=S。sig4

25、5.c=T。sig46.c=Usig47.c=V。 sig48.c=Wsig49.c=X。 sig50.c=Y 。sig51.c=Zsig52.c=0sig53.c=1 sig54.c=2 sig55.c=3 sig56.c=4。sig57.c=5sig58.c=6 sig59.c=7 sig60.c=8 sig61.c=9。sig62.c=+sig63.c=- sig64.c=* sig65.c=/。 sig66.c=,。sig67.c=.。 sig68.c=sig69.c=。 sig70.c=:。 sig71.c=sig72.c= sig74.c= sig75.c=? sig76.c= 。

26、sig77.c=(。sig78.c= 。sig79.c= 。sig80.c= 。sig81.c=。sig82.c=sig83.c=! 。sig84.c=sig85.c=#。 sig86.c=$。sig87.c=%sig88.c=“sig89.c=&。 sig90.c=。 sig91.c=10。/壓縮情況對比 /void compress( cout壓縮前:memo1*8bit 壓縮后:memo2bitendlcout 壓縮率 :sig=NULL。size=O。b=true。hufnode hufNode256 。void exchange(/ 調換首尾交換哈夫曼編碼 /int temp。for

27、(int i=O 。 hufNodei.sig!=NULL 。 i+for(int s=O,b=hufNodei.size-1 。 stemp=hufNodei.codes 。 hufNodei.codes=hufNodei.codeb 。hufNodei.codeb=tempclass HFM/ 哈夫曼類 /private:signode * root。/哈夫曼樹根 /signode * pt。/編碼時做哨兵指針 /int alleaf。public:HFM(int allroot=pt=NULL 。 alleaf=all 。 /all 是森林中樹的個數(shù) /HFM(/創(chuàng)建哈夫曼樹 /編碼/s

28、ignode * getroot(return root 。 signode * creat(。/ 用哈弗曼編碼存儲文件 /void hufcode( 。void savewithhufcode(FILE * inf,FILE * outfvoid hufdecode(FILE* ipf,FILE* opf 。/解碼/void inorder(signode * sig 。int maxc( 。/求取哈夫碼曼最大長度 / signode * HFM:creat(signode * pp=NULL 。for(int i=0。ivcount。i+foresti-b=false。/為 hufcode

29、函數(shù)作準備，與此函數(shù)無關 while(count1int min=1OOOO 。int min1,min2 。for(int i=0 。 foresti!=NULL 。 i+/ 以 下 三 個 for 循 環(huán) 選 出 當 前 森 林 中 的 最 小 兩 個 節(jié) 點 /if(foresti-weightvminmin=foresti-weight 。 min1=i。 /min=10000for(i=0。foresti!=NULL&i匸mini。i+/if(foresti-weightmin=foresti-weight 。 min2=i。 /for(i=min1+1。foresti!=NULL。

30、i+/if(foresti-weightmin=foresti-weight 。 min2=i。 / 至此找到 min1min2pp=new signode(。/新生成節(jié)點，權值為兩最小節(jié)點權值之和/pp-left=forestmin1 。pp-right=forestmin2 。forestmin2-b=true。/為hufcode函數(shù)作準備，與此函數(shù)無關 /pp-weight=forestmin1-weight+forestmin2-weight 。forestmin1-parent=pp 。forestmin2-parent=pp 。forestmin1=pp 。/ 新生成節(jié)點加入森林

31、for(i=min2 。 foresti!=NULL 。 i+foresti=foresti+1 。/min2 后的節(jié)點依次前移 /count-。root=pp。return pp。void HFM:hufcode(/ 哈夫曼編碼，保存在 hufNode 節(jié)點的數(shù)組當中 /inorder(root 。for(int i=0 。 hufNodei.sig!=NULL 。 i+signode * gud=hufNodei.sig 。while(gud-parent!=NULLif(gud-parent-left=gudhufNodei.codehufNodei.size+=0 。else if(gud-parent-right=gudhufNodei.codehufNodei.size+=1 。gud=gud-parent。void HFM:savewithhufcode(FILE * inf,FILE * outf/ 用哈弗曼編碼存儲文件 /rewind(inf 。/回到文件起始防止文件未關閉導致的錯誤/char ch=fgetc(inf