實驗五 哈夫曼編碼與譯碼的設計與實現

1、實驗五 哈夫曼編碼與譯碼的設計與實現一、問題描述利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)編寫一個哈夫曼碼的編/譯碼系統(tǒng)?；疽螅海?）接收原始數據：從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件nodedata.dat中。（2）編碼：利用已建好的哈夫曼樹（如不在內存，則從文件nodedata.dat中讀入），對文件中的正文進行編碼，然后將結

2、果存入文件code.dat中。（3）譯碼：利用已建好的哈夫曼樹將文件code.dat中的代碼進行譯碼，結果存入文件textfile.txt中。（4）打印編碼規(guī)則：即字符與編碼的一一對應關系。（5）打印哈夫曼樹：將已在內存中的哈夫曼樹以直觀的方式顯示在終端上。二、數據結構設計1、構造哈夫曼樹時，使用靜態(tài)鏈表作為哈夫曼樹的存儲。在構造哈夫曼樹時，設計一個結構體數組HuffNode保存哈夫曼樹中各結點的信息，根據二叉樹的性質可知，具有n個葉子結點的哈夫曼樹共有2n-1個結點，所以數組HuffNode的大小設置為2n-1，描述結點的數據類型為：typedef struct int weight;int

3、 parent;int lchild;int rchild;char inf;HNodeType;2.求哈夫曼編碼時使用一維結構數組HuffCode作為哈夫曼編碼信息的存儲。求哈夫曼編碼實際上就是在已建立的哈夫曼樹中，從葉子結點開始，沿結點的雙親鏈域回退到根結點，每回退一步，就走過了哈夫曼的一個分支，從而得到一位哈夫曼編碼值。由于一個字符的哈夫曼編碼就是從根結點到相應葉子結點所經過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求的高位碼。所以設計如下數據類型：#define MaxBit 10struct HcodeTypeint bitMaxB

4、it;int start;3、文件nodedata.dat、code.dat、textfile.txt三、功能函數設計1、初始化功能模塊此功能模塊的功能為從鍵盤接受字符集大小n，以及n個字符和n個權值。2、建立哈夫曼編碼的功能模塊此模塊功能為使用1中得到的數據按照教材中的構造哈弗曼的算法構造哈弗曼樹，即將HuffNode數組中的各個位置的各個域都填上相關的值，并將這個結構體數組存于文件nodedata.dat中。函數原型為：void Creat_Haffmantree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m

5、1,m2,x1,x2;for(i=0;i<2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf='0'for(i=0;i<n;i+)cout<<"請輸入字符"<<endl;cin>>HaffNodei.inf;cout<<"請輸入該字符的權值"<<endl;cin>>HaffNodei.weight;for(

6、i=0;i<n-1;i+)/構造哈夫曼樹m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j+)/選取最小和次小if(HaffNodej.parent=-1&&HaffNodej.weight<m1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&&HaffNodej.weight<m2)m2=HaffNodej.weight;x2=j;/將找出的最小和次小合并，創(chuàng)造其父母結點HaffNodex1.parent=n+i;HaffNode

7、x2.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<<"權值左孩子右孩子雙親"<<endl; for(i=0;i<2*n-1;i+) cout<<HaffNodei.inf<<" "

8、; cout<<HaffNodei.weight<<" " cout<<HaffNodei.lchild<<" " cout<<HaffNodei.rchild<<" " cout<<HaffNodei.parent<<endl; /寫入文件fstream outfile1;outfile1.open("E:nodedata.dat",ios:out|ios:trunc|ios:binary);/建立進行寫入的文件if(

9、!outfile1) /沒有創(chuàng)建成功則顯示相應信息cout<<"nodedata.dat文件不能打開"<<endl;abort();for(i=0;i<2*n-1;i+) /將內存中從HaffNodei地址開始的sizeof(HaffNodei)的內容寫入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/關閉文件delete HaffNode;3、建立哈弗曼編碼功的功能模塊此模塊功能是從文件nodedata.dat中讀入相關的字符信息進行哈弗曼

10、編碼，然后將結果存入code.dat中，同時將字符與0和1代碼串的一一對應關系顯示到屏幕上。函數原型為：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.c

