數(shù)據(jù)結構哈夫曼編碼實驗報告

1、數(shù)據(jù)結構實驗報告實驗五簡單哈夫曼編/譯碼的設計與實現(xiàn)本實驗的目的是通過對簡單哈夫曼編/譯碼系統(tǒng)的設計與實現(xiàn)來熟練掌握樹型結構在實際問題中的應用。此實驗可以作為綜合實驗，階段性實驗時可以選擇其中的幾個功能來設計和實現(xiàn)。一、【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼，此實驗即設計這樣的一個簡單編/碼系統(tǒng)。系統(tǒng)應該具有如下的幾個功能：1、接收原始數(shù)據(jù)。從終端讀入字符集大小n以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件nodedata.dat中。2、編碼。利用已建

2、好的哈夫曼樹（如不在內(nèi)存，則從文件nodedata.dat中讀入），對文件中的正文進行編碼，然后將結果存入文件code.dat中。3、譯碼。利用已建好的哈夫曼樹將文件code.dat中的代碼進行譯碼，結果存入文件textfile.dat中。4、打印編碼規(guī)則。即字符與編碼的一一對應關系。二、【數(shù)據(jù)結構設計】1、構造哈夫曼樹時使用靜態(tài)鏈表作為哈夫曼樹的存儲。在構造哈夫曼樹時，設計一個結構體數(shù)組HuffNode保存哈夫曼樹中各結點的信息，根據(jù)二叉樹的性質可知，具有n個葉子結點的哈夫曼樹共有2n-1個結點，所以數(shù)組HuffNode的大小設置為2n-1，描述結點的數(shù)據(jù)類型為：typedefstructi

3、ntweight;/結點權值intparent;intlchild;intrchild;charinf;HNodeType;2、求哈夫曼編碼時使用一維結構數(shù)組HuffCode作為哈夫曼編碼信息的存儲。求哈夫曼編碼，實質上就是在已建立的哈夫曼樹中，從葉子結點開始，沿結點的雙親鏈域回退到根結點，沒回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結點到相應葉子結點所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼位所求編碼的高位碼，所以設計如下數(shù)據(jù)類型：#defineMAXBIT10typedefstructi

4、ntbitMAXBIT；intstart；HcodeType；3、文件nodedata.dat、code.dat和textfile.dat。三、【功能(函數(shù))設計】1、初始化功能模塊。此功能模塊的功能為從鍵盤接收字符集大小n以及n個字符和n個權值。2、建立哈夫曼樹的功能模塊。此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構造哈夫曼樹的算法構造哈夫曼樹，即將HuffNode數(shù)組中的各個位置的各個域都添上相關的值，并將這個結構體數(shù)組存于文件hfmtree.dat中。3、建立哈夫曼編碼的功能模塊。此模塊功能為從文件nodedata.dat中讀入相關的字符信息進行哈夫曼編碼，然后將結果存入code.dat

5、中，同時將字符與0、1代碼串的一一對應關系打印到屏幕上。4、譯碼的功能模塊。此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時將翻譯的結果在屏幕上打印輸出。四、【編碼實現(xiàn)】#include#include#include#include#defineMaxBit10#defineMaxvalue100/應該大于權重之和#defineMaxleaf100#defineMaxnodeMaxleaf*2-1typedefstructintweight;intparent;intlchild;intrchild

