哈夫曼樹實(shí)驗(yàn)報(bào)告

1、計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告班級2014級計(jì)算機(jī)1班學(xué)號姓名張建華成績實(shí)驗(yàn)項(xiàng)目簡單哈夫曼編/譯碼的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)日期2016.1.5一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)的目的是進(jìn)一步理解哈夫曼樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，進(jìn)一步提高使用理論知識指導(dǎo)解決實(shí)際問題的能力。二、實(shí)驗(yàn)問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼，此實(shí)驗(yàn)即設(shè)計(jì)這樣的一個簡單編/碼系統(tǒng)。系統(tǒng)應(yīng)該具有如下的幾個功能：1、接收原始數(shù)據(jù)。從終端讀入字符集大小n,以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmt

2、ree.dat中。2、編碼。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.dat中讀入），對文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.dat中。3、譯碼。利用已建好的哈夫曼樹將文件codefile.dat中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat中。4、打印編碼規(guī)則。即字符與編碼的對應(yīng)關(guān)系。5、打印哈夫曼樹，將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在終端上三、實(shí)驗(yàn)步驟1 、實(shí)驗(yàn)問題分析1 、構(gòu)造哈夫曼樹時(shí)使用靜態(tài)鏈表作為哈夫曼樹的存儲。在構(gòu)造哈夫曼樹時(shí)，設(shè)計(jì)一個結(jié)構(gòu)體數(shù)組HuffNode保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點(diǎn)的哈

3、夫曼樹共有2n-1個結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n-1，描述結(jié)點(diǎn)的數(shù)據(jù)類型為：TypedefstrcutIntweight；/*結(jié)點(diǎn)權(quán)值*/Intparent；Intlchild；Intrchild；HNodeType；2 、求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲。求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉子結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，沒回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后

4、得到的分支代碼位所求編碼的高位碼，所以設(shè)計(jì)如下數(shù)據(jù)類型：#defineMAXBIT10TypedefstructIntbitMAXBIT；Intstart；HCodeType；3、文件hfmtree.dat、codefile.dat和textfile.dat。2、功能（函數(shù)）設(shè)計(jì)（ 1） 、初始化功能模塊。此功能模塊的功能為從鍵盤接收字符集大小n,以及n個字符和n個權(quán)值。（ 2） 、建立哈夫曼樹的功能模塊。此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構(gòu)造哈夫曼樹的算法構(gòu)造哈夫曼樹，即將HuffNode數(shù)組中的各個位置的各個域都添上相關(guān)的值，并將這個結(jié)構(gòu)體數(shù)組存于文件hfmtree.dat中。（

5、3） 、建立哈夫曼編碼的功能模塊。此模塊功能為從文件hfmtree.dat中讀入相關(guān)的字符信息進(jìn)行哈夫曼編碼，然后將結(jié)果存入codefile.dat中，同時(shí)將字符與0、1代碼串的一一對應(yīng)關(guān)系打印到屏幕上。（ 4） 、譯碼的功能模塊。此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時(shí)將翻譯的結(jié)果在屏幕上打印輸出。（ 5） 、打印哈夫曼樹的功能模塊。此模塊功能為從HuffNode數(shù)組中讀入相關(guān)的結(jié)點(diǎn)信息，以圖形的方式將各個結(jié)點(diǎn)以及葉子結(jié)點(diǎn)的權(quán)值和左分支上的0和右分支上的1畫出來。四、實(shí)驗(yàn)結(jié)果（程序）及分析1

6、 、實(shí)驗(yàn)主要代碼typedefstruct/*結(jié)點(diǎn)結(jié)構(gòu)體*/stringhfmstr;/*結(jié)點(diǎn)內(nèi)容*/intweight;/*結(jié)點(diǎn)權(quán)值*/intparent;intlchild;intrchild;HNodeType;typedefstruct/*編碼結(jié)構(gòu)體*/intbitMAXBIT;intstart;HCodeType;創(chuàng)建哈夫曼樹*/voidCreate_HuffMTree(HNodeTypeHFMTree,intn)/*intm1,x1,m2,x2;inti,j;for(i=0;i<2*n-1;i+)HFMTreei.hfmstr=""HFMTreei.wei

7、ght=0;HFMTreei.parent=-1;HFMTreei.lchild=-1;HFMTreei.rchild=-1;for(i=0;i<n;i+)cout<<"請輸入第"<<i+1<<"個權(quán)值"<<endl;cin>>HFMTreei.weight;cout<<"請輸入對應(yīng)字符"<<endl;cin>>HFMTreei.hfmstr;for(i=0;i<n-1;i+)x1=x2=MAXVALUE;m1=m2=0;for

8、(j=0;j<n+i;j+)if(HFMTreej.parent=-1&&HFMTreej.weight<x1)x2=x1;m2=m1;x1=HFMTreej.weight;m1=j;elseif(HFMTreej.parent=-1&&HFMTreej.weight<x2)x2=HFMTreej.weight;m2=j;HFMTreem1.parent=n+i;HFMTreem2.parent=n+i;HFMTreen+i.weight=HFMTreem1.weight+HFMTreem2.weight;HFMTreen+i.lchild=m

9、1;HFMTreen+i.rchild=m2;cout<<"創(chuàng)建哈夫曼樹成功！"<<endl;voidHaffmanCode(HNodeTypeHFMTree,HCodeTypeHuffCode,intn)/*構(gòu)建*/HCodeTypecd;inti,j,c,p;for(i=0;i<n;i+)cd.start=n-1;c=i;p=HFMTreec.parent;while(p!=-1)if(HFMTreep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HFMTre

10、ec.parent;for(j=cd.start+1;j<n;j+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start;voiddecodeing(charstring,HNodeTypeHFMTree,intn)/*解碼*/inti,tmp=0,code1024;intm=2*n-1;char*nump;charnum1024;for(i=0;i<strlen(string);i+)if(stringi='0')numi=0;elsenumi=1;i=0;nump=&num0;while(nump<(&numstrlen(string)tmp=m-1;while(HFMTreetmp.lchild!=-1)&&(HFMTreetmp.rchild!=-1)if(*nump=0)tmp=HFMTreetmp.lchild;elsetmp=HFMTreetmp.rchild;nump+;cout<<HFMTreetmp.hfmstr;cout<<endl;2、測試數(shù)據(jù)與輸出y丁"yb，imwT”J、=/、-rwur")V>CJ