11、lose();fstream outfile;outfile.open("E:codedata.dat",ios:out|ios:binary);/建立進行寫入的文件for(i=0;i<n;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;j<n;j+)HaffCodei.bitj=cd.bit

12、j;HaffCodei.start=cd.start;for(i=0;i<n;i+) outfile<<HaffNodei.inf;for(j=HaffCodei.start+1;j<n;j+)outfile<<HaffCodei.bitj; cout<<"字符信息-編碼信息"<<endl; for(i=0;i<n;i+) cout<<HaffNodei.inf<<"-" for(j=HaffCodei.start+1;j<n;j+) cout<<

13、HaffCodei.bitj; cout<<endl; outfile.close ();cout<<"請輸入要編碼的字符串,基本元素為（"for(i=0;i<n;i+)cout<<HaffNodei.inf<<","cout<<")"<<endl;char inf100;cin>>inf;int f=strlen(inf);fstream outfile1;outfile1.open("E:code.dat",ios:out

14、|ios:binary);/建立進行寫入的文件if(!outfile1) cout<<"code.dat文件不能打開!"<<endl; abort(); else cout<<endl; cout<<"字符串編碼后為:" for(int x=0;x<f;x+) for(i=0;i<n;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1;j<n;j+) outfile1.write(char*)&HaffCodei.bitj,size

15、of(HaffCodei.bitj); cout<<HaffCodei.bitj; cout<<endl; cout<<"編譯后的代碼串已經存入code.dat文件中!"<<endl; cout<<endl; outfile1.close(); delete HaffNode;delete HaffCode;4. 此模塊功能為接收需要譯碼的0、1代碼串，按照3中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件textfile.dat，同時將翻譯的結果在屏幕上打印輸出。接受0、1代碼串有兩種形式，一種

16、是直接輸入，一種是從文件中讀取。函數原型為：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)cout<<"nodedata.dat文件不能打開"<<endl;abort();for(i=0;i<2*n-1;i+)infile1.read(char*)&Haf

