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

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

2、碼的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ù)組、類的定義：1. 定義結構體類型的s

4、ignode 作為哈夫曼樹的節(jié)點，定義結構體類型的hufnode 作為哈夫曼編碼對照表的節(jié)點，定義HFM類實現(xiàn)對哈夫曼樹的創(chuàng)建，利用其成員函數(shù)完成哈夫曼編碼譯碼的工作。2. 定義signode 類型的全局數(shù)組SN256（為方便調用，之后的forest256，hufNode256均為全局數(shù)組）, 保存ASCII編碼的字符，是否在文章中出現(xiàn)（bool類型）以及出現(xiàn)次數(shù)（int類型，權重），左右孩子節(jié)點位置，父節(jié)點位置信息；3. 為節(jié)省存儲空間，定義signode * 類型的全局數(shù)組forest256, 模擬森林，在創(chuàng)建哈夫曼樹的過程中保存出現(xiàn)字符的指針，模擬哈夫曼樹選取和刪除左右子樹的過程；4.

5、定義hufnode 類型的全局數(shù)組hufNode256，在編碼時最為哈夫曼編碼對照表的節(jié)點，char 型c保存字符,int code100保存其哈夫曼編碼；5. 定義HFM類，主要保存哈夫曼樹的根節(jié)點指針，但其豐富的功能函數(shù)將實現(xiàn)哈夫曼編碼譯碼的工作及其他功能；函數(shù)介紹：1. void init(signode * sig) 初始化數(shù)組SN；2. void compress()輸出壓縮對比情況的信息;3. void exchange()用兩層for循環(huán)實現(xiàn)hufNodei節(jié)點的成員哈夫曼編碼數(shù)組code前后元素的對換，因為在之前的編碼過程中由于是從葉節(jié)點追溯至根節(jié)點，存入code數(shù)組的哈夫曼編

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

7、t數(shù)組中清除min1,min2并加入pp的操作；6. void HFM:hufcode()哈夫曼編碼，用for循環(huán)控制查看hufNode 數(shù)組，其初始化已在creat（）的開始完成，對每一個字符實現(xiàn)編碼，用while循環(huán)從葉節(jié)點開始，如果該節(jié)點是其父節(jié)點的左孩子就將codehufNodei.size+賦值0，否則賦為1，直至當前節(jié)點的父節(jié)點為空，while循環(huán)結束；7. void HFM:savewithhufcode(FILE * inf,FILE * outf)將讀入的文章以哈夫曼編碼的形式存儲，其中inf為讀入文件的指針，outf為寫入文件的指針,首先調用rewind(inf)函數(shù)將光標

8、放置在文章開頭，防止文件未關閉導致的錯誤，每讀一個字符就用for循環(huán)在hufNode 數(shù)組中查找，因為hufNode 數(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)解碼，從哈夫曼編碼到字符

9、，輸出到屏幕和指定的文件中；11. void input(FILE * f)初始讀入文章，保存出現(xiàn)的字符記錄修改其權重；數(shù)據(jù)結構選擇與算法設計 數(shù)據(jù)結構選擇：signode： struct signode /signode節(jié)點，哈夫曼樹節(jié)點/ char c; /字符/ int weight; /權重/ bool b; /文章中是否出現(xiàn)/ signode * parent; signode * left; signode * right; signode() /初始化/ c=NULL; b=false; weight=0; parent=left=right=NULL; ;C weight b

10、parent left right hufnode: struct hufnode /哈夫曼編碼對照表節(jié)點/ signode * sig; int code100; /保存哈夫曼編碼/ int size;bool b; hufnode()sig=NULL;size=0;b=true;Sig code100 size;HFM:class HFM /哈夫曼類/ private: signode * root; /哈夫曼樹根/ signode * pt; /編碼時做哨兵指針/ int alleaf; public: HFM(int all)root=pt=NULL;alleaf=all; /all是

11、森林中樹的個數(shù)/ HFM() signode * getroot()return root; signode * creat(); /創(chuàng)建哈夫曼樹/ void hufcode(); /編碼/ void savewithhufcode(FILE * inf,FILE * outf); /用哈弗曼編碼存儲文件/ void hufdecode(FILE* ipf,FILE* opf); /解碼/ void inorder(signode * sig); int maxc(); /求取哈弗曼編碼最大長度/;Root pt alleafcreat() hufcode() savewithhufcode(

12、inf,outf) inorder(sig) getroot()hufdecode(ipf,opf) maxc()算法設計：init(SN)初始化SN數(shù)組input（f1）從f1讀入字符 輸出字符信息及權重 huffman.creat（）創(chuàng)建哈夫曼樹 huffman.hufcode(); exchange(); huffman.savewithhufcode(f1,f2);哈夫曼編碼并用該編碼保存 文件輸入數(shù)字選擇compress（）1. 查看哈夫曼編碼3.查看壓縮率2.哈夫曼解碼huffman.hufdecode(f2,f3)輸入數(shù)字選擇測試結果Doc窗口： 文件讀寫（部分）： 總結程序分析

