實(shí)驗(yàn)五簡(jiǎn)單哈夫曼編

1、實(shí)驗(yàn)五 簡(jiǎn)單哈夫曼編/譯碼的設(shè)計(jì)與實(shí)現(xiàn)本實(shí)驗(yàn)的目的是通過(guò)對(duì)簡(jiǎn)單哈夫曼編/譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)來(lái)熟練掌握樹型結(jié)構(gòu)在實(shí)際問(wèn)題中的應(yīng)用。此實(shí)驗(yàn)可以作為綜合實(shí)驗(yàn)，階段性實(shí)驗(yàn)時(shí)可以選擇其中的幾個(gè)功能來(lái)設(shè)計(jì)和實(shí)現(xià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)值，建立哈夫曼樹，并將它存于文件hfmtree.dat中。2、編碼。利用已建好的哈夫曼樹（

2、如不在內(nèi)存，則從文件hfmtree.dat中讀入），對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.dat中。3、譯碼。利用已建好的哈夫曼樹將文件codefile.dat中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat中。4、打印編碼規(guī)則。即字符與編碼的一一對(duì)應(yīng)關(guān)系。5、打印哈夫曼樹，將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在終端上。二、【數(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的大小

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

4、據(jù)類型：#define MAXBIT 10Typedef structInt bitMAXBIT；Int start；HCodeType；3、文件hfmtree.dat、codefile.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、建立哈夫曼編碼的功能模塊。此模塊功能為從文件hfm

5、tree.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、打印哈夫曼樹的功能模塊。此模塊功能為從HuffNode數(shù)組中讀入相關(guān)的結(jié)點(diǎn)信息，以圖形的方式將各個(gè)結(jié)點(diǎn)以及葉子結(jié)點(diǎn)的權(quán)值和左分支上的0和右分支上的1畫出來(lái)。四、【編碼實(shí)現(xiàn)】#include iostream#include fstream#include s

6、tringusing namespace std;#define MAXBIT 10#define MAX 1000#define MAXVALUE 1000typedef structint dataMAX;int front,rear;SeQueue;typedef structint weight;int parent;int lchild;int rchild;HNodeType;typedef structchar c;int n;int x;Math;typedef structint bitMAXBIT;int start;HCodeType;SeQueue *Init_SeQu

7、eue()SeQueue *q;q=new SeQueue;q-front=q-rear=-1;return q;int In_SeQueue(SeQueue *q,int x)if(q-rear=MAX-1)return 0;elseq-rear+;q-dataq-rear=x;return 1;int Out_SeQueue(SeQueue *q,int *x)if(q-rear=q-front)return 0;elseq-front+;*x=q-dataq-front;return 1;int WriteFile()char xMAX;int n;ofstream outfile(hf

8、mtree.txt,ios:out);if(!outfile)cerrOpen file or create file error.endl;elsecoutx;outfilexendl;n=strlen(x);outfile.close();return n-1;int ReadFile(int a)char *x,*y;Math M26;for(int i=0;i26;i+)Mi.n=0;Mi.x=-1;int *n,m=0,b=0;ifstream infile(hfmtree.txt,ios:in);if(!infile)cerrFile open error.x;for(int i=

9、0;ia;i+)for(int j=0;j26;j+)if(xi=a+j)Mj.c=xi;Mj.n+;Mj.x=0;for(int i=0;i26;i+)if(Mi.x=0)m+;n=new intm;y=new charm+1;for(int i=0;im;i+)ni=0;for(int i=0;i26;i+)if(Mi.x=0)yb=Mi.c;nb=Mi.n;b+;for(int i=0;im-1;i+)for(int j=i+1;jyj)char h;h=yi;yi=yj;yj=h;ofstream outfile2(char.txt,ios:out);if(!outfile2)cerr

10、Open or creat char error.endl;elsefor(int i=0;im;i+)outfile2yi;outfile2.close();ofstream outfile(hfmtree.txt,ios:app);if(!outfile)cerrOpen or creat hfmtree error.endl;elsefor(int i=0;im;i+)outfileniendl;outfile.close();ofstream outfile1(value.txt,ios:out);if(!outfile1)cerrOpen or creat value error.e

11、ndl;elsefor(int i=0;im;i+)outfile1niendl;outfile1.close();return m;void HaffmanTree(int m)int *n;char *y;n=new intm;y=new charm+1;ifstream infile1(char.txt,ios:in);if(!infile1)cerrRead file char error.y;HNodeType *Huffnode;Huffnode=new HNodeType26*2-1;int m1,m2,x1,x2;for(int i=0;i2*m-1;i+)Huffnodei.

12、weight=0;Huffnodei.parent=-1;Huffnodei.lchild=-1;Huffnodei.rchild=-1;ifstream infile(value.txt,ios:in);if(!infile)cerrRead file error.endl;elsefor(int i=0;ini;for(int i=0;im;i+)Huffnodei.weight=ni;for(int i=0;im-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(int j=0;jm+i;j+)if(Huffnodej.parent=-1&Huffnodej.weightm

13、1)m2=m1;x2=x1;m1=Huffnodej.weight;x1=j;elseif(Huffnodej.parent=-1&Huffnodej.weightm2)m2=Huffnodej.weight;x2=j;Huffnodex1.parent=m+i;Huffnodex2.parent=m+i;Huffnodem+i.weight=Huffnodex1.weight+Huffnodex2.weight;Huffnodem+i.lchild=x1;Huffnodem+i.rchild=x2;ofstream outfile(hfmtree.txt,ios:app);if(!outfi

14、le)cerrOpen or create file error.endl;elsefor(int i=0;i2*m-1;i+)outfileHuffnodei.weight ; outfileHuffnodei.parent ; outfileHuffnodei.lchild ; outfileHuffnodei.rchildendl;ofstream outfile1(hfmtree1.txt,ios:out);if(!outfile)cerrOpen or create file error.endl;elsefor(int i=0;i2*m-1;i+)outfile1Huffnodei

15、.weight ; outfile1Huffnodei.parent ; outfile1Huffnodei.lchild ; outfile1Huffnodei.rchildendl;void HaffmanCode(int m)char *y;int n,a,b;y=new charm+1;HNodeType *HuffNode;HuffNode=new HNodeType2*m-1;HCodeType HuffCode100,cd;int i,j,c,p; HaffmanTree(m);ifstream infile(hfmtree1.txt,ios:in);if(!infile)cer

16、rRead file error.endl;elsefor(i=0;iHuffNodei.weight;infileHuffNodei.parent;infileHuffNodei.lchild;infileHuffNodei.rchild;for(i=0;im;i+)cd.start=m-1;c=i;p=HuffNodec.parent;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1; cd.start-; c=p; p=HuffNodec.parent; for(j=cd.start+1;jm;

17、j+) HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start;ifstream infile1(char.txt,ios:in);if(!infile1)cerrRead char error.y;for(i=0;im;i+)coutyi ;for(j=HuffCodei.start+1;jm;j+)coutHuffCodei.bitj;coutendl;coutn;SeQueue *Q;Q=Init_SeQueue();for(int i=0;in;i+)couta;In_SeQueue(Q,a);HNodeType h; for(int i=0;irear!=Q-front)Out_S