數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實(shí)驗(yàn)報(bào)告

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

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

3、uct int weight;/結(jié)點(diǎn)權(quán)值int parent;int lchild;int rchild;char inf;HNodeType;2、求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲(chǔ)。求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉子結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，沒回退一步，就走過了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼位所求編碼的高位碼，所以設(shè)計(jì)如下數(shù)據(jù)類型：#define MAXBIT 10ty

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

5、，然后將結(jié)果存入code.dat中，同時(shí)將字符與0、1代碼串的一一對(duì)應(yīng)關(guān)系打印到屏幕上。4、譯碼的功能模塊。此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時(shí)將翻譯的結(jié)果在屏幕上打印輸出。四、【編碼實(shí)現(xiàn)】 #include<iostream.h>#include<fstream.h>#include<string.h>#include<stdlib.h>#define MaxBit 10#define Maxvalue 100/應(yīng)該大于權(quán)重之和#defin

6、e Maxleaf 100#define Maxnode Maxleaf*2-1typedef struct int weight;int parent;int lchild;int rchild;char inf;HNodeType;struct HcodeTypeint bitMaxBit;int start;void Creat_Haffmantree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0;i<2*n-1;i+)HaffNodei.weight=0;Haff

7、Nodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf='0'for(i=0;i<n;i+)cout<<"請(qǐng)輸入字符"<<endl;cin>>HaffNodei.inf;cout<<"請(qǐng)輸入該字符的權(quán)值"<<endl;cin>>HaffNodei.weight;for(i=0;i<n-1;i+)/構(gòu)造哈夫曼樹m1=m2=Maxvalue;x1=x2=0;for(j=0;j&

8、lt;n+i;j+)/選取最小和次小if(HaffNodej.parent=-1&&HaffNodej.weight<m1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&&HaffNodej.weight<m2)m2=HaffNodej.weight;x2=j;/將找出的最小和次小合并，創(chuàng)造其父母結(jié)點(diǎn)HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffN

9、odex2.weight;HaffNoden+i.lchild=x1;HaffNoden+i.rchild=x2;HaffNoden+i.inf=NULL;cout<<"顯示存儲(chǔ)的哈弗曼樹信息:"<<endl; cout<<"權(quán)值 左孩子 右孩子 雙親"<<endl; for(i=0;i<2*n-1;i+) cout<<HaffNodei.weight<<" " cout<<HaffNodei.lchild<<" "

10、; cout<<HaffNodei.rchild<<" " cout<<HaffNodei.parent<<" " cout<<HaffNodei.inf<<endl;/寫入文件fstream outfile1;outfile1.open("E:nodedata.dat",ios:out|ios:trunc|ios:binary);/建立進(jìn)行寫入的文件if(!outfile1) /沒有創(chuàng)建成功則顯示相應(yīng)信息cout<<"nodedata.da

11、t文件不能打開"<<endl;abort();for(i=0;i<2*n-1;i+) /將內(nèi)存中從HaffNodei地址開始的sizeof(HaffNodei)的內(nèi)容寫入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/關(guān)閉文件delete HaffNode;void HaffCode(int &n)/哈夫曼編碼HNodeType *HaffNode=new HNodeTypeMaxnode;HcodeType *HaffCode=new HcodeType

12、Maxleaf;HcodeType cd;int i,j,c,p;fstream in("E:nodedata.dat",ios:in|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);in.close();fstream outfile;outfile.open("E:codedata.dat",ios:out|ios:binary);/建立進(jìn)行寫入的文件for(i=0;i<n;i+)cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-

13、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;j<n;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;i<n;i+) outfile<<HaffNodei.inf;for(j=HaffCodei.start+1;j<n;j+)outfile<<HaffCodei.bitj; cout<<"

14、;字符信息-編碼信息"<<endl; for(i=0;i<n;i+) cout<<HaffNodei.inf<<"-" for(j=HaffCodei.start+1;j<n;j+) cout<<HaffCodei.bitj; cout<<endl; outfile.close ();cout<<"請(qǐng)輸入要編碼的字符串,基本元素為（"for(i=0;i<n;i+)cout<<HaffNodei.inf<<","c

15、out<<")"<<endl;char inf100;cin>>inf;int f=strlen(inf);fstream outfile1;outfile1.open("E:code.dat",ios:out|ios:binary);/建立進(jìn)行寫入的文件if(!outfile1) cout<<"code.dat文件不能打開!"<<endl; abort(); else cout<<endl; cout<<"字符串編碼后為:" fo

16、r(int x=0;x<f;x+) for(i=0;i<n;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1;j<n;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); cout<<HaffCodei.bitj; cout<<endl; cout<<"編譯后的代碼串已經(jīng)存入code.dat文件中!"<<endl; cout<<endl; outfile1.clo

17、se(); delete HaffNode;delete HaffCode;void decode( int &n)/解碼int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open("E:nodedata.dat",ios:in|ios:binary);/讀出哈夫曼樹if(!infile1)cout<<"nodedata.dat文件不能打開"<<endl;abort();for(i=0;i<2*n-1;i+)infile1.rea

18、d(char*)&HaffNodei,sizeof(HNodeType);infile1.close(); int tempcode100;int num=0;for(i=0;i<100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;fstream infile2;/讀編碼infile2.open("E:code.dat",ios:in|ios:binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);n

19、um+;infile2.close();num-;cout<<"從文件中讀出的編碼為"<<endl;for(i=0;i<num;i+)cout<<tempcodei; cout<<endl; int m=2*n-2; i=0; cout<<endl; cout<<"譯碼后為:"<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfile) cout<

20、<"textfile.txt文件不能打開!"<<endl; abort(); while(i<num)/ 小于字符串的長度 while(HaffNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cout<<endl; outfile.close(); cout<<"譯碼后的結(jié)果已經(jīng)存入textfile.txt中!"<<endl; delete HaffNode; int main() int n;cout<<"* 歡迎進(jìn)入編/譯碼系統(tǒng)！*"<<endl; int ch1;docout<<" 1.建樹"<<endl;cout<<" 2:編碼，并顯示字符和對(duì)應(yīng)的編碼"<<end