(完整word版)哈夫曼編碼譯碼器實驗評測報告(免費)

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

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

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

4、結(jié)構(gòu)體類型的hufnode作為哈夫曼編碼對照表的節(jié)點，定義HFM類實現(xiàn)對哈夫曼樹的創(chuàng)建，利用其成員函 數(shù)完成哈夫曼編碼譯碼的工作。2.定義signode類型的全局數(shù)組SN256為方便調(diào)用， 之后的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é)點的成員哈夫曼編碼數(shù)組code前后元素的對換，因為在之前的編碼過程中因為是從葉節(jié)點追溯至根節(jié) 點，存入code數(shù)組的哈夫曼編碼與

5、哈夫曼編碼的概念反向，故而要調(diào)整；4. signode * getroot( 返回哈夫曼樹的根節(jié)點指針；5. sig node * HFM:creat( 創(chuàng)建哈夫曼樹，首先用三個for循環(huán)查看forest數(shù)組，找到權(quán)值最小的兩個字符，以int型的min1,min2記錄其下標，定義signode *類 型指針pp指向新生成signode節(jié)點，用指針操作使pp指向的節(jié)點的權(quán)值為min1,min2權(quán)值之和，pp做孩子指向forestmin1,右孩子指向forestmin2，min1,min2的父指針指向pp，然后將pp存入mini的位置，min2之后的每一個節(jié) 點依次往前移一個位置，實現(xiàn)從fores

6、t數(shù)組中清除min1,min2并加入pp的操作；6. void HFM:hufcode( 哈夫曼編碼，用for循環(huán)控制查看hufNode數(shù)組，其初始化已在creat 將讀入的文章以哈夫曼編碼的形式存儲，其中inf為讀入文件的指針，outf為寫入文件的指針,首先調(diào)用rewind(inf函數(shù)將光標放置在文章開頭，防止文件未關(guān)閉導(dǎo)致的錯誤，每讀一個 字符就用for循環(huán)在hufNode數(shù)組中查找，因為hufNode數(shù)組就是保存出現(xiàn)的字 符的，故一定可以找到，然后再用fputc函數(shù)將code數(shù)組的內(nèi)容寫入文件，直至讀入文件結(jié)束；8. void HFM:inorder(signode * sig .迭代法

7、遍歷樹，遍歷到 葉節(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)的字符記錄修改其權(quán)重；數(shù)據(jù)結(jié)構(gòu)選擇與算法設(shè)計數(shù)據(jù)結(jié)構(gòu)選擇：signode：struct signode/signode節(jié)點，哈夫曼樹節(jié)點/char c。/字符/int weight。II權(quán)重/bool b。

8、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 wei ght b pare ntleftrightrrldstruct hufnodeII哈夫曼編碼對照表節(jié)點IIsig node * sig。int code100。II保存哈夫曼編碼IIint size。bool b。hufnode(sig=NULL。size=0。b=true。M?igcode100sizeclass HFMII哈夫曼類I

9、Iprivate: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創(chuàng)建哈夫曼樹IIvoid hufcode(。II編碼/void savewithhufcode(FILE * i nf,FILE * outf。II用哈弗曼編碼存儲文件/void hufdecode(FILE* ipf,FILE* o

10、pf。II解碼IIvoid inorder(signode * sig。int maxc(。II求取哈弗曼編碼最大長度II。Rootptalleafcreat(hufcode(savewithhufcode(i nf,outf設(shè)計n：rder(siggetroot(hufdecode(ipf,opfmaxc(測試結(jié)果Doc窗口： 中工昇嚴hrt P hr-T才F-4Vl- hL*ij T ?-Ieb*.g,hI.-(Trti.“hat i hAve doneHZ2uff5Dfaug；hulkgnEe出現(xiàn)字苻種央”ii10111011 iBieiiie0imiiMMHiMeMiiHii9i0iw

11、ii0tm99iiii*R1 R1 HUW1 H1111W1 HI 111 HU H11 HUI 11WK11WH HI W11B1 niilnmiwmmAiwiimwinmum 11 iHirwwi i iminniniiiHnBinnimniwiini wiivainnlUlUMftll 111i 1 illii 11101 HUlMlilUklillliMAIkMilllMiiMilHIMtieitttiOBiiiaiMOOiiiimeifiiieiiaittiMeiiiQaiiiiieitaiMitttiQtiiMiuimnIHIHSmill tailiiaiaiiHMtiutmmiu

12、HiiiaiMiaiiIU“ i dc*eHVr；b4ljnsn0eUghu*+u- -nrh lltt 1 boy Eun,PAretGlull ofink inf& woldlo6l必Jin lnstituc tens for 11 “ did notbelieve tha: to hiw Finallywe.cerwKAOMCIMily丄 r,2* beantvntof thein heva ob&ndoxd. IMbeen th followinahis wucic he uitlke7|huilllilMM：iimiie：!：11B1Oout of the oepl

13、L車百壬衣民紜和Z f電J 二古1：乍：文件讀寫部分）：3 pi-厲本丄-旦LI更 蘭它訥 蘇:T) Theli ttlrboy Bvan.Ji,vtd in institinl _ons fcr 11YEHTHhcs * been front of iheir ptients : =n( (i full of hope. He did no IbclLtvt That he was atandoneha* been thlnkirie parrT.rs would coccc t hi*. FinallyDTXiavLfallcivinF；his irvEibetalkedut jf ihe

14、 tirpharase &nd lute (tie city.OIQILLOQQIOOUIOOOIIILOIQIXLOQIIOOIJILIQ1100(JQlLLlllOlOlCaL0)0001011101110111001101100101101001111010001101110111010111ooiot) )dii( (y) )ooi( (KOiLdOiiflioictiiiMOioonLiDiioioaiioocidaoiidciLJIUI1.11._L11J_|.L.i_i.I.J1UL1|_|LUJ.i.li_i.ll_i.i.U|dj Jorjei hd ber. il.

15、iTtdi.g rartri(s tjmild aecTBhim. Finally me fal 1 nwin hi s w wi *., hr iaLLffid out of thearphaafle and into ibe ciy.總結(jié)程序分析：本次哈夫曼編碼譯碼器的課程實驗做得還算成功，不僅僅在于程序能夠正常運行，實 現(xiàn)應(yīng)有的功能，關(guān)鍵在于過程，在于小組成員的分工合作和一起糾錯排錯的過程，在完成 程序的過程中才能真正理解面向?qū)ο蠛湍K化設(shè)計的思想，我們不僅僅是說要每人分幾個132 Uh hi*. FliHhs1.lv or 返回值總為-1，于是我考 慮是否是文件沒有打開或者文件結(jié)束的緣

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

17、ILE * f1=fopen(d:pra1.txt,rFILE * f2=fopen(d:pra2.txt,wFILE * f3=fopen(d:pra4.huf,wint 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. 查看哈夫曼編碼 endlco

18、ut2. 哈夫曼解碼 endl 。cout3. 查看壓縮率 choice。while(choice=1&choice switch(choice/創(chuàng)建哈夫曼樹實例 / huffman.creat(/哈夫曼編碼，此時為逆向 / 調(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。c

19、outendl。cout1. 查看哈夫曼編碼 endl 。cout2. 哈夫曼解碼 endl 。cout3. 查看壓縮率 choice。cout* 謝謝使用 *#includeusingnamespacestd 。structsignode char c。 int weight 。bool b。 signode * parent。signode * left 。signode * right 。signode(/初始化 /c=NULL 。b=false。weight=0。parent=left=right=NULL 。signode SN256。/出現(xiàn)字符計數(shù) /sig1.c=b。sig2.c

20、=csig3.c=d。 sig4.c=e。sig6.c=g。 sig7.c=hsig8.c=i 。 sig9.c=j 。sig15.c=psig16.c=qsig17.c=rsig18.c=s。 sig19.c=t。sig20.c=usig21.c=vsig22.c=wsig23.c=xsig24.c=y。sig25.c=zsig26.c=Asig27.c=Bsig28.c=Csig29.c=Dsig30.c=E。sig31.c=Fsig32.c=Gsig33.c=H。sig34.c=I。 sig35.c=J。sig36.c=Ksig37.c=Lsig38.c=Msig39.c=Nsig40.

21、c=O 。sig41.c=Psig42.c=Qsig43.c=R 。sig44.c=S。 sig45.c=T。ig51.c=Zsig52.c=0sig53.c=1sig54.c=2sig55.c=3sig56.c=4。sig57.c=5sig58.c=6sig59.c=7sig60.c=8sig61.c=9。sig62.c=+sig63.c=-sig64.c=*sig65.c=/。 sig66.c=,。sig69.c=。 sig70.c=:。 sig71.c=sig72.c=sig74.c=sig75.c=?sig76.c= 。sig77.c=(。sig78.c=。sig79.c= 。sig8

22、0.c= 。sig81.c=。void compress( cout壓縮前:memo1*8bit 壓縮后:memo2bit/SN 數(shù)組初始化，輸入常見字符/sig10.c=ksig11.c=lsig12.c=msig13.c=nsig14.c=o。sig46.c=Usig47.c=V 。 sig48.c=Wsig49.c=X 。 sig50.c=Y 。sig82.c=sig83.c=! 。sig84.c=sig85.c=#。 sig86.c=$。sig87.c=%sig88.c=“sig89.c=& 。 sig90.c=。 sig91.c=10。/signode 節(jié)點，哈夫曼樹節(jié)點 /

23、字符 /權(quán)重 / 文章中是否出現(xiàn) /signode * forest256 。/森林數(shù)組保存出現(xiàn)的字符 /int count=0 。sig0.c=a。sig5.c=f。sig67.c=.。 sig68.c=/壓縮情況對比 /cout 壓縮率 :sig=NULL。size=O。b=true。hufnode hufNode256 。void exchange(/ 調(diào)換首尾交換哈夫曼編碼 /int temp。for(int i=O 。 hufNodei.sig!=NULL 。 i+for(int s=O,b=hufNodei.size-1 。 stemp=hufNodei.codes 。 hufNo

24、dei.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(signode * getroot(return root 。 signode* creat(。void hufcode( 。void savewithhufcode(FILE * inf,FILE * outfv

25、oid 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 函數(shù)作準備，與此函數(shù)無關(guān) while(count1int min=1OOOO 。int min1,min2 。for(int i=0 。 foresti!=NULL 。 i+/ 以 下 三 個 for 循 環(huán) 選 出 當 前 森 林 中 的

26、 最 小 兩 個 節(jié) 點 /if(foresti-weightvminmin=foresti-weight 。 min1=i。 /創(chuàng)建哈夫曼樹 /編碼/ 用哈弗曼編碼存儲文件 /min=10000for(i=0。foresti!=NULL&i 匸 mini。i+/if(foresti-weightmin=foresti-weight 。 min2=i。 /for(i=min1+1。foresti!=NULL。i+/if(foresti-weightmin=foresti-weight 。 min2=i。 / 至此找到 min1min2pp=new signode(。 /新生成節(jié)點，權(quán)值

27、為兩最小節(jié)點權(quán)值之和/pp-left=forestmin1 。pp-right=forestmin2 。forestmin2-b=true。/為 hufcode 函數(shù)作準備，與此函數(shù)無關(guān) /pp-weight=forestmin1-weight+forestmin2-weight 。forestmin1-parent=pp 。forestmin2-parent=pp 。forestmin1=pp 。/ 新生成節(jié)點加入森林 for(i=min2 。 foresti!=NULL 。 i+foresti=foresti+1 。/min2 后的節(jié)點依次前移 /count-。root=pp。return

28、 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 。/回到文件起始防止文件未關(guān)閉導(dǎo)致的錯誤/char ch=fgetc(inf 。while(!feof(inffor(int i=0 。 hufNodei.sig-c!=ch 。 i+ 。if(hufNodei.sig-c=ch for(int k=0 。 kcoutfputc(48,outf