哈夫曼編碼譯碼器實(shí)驗(yàn)評測報(bào)告

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

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

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

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

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

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

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

8、錄修改其權(quán)重；數(shù)據(jù)結(jié)構(gòu)選擇與算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)選擇：signode：struct signode/signode 節(jié)點(diǎn)，哈夫曼樹節(jié)點(diǎn) /char c。/ 字符 /int weight。II權(quán)重/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é)點(diǎn) 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編碼時(shí)做哨兵指針I(yè)Iint alleaf。public:HFM(int allroot=pt=NULL。alleaf=all。IIall 是森林中樹的個(gè)數(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 用哈弗曼編碼存儲(chǔ)文件/void hufdecode(FILE* ipf,FILE* opf 。II 解碼 IIvoid inorder(signode * sig 。int maxc(。II求取哈弗曼編碼最大長度II。Rootptalleafcreat(hufcode(savewithhufcode(i nf,outf設(shè)計(jì)n：rder(siggetroot(hufdecode(ipf,opfmaxc(測試結(jié)果Doc 窗口： 中工昇嚴(yán) 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.總結(jié)程序分析：本次哈夫曼編碼譯碼器的課程實(shí)驗(yàn)做得還算成功，不僅僅在于程序能夠正常運(yùn)行，實(shí) 現(xiàn)應(yīng)有的功能，關(guān)鍵在于過程，在于小組成員的分工合作和一起糾錯(cuò)排錯(cuò)的過程，在完成 程序的過程中才能真正理解面向?qū)ο蠛湍K化設(shè)計(jì)的思想，我們不僅僅是說要每人分幾個(gè)函數(shù)，關(guān)鍵在于這些函數(shù)代表的是一個(gè)個(gè)功能模塊，任何一個(gè)模塊出現(xiàn)問題或者模塊之間 的銜接出現(xiàn)問題都將導(dǎo)致程序運(yùn)行的失

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

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

19、光標(biāo) 讀操作結(jié)束后仍在結(jié)尾故每次總返回 -1 ，故調(diào)用 rewind 函數(shù)將光標(biāo)位置移動(dòng)到文 章開始。2. 用哈夫曼編碼存儲(chǔ)文件的時(shí)候還應(yīng)注意數(shù)字0,1與字符0,1 的不同，不應(yīng)直接在fputc(函數(shù)中直接寫入0,1那么將會(huì)是寫入的文章中什么都沒有，因?yàn)?在ASCII碼中代表 NULL。3. 該程序函數(shù)清晰功能明確，程序具有通用性，對于不同的輸入文章都可進(jìn)行處 理，因?yàn)椴捎霉蚵幋a對照表，使得查看哈夫曼編碼是效率較高無需每次遍歷 哈夫曼樹。.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(。 /用哈夫曼編碼存儲(chǔ)原文件 / coutendl。cout1. 查看哈夫曼編碼 endl cout

21、2. 哈夫曼解碼 endl 。 cout3. 查看壓縮率 choice。 while(choice=1&choice switch(choice/創(chuàng)建哈夫曼樹實(shí)例 / huffman.creat(/哈夫曼編碼，此時(shí)為逆向 / 調(diào)整首尾對調(diào)哈夫曼編碼 /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é)點(diǎn)，哈夫曼樹節(jié)點(diǎn) /字符 /權(quán)重 / 文章中是否出現(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 。/森林?jǐn)?shù)組保存出現(xiàn)的字符 /int count=0 。/出現(xiàn)字符計(jì)數(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(/ 調(diào)換首尾交換哈夫曼編碼 /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。/編碼時(shí)做哨兵指針 /int alleaf。public:HFM(int allroot=pt=NULL 。 alleaf=all 。 /all 是森林中樹的個(gè)數(shù) /HFM(/創(chuàng)建哈夫曼樹 /編碼/s

28、ignode * getroot(return root 。 signode * creat(。/ 用哈弗曼編碼存儲(chǔ)文件 /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ù)作準(zhǔn)備，與此函數(shù)無關(guān) while(count1int min=1OOOO 。int min1,min2 。for(int i=0 。 foresti!=NULL 。 i+/ 以 下 三 個(gè) for 循 環(huán) 選 出 當(dāng) 前 森 林 中 的 最 小 兩 個(gè) 節(jié) 點(diǎn) /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é)點(diǎn)，權(quán)值為兩最小節(jié)點(diǎn)權(quán)值之和/pp-left=forestmin1 。pp-right=forestmin2 。forestmin2-b=true。/為hufcode函數(shù)作準(zhǔn)備，與此函數(shù)無關(guān) /pp-weight=forestmin1-weight+forestmin2-weight 。forestmin1-parent=pp 。forestmin2-parent=pp 。forestmin1=pp 。/ 新生成節(jié)點(diǎn)加入森林

31、for(i=min2 。 foresti!=NULL 。 i+foresti=foresti+1 。/min2 后的節(jié)點(diǎn)依次前移 /count-。root=pp。return pp。void HFM:hufcode(/ 哈夫曼編碼，保存在 hufNode 節(jié)點(diǎn)的數(shù)組當(dāng)中 /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/ 用哈弗曼編碼存儲(chǔ)文件 /rewind(inf 。/回到文件起始防止文件未關(guān)閉導(dǎo)致的錯(cuò)誤/char ch=fgetc(inf