數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實驗報告

1、本文格式為word版，下載可任意編輯數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼實驗報告 數(shù)據(jù)結(jié)構(gòu)試驗報告 試驗五 簡潔哈夫曼編/譯碼的設(shè)計與實現(xiàn) 本試驗的目的是通過對簡潔哈夫曼編/譯碼系統(tǒng)的設(shè)計與實現(xiàn)來嫻熟把握樹型結(jié)構(gòu)在實際問題中的應(yīng)用。此試驗可以作為綜合試驗，階段性試驗時可以選擇其中的幾個功能來設(shè)計和實現(xiàn)。 一、【問題描述】 利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼，此試驗即設(shè)計這樣的一個簡潔編/碼系統(tǒng)。系統(tǒng)應(yīng)當(dāng)具有如下的幾個功能： 1、接收原始數(shù)據(jù)。 從終端讀入字符集大小 n，以及 n 個字符

2、和 n 個權(quán)值，建立哈夫曼樹，并將它存于文件nodedata.dat 中。 2、編碼。 利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件 nodedata.dat 中讀入），對文件中的正文進行編碼，然后將結(jié)果存入文件 code.dat 中。 3、譯碼。利用已建好的哈夫曼樹將文件 code.dat 中的代碼進行譯碼，結(jié)果存入文件textfile.dat 中。 4、打印編碼規(guī)章。 即字符與編碼的一一對應(yīng)關(guān)系。 二、【數(shù)據(jù)結(jié)構(gòu)設(shè)計】 1、構(gòu)造哈夫曼樹時使用靜態(tài)鏈表作為哈夫曼樹的存儲。 在構(gòu)造哈夫曼樹時，設(shè)計一個結(jié)構(gòu)體數(shù)組 huffnode 保存哈夫曼樹中各結(jié)點的信息，依據(jù)二叉樹的性質(zhì)可知，具有 n 個葉子

3、結(jié)點的哈夫曼樹共有 2n-1 個結(jié)點，所以數(shù)組 huffnode的大小設(shè)置為 2n-1，描述結(jié)點的數(shù)據(jù)類型為： typedef struct int weight;/結(jié)點權(quán)值 int parent; int lchild; int rchild; char inf; hnodetype; 2、求哈夫曼編碼時使用一維結(jié)構(gòu)數(shù)組 huffcode 作為哈夫曼編碼信息的存儲。 求哈夫曼編碼，實質(zhì)上就是在已建立的哈夫曼樹中，從葉子結(jié)點開頭，沿結(jié)點的雙親鏈域回退到根結(jié)點，沒回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結(jié)點到相應(yīng)葉子結(jié)點所經(jīng)過的路徑上各分支所組

4、成的 0、1 序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼位所求編碼的高位碼，所以設(shè)計如下數(shù)據(jù)類型： #define maxbit 10 typedef struct int bitmaxbit； int start； - hcodetype； 3、文件 nodedata.dat、code.dat 和 textfile.dat。 三、【功能（函數(shù)）設(shè)計】 1、初始化功能模塊。 此功能模塊的功能為從鍵盤接收字符集大小 n，以及 n 個字符和 n 個權(quán)值。 2、建立哈夫曼樹的功能模塊。 此模塊功能為使用 1 中得到的數(shù)據(jù)根據(jù)教材中的構(gòu)造哈夫曼樹的算法構(gòu)造哈夫曼樹，即將 huffn

5、ode 數(shù)組中的各個位置的各個域都添上相關(guān)的值，并將這個結(jié)構(gòu)體數(shù)組存于文件hfmtree.dat 中。 3、建立哈夫曼編碼的功能模塊。 此模塊功能為從文件 nodedata.dat 中讀入相關(guān)的字符信息進行哈夫曼編碼，然后將結(jié)果存入 code.dat 中，同時將字符與 0、1 代碼串的一一對應(yīng)關(guān)系打印到屏幕上。 4、譯碼的功能模塊。 此模塊功能為接收需要譯碼的 0、1 代碼串，根據(jù) 3 中建立的編碼規(guī)章將其翻譯成字符集中字符所組成的字符串形式，存入文件 textfile.dat，同時將翻譯的結(jié)果在屏幕上打印輸出。 四、【編碼實現(xiàn)】 #includeiostream.h #includefstr

6、eam.h #includestring.h #includestdlib.h #define maxbit 10 #define maxvalue 100/應(yīng)當(dāng)大于權(quán)重之和 #define maxleaf 100 #define maxnode maxleaf*2-1 typedef struct int weight; int parent; int lchild; int rchild; char inf; hnodetype; struct hcodetype int bitmaxbit; int start; ; void creat_haffmantree(int n) hnode