13、： 本次哈夫曼編碼譯碼器的課程實驗做得還算成功，不僅僅在于程序能夠正常運行，實現(xiàn)應有的功能，關鍵在于過程，在于小組成員的分工合作和一起糾錯排錯的過程，在完成程序的過程中才能真正理解面向對象和模塊化設計的思想，我們不僅僅是說要每人分幾個函數(shù)，關鍵在于這些函數(shù)代表的是一個個功能模塊，任何一個模塊出現(xiàn)問題或者模塊之間的銜接出現(xiàn)問題都將導致程序運行的失敗。哈夫曼編碼譯碼器課程實驗我主要負責完成編碼譯碼器數(shù)據(jù)結構和功能模塊框架的設計，結構體和類的定義，以及creat函數(shù)，hufcode函數(shù)，savewithhufcode函數(shù)的實現(xiàn)。在初始設計的時候，我體會到書寫流程圖的重要性，只有又一個清晰的設計思路才

14、能事半功倍，分工明確，避免無效勞動或者在錯誤的編程方向上走彎路，也讓大家明白自己在程序設計中的位置和職責。初始的創(chuàng)建是哈夫曼編碼譯碼系統(tǒng)成功的關鍵，我在創(chuàng)建的過程當中多次使用樹的先根，配合中根遍歷操作，輸出接點字符或者權重信息，作為檢驗，對驗證和糾錯起到了非常大的作用。在適當?shù)牡胤秸{用它們，運行時可以看到驗證編寫程序的正確性； 通過本次實驗，提高了自已調試程序的能力。充分體會到了在程序執(zhí)行時的提示性輸出的重要性。編寫大一點的程序，應先寫出算法，再寫程序，一段一段調試；對于沒有實現(xiàn)的操作用空操作代替，這樣容易找出錯誤所在。最忌諱將所有代碼寫完后再調試，這樣若程序有錯誤，太難找 。需要特別強調的是

15、：1 感覺文件操作自己并不是很熟練，盡管在向顯示器輸出的時候并沒有什么錯誤但是讀寫文件的時候就沒那么順利了，比如說當編寫savewithhufcode函數(shù)時讀文件，卻總不執(zhí)行，后來通過斷點測試發(fā)現(xiàn)每次fgetc()返回值總為-1，于是我考慮是否是文件沒有打開或者文件結束的緣故，后來想通了是之前打開的文件光標讀操作結束后仍在結尾故每次總返回-1，故調用rewind函數(shù)將光標位置移動到文章開始。2. 用哈夫曼編碼存儲文件的時候還應注意數(shù)字0,1與字符0,1的不同，不應直接在fputc()函數(shù)中直接寫入0,1那么將會是寫入的文章中什么都沒有，因為0在ASCII碼中代表NULL。3.該程序函數(shù)清晰功能

16、明確，程序具有通用性，對于不同的輸入文章都可進行處理，由于采用哈夫曼編碼對照表，使得查看哈夫曼編碼是效率較高無需每次遍歷哈夫曼樹。程序清單.cpp#include<iostream>#include<stdio.h>#include<stdlib.h>#include<string>#include"Hh1.h"using namespace std;FILE * f1=fopen("d:pra1.txt","r");FILE * f2=fopen("d:pra2.txt&qu

17、ot;,"w");FILE * f3=fopen("d:pra4.huf","w");int main()init(SN); /初始化字符數(shù)據(jù)庫/input(f1); /讀入初始文件的字符/for(int i=0;foresti!=NULL;i+)cout<<foresti->c<<":"<<foresti->weight<<endl; /輸出字符及出現(xiàn)次數(shù)/ cout<<"出現(xiàn)字符種類 "<<count<

18、<endl; /輸出字符種類/ HFM huffman(count); /創(chuàng)建哈夫曼樹實例/ huffman.creat(); /創(chuàng)建哈夫曼樹/ count=0;huffman.hufcode(); /哈夫曼編碼，此時為逆向/ exchange(); /調整首尾對調哈夫曼編碼/ huffman.savewithhufcode(f1,f2); /用哈夫曼編碼存儲原文件/cout<<endl;cout<<"1.查看哈夫曼編碼"<<endl; cout<<"2.哈夫曼解碼"<<endl; cou

19、t<<"3.查看壓縮率"<<endl;int choice;cin>>choice;while(choice>=1&&choice<=3) switch(choice)case 1:for(i=0;hufNodei.sig!=NULL;i+)cout<<"字符"<<hufNodei.sig->c<<"的哈夫曼編碼:" /輸出哈夫曼編碼/for(int j=0;j<hufNodei.size;j+)cout<<hu

20、fNodei.codej;cout<<endl; cout<<"最大列數(shù):"<<huffman.maxc()<<endl; break;case 2:fclose(f2);f2=fopen("d:pra2.txt","r"); huffman.hufdecode(f2,f3); /哈夫曼解碼/cout<<endl;break;case 3:compress(); /查看壓縮情況/cout<<endl; cout<<"1.查看哈夫曼編碼&quo

