哈夫曼編碼譯碼的設(shè)計與實現(xiàn)

1、1軟件學院課程設(shè)計報告設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 選題名稱： 哈夫曼編碼/譯碼的設(shè)計與實現(xiàn) 姓 名： 學 號： 專業(yè)班級： 移動 一 班 系 （院）： 軟件學院 設(shè)計時間： 2014.6.12014.6.4 目 錄一、需求分析-3 二、系統(tǒng)設(shè)計-33、 程序流程圖-10四、實現(xiàn)代碼-13五、總結(jié)-23六、參考書目-23數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 第 22 頁 共 23 頁1、 需求分析哈夫曼編碼是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，哈夫曼編碼是一種編碼方式，以哈夫曼樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。哈夫曼編碼使用一張?zhí)厥獾木幋a表將源字符進行編碼。這張編碼表的特殊在于，它是根據(jù)每一

2、個源字符出現(xiàn)的估算概率而建立起來的。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼成為哈夫曼編碼，樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。哈夫曼譯碼輸入字符串可以把它編譯成二進制代碼。輸入二進制代碼時可以編譯成字符串。2、 系統(tǒng)設(shè)計構(gòu)造哈夫曼樹時，使用靜態(tài)鏈表作為哈夫曼樹的存儲。在構(gòu)造哈夫曼樹時，設(shè)計一個結(jié)構(gòu)體數(shù)組HuffNode保存哈夫曼樹中各結(jié)點的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點

3、，所以數(shù)組HuffNode的大小設(shè)置為2n-1，求哈夫曼編碼時使用一維結(jié)構(gòu)數(shù)組HuffCode作為哈夫曼編碼信息的存儲。求哈夫曼編碼實際上就是在已建立的哈夫曼樹中，從葉子結(jié)點開始，沿結(jié)點的雙親鏈域回退到根結(jié)點，每回退一步，就走過了哈夫曼的一個分支，從而得到一位哈夫曼編碼值。由于一個字符的哈夫曼編碼就是從根結(jié)點到相應(yīng)葉子結(jié)點所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求的高位碼1、初始化功能模塊此功能模塊的功能為從鍵盤接受字符集大小n，以及n個字符和n個權(quán)值。2、建立哈夫曼編碼的功能模塊此模塊功能為使用1中得到的數(shù)據(jù)按照教材中的構(gòu)造哈弗曼的

4、算法構(gòu)造哈弗曼樹，即將HuffNode數(shù)組中的各個位置的各個域都填上相關(guān)的值，并將這個結(jié)構(gòu)體數(shù)組存于文件nodedata.dat中。函數(shù)原型為：void Creat_Haffmantree(int &n)HNodeType *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請輸入字

5、符HaffNodei.inf;cout請輸入該字符的權(quán)值HaffNodei.weight;for(i=0;in-1;i+)/構(gòu)造哈夫曼樹m1=m2=Maxvalue;x1=x2=0;for(j=0;jn+i;j+)/選取最小和次小if(HaffNodej.parent=-1&HaffNodej.weightm1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&HaffNodej.weightm2)m2=HaffNodej.weight;x2=j;/將找出的最小和次小合并，創(chuàng)造其父母結(jié)點HaffNodex1.pare

6、nt=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout顯示存儲的哈弗曼樹信息:endl; cout權(quán)值左孩子右孩子雙親endl; for(i=0;i2*n-1;i+) coutHaffNodei.inf ; coutHaffNodei.weight ; coutHaffNodei.lchild ; coutHaffNodei.rchild ; c

7、outHaffNodei.parentendl; /寫入文件fstream outfile1;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);outfile

8、1.close ();/關(guān)閉文件delete HaffNode;3、建立哈弗曼編碼功的功能模塊此模塊功能是從文件nodedata.dat中讀入相關(guān)的字符信息進行哈弗曼編碼，然后將結(jié)果存入code.dat中，同時將字符與0和1代碼串的一一對應(yīng)關(guān)系顯示到屏幕上。函數(shù)原型為：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:i

9、n|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);in.close();fstream outfile;outfile.open(E:codedata.dat,ios:out|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;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.pare

10、nt;for(j=cd.start+1;jn;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;in;i+) outfileHaffNodei.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請

11、輸入要編碼的字符串,基本元素為（;for(i=0;in;i+)coutHaffNodei.inf,;cout)inf;int f=strlen(inf);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.s

12、tart+1;jn;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); coutHaffCodei.bitj; coutendl; cout編譯后的代碼串已經(jīng)存入code.dat文件中!endl; coutendl; outfile1.close(); delete HaffNode;delete HaffCode;4. 此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時將翻譯的結(jié)果在屏幕上打印輸出。接受0、1代碼串有兩種形式