17、fNodei,sizeof(HNodeType);infile1.close(); int tempcode100;int num=0;for(i=0;i<100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout<<"請選擇要做的操作："<<endl;cout<<"輸入串解碼，請按4"<<endl;cout<<"從文件中解碼，請按5"<<endl;int q;cin>>q;while(q>

18、;5|q<4)cout<<"輸入錯誤請重新輸入"cin>>q;switch(q)case 4:cout<<"請輸入要解碼的0,1串(按其他鍵結束輸入）："<<endl;i=0;cin>>tempcodei;while(tempcodei=0|tempcodei=1)i+;num=i;cin>>tempcodei;cout<<"輸入的編碼為："for(i=0;i<num;i+)cout<<tempcodei;cout<<

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

20、mpcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cout<<endl; outfile.close(); cout<<"譯碼后的結果已經存入textfile.txt中!"<<endl; delete HaffNode; break;case 5:fstream infile2;/讀編碼infile2.open(&

21、quot;E:code.dat",ios:in|ios:binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout<<"從文件中讀出的編碼為"<<endl;for(i=0;i<num;i+)cout<<tempcodei; cout<<endl; int m=2*n-2; i=0; cout<<endl; cout<<&

22、quot;譯碼后為:"<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfile) cout<<"textfile.txt文件不能打開!"<<endl; abort(); while(i<num)/ 小于字符串的長度 while(HaffNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;els

23、e if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cout<<endl; outfile.close(); cout<<"譯碼后的結果已經存入textfile.txt中!"<<endl; delete HaffNode; break; 四編碼實現#include "stdafx.h"#include<iostream>#include<fstre

24、am>#include<string.h>#include<stdlib.h>using namespace std;#define MaxBit 10#define Maxvalue 100/應該大于權重之和#define Maxleaf 100#define Maxnode Maxleaf*2-1typedef struct int weight;int parent;int lchild;int rchild;char inf;HNodeType;struct HcodeTypeint bitMaxBit;int start;void Creat_Haffm

25、antree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0;i<2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf='0'for(i=0;i<n;i+)cout<<"請輸入字符"<<endl;cin>>HaffNodei.inf;cout<

26、<"請輸入該字符的權值"<<endl;cin>>HaffNodei.weight;for(i=0;i<n-1;i+)/構造哈夫曼樹m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j+)/選取最小和次小if(HaffNodej.parent=-1&&HaffNodej.weight<m1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&&HaffNodej.weight<m2)m2=Ha

27、ffNodej.weight;x2=j;/將找出的最小和次小合并，創(chuàng)造其父母結點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<<"權值左孩子右孩子雙親"<<endl

28、; for(i=0;i<2*n-1;i+) cout<<HaffNodei.inf<<" " cout<<HaffNodei.weight<<" " cout<<HaffNodei.lchild<<" " cout<<HaffNodei.rchild<<" " cout<<HaffNodei.parent<<endl; /寫入文件fstream outfile1;outfile1.open(

29、"E:nodedata.dat",ios:out|ios:trunc|ios:binary);/建立進行寫入的文件if(!outfile1) /沒有創(chuàng)建成功則顯示相應信息cout<<"nodedata.dat文件不能打開"<<endl;abort();for(i=0;i<2*n-1;i+) /將內存中從HaffNodei地址開始的sizeof(HaffNodei)的內容寫入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/關

30、閉文件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(HNodeType);in.close();fstream outfile;outfile.op

31、en("E:codedata.dat",ios:out|ios:binary);/建立進行寫入的文件for(i=0;i<n;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;j<n;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=

32、0;i<n;i+) outfile<<HaffNodei.inf;for(j=HaffCodei.start+1;j<n;j+)outfile<<HaffCodei.bitj; cout<<"字符信息-編碼信息"<<endl; for(i=0;i<n;i+) cout<<HaffNodei.inf<<"-" for(j=HaffCodei.start+1;j<n;j+) cout<<HaffCodei.bitj; cout<<endl;

33、 outfile.close ();cout<<"請輸入要編碼的字符串,基本元素為（"for(i=0;i<n;i+)cout<<HaffNodei.inf<<","cout<<")"<<endl;char inf100;cin>>inf;int f=strlen(inf);fstream outfile1;outfile1.open("E:code.dat",ios:out|ios:binary);/建立進行寫入的文件if(!outfil

34、e1) cout<<"code.dat文件不能打開!"<<endl; abort(); else cout<<endl; cout<<"字符串編碼后為:" for(int x=0;x<f;x+) for(i=0;i<n;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1;j<n;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); cout<<H

35、affCodei.bitj; cout<<endl; cout<<"編譯后的代碼串已經存入code.dat文件中!"<<endl; cout<<endl; 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

36、:binary);/讀出哈夫曼樹if(!infile1)cout<<"nodedata.dat文件不能打開"<<endl;abort();for(i=0;i<2*n-1;i+)infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close(); int tempcode100;int num=0;for(i=0;i<100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout<<"請選擇要做的操作：&

37、quot;<<endl;cout<<"輸入串解碼，請按4"<<endl;cout<<"從文件中解碼，請按5"<<endl;int q;cin>>q;while(q>5|q<4)cout<<"輸入錯誤請重新輸入"cin>>q;switch(q)case 4:cout<<"請輸入要解碼的0,1串(按其他鍵結束輸入）："<<endl;i=0;cin>>tempcodei;whil

38、e(tempcodei=0|tempcodei=1)i+;num=i;cin>>tempcodei;cout<<"輸入的編碼為："for(i=0;i<num;i+)cout<<tempcodei;cout<<endl;int m=2*n-2;i=0;cout<<"譯碼后為："<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfile) cout<<&qu

39、ot;textfile.txt文件不能打開!"<<endl; abort(); while(i<num)/ 小于字符串的長度 while(HaffNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; cout<<HaffNodem.inf;outfile<<HaffNodem.inf;m=2*n-2; cout<<endl; out

40、file.close(); cout<<"譯碼后的結果已經存入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<<"

41、;從文件中讀出的編碼為"<<endl;for(i=0;i<num;i+)cout<<tempcodei; cout<<endl; int m=2*n-2; i=0; cout<<endl; cout<<"譯碼后為:"<<endl; fstream outfile; outfile.open("E:textfile.txt",ios:out); if(!outfile) cout<<"textfile.txt文件不能打開!"<<endl; abort(); while(i<num)/ 小于字符串的長度 while(HaffNodem.lchild!=-1&&HaffNodem.rchild!=-1) if(tempcodei=0)m=Haff