21、t;<<endl; cout<<"2.哈夫曼解碼"<<endl;cout<<"3.查看壓縮率"<<endl;cin>>choice; cout<<"*使用*"<<endl; /退出操作/ return 0;.h#include<iostream>using namespace std;struct signode /signode節(jié)點，哈夫曼樹節(jié)點/char c; /字符/int weight; /權重/bool b; /文章中

22、是否出現(xiàn)/signode * parent;signode * left;signode * right;signode() /初始化/c=NULL;b=false;weight=0;parent=left=right=NULL;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=&

23、#39;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='k'sig11.c='l'sig12.c='m'sig13.c='n'sig14.c='o'sig15.c='p'sig16.c='q'sig17.c='

24、r'sig18.c='s'sig19.c='t'sig20.c='u'sig21.c='v'sig22.c='w'sig23.c='x'sig24.c='y'sig25.c='z' sig26.c='A'sig27.c='B'sig28.c='C'sig29.c='D'sig30.c='E'sig31.c='F'sig32.c='G'sig33.c=

25、'H'sig34.c='I'sig35.c='J'sig36.c='K'sig37.c='L'sig38.c='M'sig39.c='N'sig40.c='O'sig41.c='P'sig42.c='Q'sig43.c='R'sig44.c='S'sig45.c='T'sig46.c='U'sig47.c='V'sig48.c='W'sig4

26、9.c='X'sig50.c='Y'sig51.c='Z' sig52.c='0'sig53.c='1'sig54.c='2'sig55.c='3'sig56.c='4'sig57.c='5'sig58.c='6'sig59.c='7'sig60.c='8'sig61.c='9'sig62.c='+'sig63.c='-'sig64.c='*'

27、;sig65.c='/'sig66.c=',' sig67.c='.'sig68.c=''' sig69.c='"'sig70.c=':'sig71.c=''sig72.c='<'sig73.c='>'sig74.c='='sig75.c='?'sig76.c=' 'sig77.c='('sig78.c=')'sig79.c=''

28、;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*8<<"

29、;bit 壓縮后:"<<memo2<<"bit"<<endl;cout<<"壓縮率:"<<memo2/(memo1*8)<<endl;struct hufnode /哈夫曼編碼對照表節(jié)點/ signode * sig;int code100; /保存哈夫曼編碼/ int size;bool b; hufnode()sig=NULL;size=0;b=true;hufnode hufNode256;void exchange() /調換首尾交換哈夫曼編碼/ int temp;

30、 for(int i=0;hufNodei.sig!=NULL;i+)for(int s=0,b=hufNodei.size-1;s<=b;s+,b-)temp=hufNodei.codes;hufNodei.codes=hufNodei.codeb;hufNodei.codeb=temp class HFM /哈夫曼類/ private:signode * root; /哈夫曼樹根/signode * pt; /編碼時做哨兵指針/ int alleaf; public:HFM(int all)root=pt=NULL;alleaf=all;/all是森林中樹的個數(shù)/HFM()signo

31、de * getroot()return root;signode * creat(); /創(chuàng)建哈夫曼樹/ void hufcode(); /編碼/void savewithhufcode(FILE * inf,FILE * outf); /用哈弗曼編碼存儲文件/ void hufdecode(FILE* ipf,FILE* opf); /解碼/ void inorder(signode * sig); int maxc(); /求取哈夫碼曼最大長度/;signode * HFM:creat()signode * pp=NULL; for(int i=0;i<count;i+)fores

32、ti->b=false; /為hufcode函數(shù)作準備，與此函數(shù)無關/ while(count>1)int min=10000;int min1,min2;for(int i=0;foresti!=NULL;i+) /以下三個for循環(huán)選出當前森林中的最小兩個節(jié)點/ if(foresti->weight<min)min=foresti->weight;min1=i; / /min=10000; / for(i=0;foresti!=NULL&&i!=min1;i+) /if(foresti->weight<min)min=foresti

33、->weight;min2=i; / for(i=min1+1;foresti!=NULL;i+) /if(foresti->weight<min)min=foresti->weight;min2=i; / /至此找到min1 min2pp=new signode(); /新生成節(jié)點，權值為兩最小節(jié)點權值之和/pp->left=forestmin1;pp->right=forestmin2;forestmin2->b=true; /為hufcode函數(shù)作準備，與此函數(shù)無關/pp->weight=forestmin1->weight+fore

34、stmin2->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 pp;void HFM:hufcode() /哈夫曼編碼，保存在hufNode節(jié)點的數(shù)組當中/inorder(root);for(int i=0;hufNodei.sig!=NULL;i+)signode * gud=hufNodei.sig;w

35、hile(gud->parent!=NULL)if(gud->parent->left=gud)hufNodei.codehufNodei.size+=0;else if(gud->parent->right=gud)hufNodei.codehufNodei.size+=1;gud=gud->parent;void HFM:savewithhufcode(FILE * inf,FILE * outf) /用哈弗曼編碼存儲文件/rewind(inf); /回到文件起始防止文件未關閉導致的錯誤/char ch=fgetc(inf);while(!feof(inf)for(int i=0;hufNodei.sig->c!=ch;i+);if(hufNodei.sig->c=ch) fo