7、type *haffnode=new hnodetype2*n-1; - int i,j; int m1,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;in;i+) cout請輸入字符endl; cinhaffnodei.inf; cout請輸入該字符的權(quán)值endl; cinhaffnodei.weight; for(i=0;in-1;i+)/構(gòu)造

8、哈夫曼樹 m1=m2=maxvalue; x1=x2=0; for(j=0;jn+i;j+)/選取最小和次小 if(haffnodej.parent=-1haffnodej.weightm1) m2=m1; x2=x1; m1=haffnodej.weight; x1=j; else if(haffnodej.parent=-1haffnodej.weightm2) m2=haffnodej.weight; x2=j; /將找出的最小和次小合并，制造其父母結(jié)點 haffnodex1.parent=n+i; haffnodex2.parent=n+i; haffnoden+i.weight=ha

9、ffnodex1.weight+haffnodex2.weight; haffnoden+i.lchild=x1; - haffnoden+i.rchild=x2; haffnoden+i.inf=null; cout顯示存儲的哈弗曼樹信息:endl; cout權(quán)值 左孩子 右孩子 雙親endl; for(i=0;i2*n-1;i+) couthaffnodei.weight ; couthaffnodei.lchild ; couthaffnodei.rchild ; couthaffnodei.parent ; couthaffnodei.infendl; /寫入文件 fstream ou

10、tfile1; outfile1.open(e:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立進行寫入的文件 if(!outfile1) /沒有創(chuàng)建勝利則顯示相應(yīng)信息 coutnodedata.dat 文件不能打開endl; abort(); for(i=0;i2*n-1;i+) /將內(nèi)存中從 haffnodei地址開頭的 sizeof(haffnodei)的內(nèi)容寫入文件中 outfile1.write(char*)haffnodei,sizeof(haffnodei); outfile1.close ();/關(guān)閉文件 delete haffnod

11、e; void haffcode(int n)/哈夫曼編碼 hnodetype *haffnode=new hnodetypemaxnode; hcodetype *haffcode=new hcodetypemaxleaf; 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:ou

12、t|ios:binary);/建立進行寫入的文件 for(i=0;in;i+) cd.start=n-1; - c=i; p=haffnodec.parent; while(p!=-1) if(haffnodep.lchild=c) cd.bitcd.start=0; else cd.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.

13、inf; for(j=haffcodei.start+1;jn;j+) outfilehaffcodei.bitj; cout字符信息-編碼信息endl; for(i=0;in;i+) couthaffnodei.inf-; for(j=haffcodei.start+1;jn;j+) couthaffcodei.bitj; coutendl; outfile.close (); cout請輸入要編碼的字符串,基本元素為（; for(i=0;in;i+) couthaffnodei.inf,; cout)endl; char inf100; cininf; int f=strlen(inf);

14、 fstream outfile1; outfile1.open(e:code.dat,ios:out|ios:binary);/建立進行寫入的文件 if(!outfile1) coutcode.dat 文件不能打開!endl; - abort(); else coutendl; cout字符串編碼后為:; for(int x=0;xf;x+) for(i=0;in;i+) if(infx=haffnodei.inf) for(j=haffcodei.start+1;jn;j+) outfile1.write(char*)haffcodei.bitj,sizeof(haffcodei.bitj

15、); couthaffcodei.bitj; coutendl; cout編譯后的代碼串已經(jīng)存入 code.dat 文件中!endl; coutendl; outfile1.close(); 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) coutnodedata.da

16、t 文件不能打開endl; abort(); for(i=0;i2*n-1;i+) infile1.read(char*)haffnodei,sizeof(hnodetype); infile1.close(); int tempcode100; - int num=0; for(i=0;i100;i+) tempcodei=-1; hcodetype *code=new hcodetypen; fstream infile2;/讀編碼 infile2.open(e:code.dat,ios:in|ios:binary); while(!infile2.eof() infile2.read(c

17、har*)tempcodenum,sizeof(tempcodenum); num+; infile2.close(); num-; cout從文件中讀出的編碼為endl; for(i=0;inum;i+) couttempcodei; coutendl; int m=2*n-2; i=0; coutendl; cout譯碼后為:endl; fstream outfile; outfile.open(e:textfile.txt,ios:out); if(!outfile) couttextfile.txt 文件不能打開!endl; abort(); while(inum)/ 小于字符串的長度

18、 while(haffnodem.lchild!=-1haffnodem.rchild!=-1) if(tempcodei=0) m=haffnodem.lchild; i+; else if(tempcodei=1) m=haffnodem.rchild; i+; - couthaffnodem.inf; outfilehaffnodem.inf; m=2*n-2; coutendl; outfile.close(); cout譯碼后的結(jié)果已經(jīng)存入 textfile.txt 中!endl; delete haffnode; int main() int n; cout* 歡 迎 進 入 編 / 譯 碼 系 統(tǒng) ！*endl; int