13、，一種是直接輸入，一種是從文件中讀取。函數(shù)原型為：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.dat文件不能打開endl;abort();for(i=0;i2*n-1;i+)infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close(); int tem

14、pcode100;int num=0;for(i=0;i100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout請選擇要做的操作：endl;cout輸入串解碼，請按4endl;cout從文件中解碼，請按5q;while(q5|q4)coutq;switch(q)case 4:cout請輸入要解碼的0,1串(按其他鍵結(jié)束輸入）：tempcodei;while(tempcodei=0|tempcodei=1)i+;num=i;cintempcodei;cout輸入的編碼為：;for(i=0;inum;i+)couttempcodei;coute

15、ndl;int m=2*n-2;i=0;cout譯碼后為：endl; fstream outfile; outfile.open(E:textfile.txt,ios:out); if(!outfile) couttextfile.txt文件不能打開!endl; abort(); while(inum)/ 小于字符串的長度 while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; coutHaff

16、Nodem.inf;outfileHaffNodem.inf;m=2*n-2; coutendl; outfile.close(); cout譯碼后的結(jié)果已經(jīng)存入textfile.txt中!endl; delete HaffNode; break;case 5:fstream infile2;/讀編碼infile2.open(E:code.dat,ios:in|ios:binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout從文件中

17、讀出的編碼為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)/ 小于字符串的長度 while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.l

18、child;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; break; 3、 程序流程圖1. 系統(tǒng)結(jié)構(gòu)圖 哈夫曼編碼譯碼器 退出 譯碼 編碼 建樹2. 各部分功能圖建樹： 開始 初始化哈夫曼鏈表且有2n-1個節(jié)點 i=1inweight=countip=p-next for(i=n;iParent-L

19、Child)HCi.code-HCi.start=1HCi.code-HCi.start=0 p=p-nexti=n時 結(jié)束譯碼： 開始Root指向根節(jié)點 P!=rootp=p-RChildcodei=0 p=p-LChildp-LChild=NULL&p-RChild=NULLsk+=strj p=root 結(jié)束4、 實現(xiàn)代碼/#include stdafx.h#include#include#include#includeusing namespace std;#define MaxBit 10#define Maxvalue 100#define Maxleaf 100#define M

20、axnode 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;i2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchi

21、ld=-1;HaffNodei.rchild=-1;HaffNodei.inf=0;for(i=0;in;i+)cout請輸入字符HaffNodei.inf;cout請輸入該字符的權(quán)值HaffNodei.weight;for(i=0;in-1;i+)/構(gòu)造哈夫曼樹m1=m2=Maxvalue;x1=x2=0;for(j=0;jn+i;j+)if(HaffNodej.parent=-1&HaffNodej.weightm1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&HaffNodej.weightm2)m2=H

22、affNodej.weight;x2=j;/創(chuàng)造其父母結(jié)點HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout顯示存儲的哈弗曼樹信息:endl; cout權(quán)值左孩子右孩子雙親endl; for(i=0;i2*n-1;i+) coutHaffNodei.inf ; coutHaffNodei.weight ; cou

23、tHaffNodei.lchild ; coutHaffNodei.rchild ; coutHaffNodei.parentendl; /寫入文件fstream outfile1;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.writ

24、e(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/關(guān)閉文件delete HaffNode;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(HNodeTy

25、pe);in.close();fstream outfile;outfile.open(E:codedata.dat,ios:out|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;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1;jn;j+)HaffCodei.bitj=cd.bitj;HaffCodei.

26、start=cd.start;for(i=0;in;i+) outfileHaffNodei.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)inf;

27、int f=strlen(inf);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(H

28、affCodei.bitj); 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)coutnodedat

29、a.dat文件不能打開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;cout請選擇要做的操作：endl;cout輸入串解碼，請按4endl;cout從文件中解碼，請按5q;while(q5|q4)coutq;switch(q)case 4:cout請輸入要解碼的0,1串(按其他鍵結(jié)

30、束輸入）：tempcodei;while(tempcodei=0|tempcodei=1)i+;num=i;cintempcodei;cout輸入的編碼為：;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;cout譯碼后為：endl; fstream outfile; outfile.open(E:textfile.txt,ios:out); if(!outfile) couttextfile.txt文件不能打開!endl; abort(); while(inum)/ 小于字符串的長度 while(HaffNodem.lchild!

31、=-1&HaffNodem.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; break;case 5:fstream infile2;/讀編碼infile2.open(E:code.dat,ios:in|ios:

32、binary);while(!infile2.eof()infile2.read(char*)&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)/ 小于字符串的長度 while(HaffNodem.lchild!=-1&HaffNodem.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(); co