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

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

3、，根據(jù)二叉樹(shù)的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n-1，描述結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型為： Typedef strcut Int weight；/*結(jié)點(diǎn)權(quán)值*/ Int parent； Int lchild； Int rchild； HNodeType； 2、求哈夫曼編碼時(shí)使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲(chǔ)。 求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹(shù)中，從葉子結(jié)點(diǎn)開(kāi)始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，沒(méi)回退一步，就走過(guò)了哈夫曼樹(shù)的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑上

4、各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼位所求編碼的高位碼，所以設(shè)計(jì)如下數(shù)據(jù)類(lèi)型： #define MAXBIT 10 Typedef struct Int bitMAXBIT； Int start； HCodeType；3、文件hfmtree.dat、codefile.dat和textfile.dat。 2、功能（函數(shù)）設(shè)計(jì)（1）、初始化功能模塊。 此功能模塊的功能為從鍵盤(pán)接收字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值。 （2）、建立哈夫曼樹(shù)的功能模塊。 此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構(gòu)造哈夫曼樹(shù)的算法構(gòu)造哈夫曼樹(shù)，即將HuffNode數(shù)組中的

5、各個(gè)位置的各個(gè)域都添上相關(guān)的值，并將這個(gè)結(jié)構(gòu)體數(shù)組存于文件hfmtree.dat中。 （3）、建立哈夫曼編碼的功能模塊。 此模塊功能為從文件hfmtree.dat中讀入相關(guān)的字符信息進(jìn)行哈夫曼編碼，然后將結(jié)果存入codefile.dat中，同時(shí)將字符與0、1代碼串的一一對(duì)應(yīng)關(guān)系打印到屏幕上。 （4）、譯碼的功能模塊。 此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時(shí)將翻譯的結(jié)果在屏幕上打印輸出。 （5）、打印哈夫曼樹(shù)的功能模塊。 此模塊功能為從HuffNode數(shù)組中讀入相關(guān)的結(jié)點(diǎn)信息，以圖形的方式將各

6、個(gè)結(jié)點(diǎn)以及葉子結(jié)點(diǎn)的權(quán)值和左分支上的0和右分支上的1畫(huà)出來(lái)。 四、實(shí)驗(yàn)結(jié)果（程序）及分析1、實(shí)驗(yàn)主要代碼typedef struct /*結(jié)點(diǎn)結(jié)構(gòu)體*/ string hfmstr; /*結(jié)點(diǎn)內(nèi)容*/int weight; /*結(jié)點(diǎn)權(quán)值*/ int parent; int lchild; int rchild;HNodeType; typedef struct /* 編碼結(jié)構(gòu)體 */ int bitMAXBIT; int start;HCodeType; void Create_HuffMTree(HNodeType HFMTree,int n) /*創(chuàng)建哈夫曼樹(shù)*/int m1,x1,m2,

7、x2;int i,j;for(i=0;i2*n-1;i+)HFMTreei.hfmstr=;HFMTreei.weight=0;HFMTreei.parent=-1;HFMTreei.lchild=-1;HFMTreei.rchild=-1;for(i=0;in;i+) cout請(qǐng)輸入第i+1個(gè)權(quán)值HFMTreei.weight;cout請(qǐng)輸入對(duì)應(yīng)字符HFMTreei.hfmstr;for(i=0;in-1;i+)x1=x2=MAXVALUE;m1=m2=0;for(j=0;jn+i;j+)if(HFMTreej.parent=-1&HFMTreej.weightx1)x2=x1;m2=m1;

8、x1=HFMTreej.weight;m1=j;else if(HFMTreej.parent=-1&HFMTreej.weightx2)x2=HFMTreej.weight;m2=j;HFMTreem1.parent=n+i;HFMTreem2.parent=n+i;HFMTreen+i.weight=HFMTreem1.weight+HFMTreem2.weight;HFMTreen+i.lchild=m1;HFMTreen+i.rchild=m2; cout創(chuàng)建哈夫曼樹(shù)成功！endl;void HaffmanCode(HNodeType HFMTree,HCodeType HuffCod

9、e,int n) /*構(gòu)建哈夫曼編碼*/HCodeType cd;int i,j,c,p; for(i=0;in;i+) cd.start=n-1; c=i; p=HFMTreec.parent; while(p!=-1) if(HFMTreep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=HFMTreec.parent; for(j=cd.start+1;jn;j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; void decodeing(char string,HNodeType HFMTree,int n) /*解碼*/ int i,tmp=0,code1024; int m=2*n-1; char *nump; char num1024; for(i=0;istrlen(string);i+) if(stringi=0) numi=0; else numi=1; i=0; nump=&num0; while(nump(&numstrlen(string) tmp=m-1; while(HFMTr