6、;charinf;HNodeType;structHcodeTypeintbitMaxBit;intstart;voidCreat_Haffmantree(int&n)HNodeType*HaffNode=newHNodeType2*n-1;inti,j;intm1,m2,x1,x2;for(i=0;i2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf=0;for(i=0;iHaffNodei.inf;coutvv請輸入該字符的權值vvendl

7、;cinHaffNodei.weight;for(i=0;ivn-l;i+)構造哈夫曼樹ml=m2=Maxvalue;xl=x2=0;for(j=0;jvn+i;j+)選取最小和次小if(HaffNodej.parent=-l&HaffNodej.weightvml)m2=ml;x2=xl;ml=HaffNodej.weight;xl=j;elseif(HaffNodej.parent=-l&HaffNodej.weightvm2)m2=HaffNodej.weight;x2=j;/將找出的最小和次小合并，創(chuàng)造其父母結點HaffNodexl.parent=n+i;HaffNodex2.pare

8、nt=n+i;HaffNoden+i.weight=HaffNodexl.weight+HaffNodex2.weight;HaffNoden+i.lchild=xl;HaffNoden+i.rchild=x2;HaffNoden+i.inf=NULL;coutvv顯示存儲的哈弗曼樹信息:vvendl;coutvv權值左孩子右孩子雙親vvendl;for(i=0;iv2*n-1;i+)coutvvHaffNodei.weightvv;coutvvHaffNodei.lchildvv;coutvvHaffNodei.rchildvv;coutvvHaffNodei.parentvv;coutvv

9、HaffNodei.infvvendl;/寫入文件fstreamoutfile1;outfilel.open(E:nodedata.dat,ios:outlios:trunclios:binary);/健立進行寫入的文件if(!outfilel)/沒有創(chuàng)建成功則顯示相應信息coutvvnodedata.dat文件不能打開vvendl;abort();for(i=0;iv2*n-1;i+)將內(nèi)存中從HaffNodei地址開始的sizeof(HaffNodei)的內(nèi)容寫入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.cl

10、ose();/關閉文件deleteHaffNode;voidHaffCode(int&n)哈夫曼編碼HNodeType*HaffNode=newHNodeTypeMaxnode;HcodeType*HaffCode=newHcodeTypeMaxleaf;HcodeTypecd;inti,j,c,p;fstreamin(E:nodedata.dat,ios:in|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);in.close();fstreamoutfile;outfile.open(E:codedata.dat,io

11、s:outlios:binary);建立進行寫入的文件for(i=0;ivn;i+)cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1)if(HaffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1;jn;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;in;i+)outfileHaffNodei.inf;for(j=HaffC

12、odei.start+1;jn;j+)outfileHaffCodei.bitj;coutvv字符信息-編碼信息vvendl;for(i=0;iinf;intf=strlen(inf);fstreamoutfile1;outfilel.open(E:code.dat,ios:outlios:binary);/建立進行寫入的文件if(!outfile1)coutvvcode.dat文件不能打開!endl;abort();elsecoutendl;coutvv字符串編碼后為:；for(intx=0;xf;x+)for(i=0；in；i+)if(infx=HaffNodei.inf)for(j=Ha

13、ffCodei.start+1；jn；j+)outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj)；coutHaffCodei.bitj；coutendl；coutvv編譯后的代碼串已經(jīng)存入code.dat文件中!vvendl;coutendl；outfile1.close();deleteHaffNode;deleteHaffCode;voiddecode(int&n)解碼inti;HNodeType*HaffNode=newHNodeType2*n-1;fstreaminfile1;infilel.open(E:nodedat

14、a.dat,ios:inlios:binary);讀出哈夫曼樹if(!infile1)coutvvnodedata.dat文件不能打開vvendl;abort();for(i=0;iv2*n-l;i+)infilel.read(char*)&HaffNodei,sizeof(HNodeType);infilel.close();inttempcodel00;intnum=0;for(i=0;i100;i+)tempcodei=-1;HcodeType*Code=newHcodeTypen;fstreaminfile2;讀編碼infile2.open(E:code.dat,ios:in|ios:

15、binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;coutvv從文件中讀出的編碼為vvendl;for(i=0;inum;i+)coutvvtempcodei;coutvvendl;intm=2*n-2;i=0;coutvvendl;coutvv譯碼后為:vvendl;fstreamoutfile;outfile.open(E:textfile.txt,ios:out);if(!outfile)coutvvtextfile.txt文件

16、不能打開!vvendl;abort();while(ivnum)/小于字符串的長度while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1)if(tempcodei=0)m=HaffNodem.lchild;i+;elseif(tempcodei=1)m=HaffNodem.rchild;i+;coutHaffNodem.inf;outfileHaffNodem.inf;m=2*n-2;coutch1;while(!(ch1v=3&ch1=0)/輸入不在0到4之間無效coutvv數(shù)據(jù)輸入錯誤，請重新選擇(04):;cinch1;switch(ch1)case1:coutvvttt請輸入編碼個數(shù)vvendl;/葉子結點個數(shù)cinn;Creat_Haffmantree(n);break;case2:HaffCode(n);break;case3:dec