哈夫曼樹編碼譯碼

1、程序源代碼: 文件一:my.h(自定義頭文件) /調(diào)用有文件以及定義常數(shù)值#include "stdio.h"#include "string.h"#define MAXLEN 100#define MAXLEN_1 1000/自定義類型聲明typedef struct int weight; char data; int lchild,rchild,parent;HFMTnode;typedef 

2、;HFMTnode HFMTMAXLEN;typedef struct char codeMAXLEN; char data;HFMCnode;typedef HFMCnode HFMCMAXLEN;typedef struct char dataMAXLEN; int top;seqstack;/文件全局變量外部聲明extern int n;/所有子函數(shù)聲明void InitializeTree(HFMT T);void&#

3、160;InputTree(HFMT T);void Selectleast(HFMT T,int *p1,int *p2);void CreateHFMT(HFMT T);void push(char x);void hfmc(HFMT T,int i);void CreateHFMC(HFMT T,HFMC C);void Initialization(HFMT T,HFMC C);void Codei

4、ng(HFMC C);void Decodeing(HFMC C);void Showcodefile();void Showhfmt(HFMT T);int TreeDepth(HFMT T,int i);void print(HFMT T,int i,int a); 文件二:Initialization.c（初始化） #include "my.h"seqstack s;/初始化樹void In

5、itializeTree(HFMT T) int i; printf("請輸入要輸入的字符個數(shù)n(n應(yīng)大于1):"); scanf("%d",&n); for(i=0;i<2*n-1;i+)   T.weight=-1;  T.lchild=-1;  T.rchild=-1;  T.parent=-1;  T.data='0' /輸入樹void&#

6、160;InputTree(HFMT T) int i; for(i=0;i<n;i+)   printf("請輸入第%d個字符與權(quán)重:",i+1);  getchar();  scanf("%c %d",&T.data,&T.weight); /從樹數(shù)組中選取權(quán)值最小的兩個元素void Selectleast(HFMT T,int *p1,int *p2)

7、0;long min1,min2; int i; min1=min2=999999; for(i=0;i<2*n-1;i+)   if(T.parent=-1&&T.weight!=-1)   if(T.weight<min1)       min1=T.weight;    *p1=i;     f

8、or(i=0;i<2*n-1;i+)     if(T.parent=-1&&T.weight!=-1)   if(T.weight<min2&&i!=*p1)       min2=T.weight;    *p2=i;    /構(gòu)建哈夫曼樹void CreateHFMT(HFMT T) in

9、t i,p1,p2; InitializeTree(T); InputTree(T); for(i=n;i<2*n-1;i+)   Selectleast(T,&p1,&p2);  T.weight=Tp1.weight+Tp2.weight;  T.lchild=p1;  T.rchild=p2;  Tp1.parent=Tp2.parent=i; /入棧void push(char x)&#

10、160;s.top+; s.datas.top=x;/構(gòu)建哈夫曼樹編碼庫遞歸調(diào)用函數(shù)void hfmc(HFMT T,int i) int j; j=T.parent; if(j!=-1)   if(i=Tj.lchild)   push('0');  if(i=Tj.rchild)   push('1');  hfmc(T,j); /構(gòu)建哈夫曼

11、樹編碼庫void CreateHFMC(HFMT T,HFMC C) int i,j; s.top=-1; for(i=0;i<n;i+)   hfmc(T,i);  C.data=T.data;  for(j=0;s.top!=-1;j+)     C.codej=s.datas.top;   s.top-;    C.codej

12、='0' /初始化函數(shù)void Initialization(HFMT T,HFMC C) FILE *out; int i; CreateHFMT(T); CreateHFMC(T,C); if(out=fopen("hfmt.dat","w")!=NULL)   fprintf(out,"%d",n);  for(i=0;i<n;i+) &#

13、160; fprintf(out,"%c",T.data);  for(i=0;i<2*n-1;i+)   fprintf(out,"n%d %d %d %d",T.weight,T.parent,T.lchild,T.rchild);  else   printf("n文件打開錯誤!");  return;  fclose(out); pr

14、intf("n初始化完畢!");  文件三:Codeing.c（編碼） #include "my.h"/編碼函數(shù)void Codeing(HFMC C) FILE *in,*out; char zwMAXLEN,codeMAXLEN_1; int i=0,j,k,c_len,error=1; c_len=0;/編碼正文初始長度置零 /打開文件toberrans.dat并讀取正文存入正文數(shù)組zw if(in=

15、fopen("tobetrans.dat","r")!=NULL)   zw=fgetc(in);  while(feof(in)=0)     i+;   zw=fgetc(in);    zw='0'  else    printf("n文件打開錯誤!");  retu

16、rn;  fclose(in); /進(jìn)行編碼 for(i=0;zw!='0'i+)   error=1;/錯誤置為真  for(j=0;j<n;j+)     if(zw=Cj.data)       for(k=0;Cj.codek!='0'k+)        

17、60;codec_len=Cj.codek;     c_len+;        error=0;/若編碼庫存在匹配字符，則錯誤為假    break;       if(error=1)   break;  codec_len='0' if(error)  &

18、#160;printf("n編碼錯誤,請重新檢查!");  return;  else   printf("n正文為:%s",zw);  printf("n編碼為:%s",code);  /打開文件codefile.dat，并將編碼正文寫入文件  if(out=fopen("codefile.dat","w")!=NULL)   fpri

19、ntf(out,"%s",code);  else     printf("n打開文件錯誤!");   return;    fclose(out);  printf("n編碼成功!");   文件四:Decodeing.c（譯碼） #include "my.h"/譯碼函數(shù)void Decodein

20、g(HFMC C) FILE *in,*out; int i,j,k,c_max,c_len,dq,dq_len,flag,error=0;/error初始狀態(tài)為假 char codeMAXLEN_1,aMAXLEN,zwMAXLEN; code0='0' /打開文件codefile.dat，讀取編碼正文寫入內(nèi)存，存入數(shù)組code if(in=fopen("codefile.dat","r")!=NULL)   

21、;fscanf(in,"%s",code);  else   printf("n打開文件錯誤!");  return;  fclose(in); /求編碼正文長度c_len for(i=0;code!='0'i+); c_len=i; if(c_len=0)  error=1;/錯誤情況1 /求編碼庫最長編碼長度c_max c_max=0; for(i=0;i&

22、lt;n;i+)   for(j=0;C.codej!='0'j+);  if(c_max<j)   c_max=j;  /進(jìn)行譯碼 dq=0; /dq用來記錄code數(shù)組的讀取位置 k=0;  /k用來記錄zw數(shù)組讀取位置 while(dq<c_len)   flag=1;  dq_len=c_max;  for(i=dq,j=0;j&l

23、t;c_max;i+,j+)   aj=code;  aj='0'  while(flag&&!error)/若無錯誤且flag為1則繼續(xù)循環(huán)     for(i=0;i<n;i+)       if(strcmp(a,C.code)=0)         zwk=C.data;&

24、#160;    k+;     flag=0;     break;       /若找到編碼庫里匹配的編碼，則結(jié)束循環(huán)   if(flag)       dq_len-;    adq_len='0'  

25、60;/未找到則將當(dāng)前長度減一，繼續(xù)尋找   if(dq_len<1)    error=1;/譯碼錯誤情況2    dq=dq+dq_len;/編碼正文當(dāng)前讀取位置改變  zwk='0'/在zw數(shù)組的最后一個位置添加字符串結(jié)束符  if(error)   printf("n譯碼錯誤，請重新檢查!");  return;  else&#

26、160;  /打印編碼正文以及譯碼正文  printf("n編碼為:%s",code);  printf("n譯碼為:%s",zw);  /打開文件textfile.dat，將譯碼正文即數(shù)組zw寫入文件  if(out=fopen("textfile.dat","w")!=NULL)   fprintf(out,"%s",zw);  else

27、60;    printf("n打開文件錯誤!");   return;    fclose(out);  printf("n譯碼成功!");   文件五:Showcodefile.c（顯示代碼文件） #include "my.h"/顯示編碼文件內(nèi)容函數(shù)void Showcodefile() FILE *in; cha

28、r codeMAXLEN_1; int i; code0='0' /打開文件 if(in=fopen("codefile.dat","r")!=NULL)   fscanf(in,"%s",code);  else   printf("n打開文件錯誤!");  return;  fclose(in); /打印內(nèi)容

29、 printf("n代碼文件內(nèi)容為:"); for(i=0;code!='0'i+)   if(i%50=0)   printf("n");  printf("%c",code);   文件六:Showhfmt.c（以凹入法顯示哈夫曼樹） #include "my.h"/求哈夫曼樹深度函數(shù)int TreeDepth(HFMT T,i

30、nt i) int ldep,rdep; if(T.lchild=-1)  return 1; else   ldep=TreeDepth(T,T.lchild);  rdep=TreeDepth(T,T.rchild);  if(ldep>rdep)   return ldep+1;  else   return rdep+1; 

31、/顯示哈夫曼樹遞歸調(diào)用函數(shù)void print(HFMT T,int i,int a) int j; if(i>n-1)  printf("n%6d",T.weight); else  printf("n%6c",T.data); for(j=0;j<a;j+)  printf(""); if(T.lchild!=-1)   a-;&#

32、160; print(T,T.lchild,a);  print(T,T.rchild,a); /顯示哈夫曼樹void Showhfmt(HFMT T) int dep; if(n=0)   printf("n哈夫曼樹不存在!請初始化.");  return;  else   printf("凹入表示法:(單位長度  )");  

33、;dep=TreeDepth(T,2*n-2);  print(T,2*n-2,dep);   測試數(shù)據(jù)    根據(jù)實(shí)驗(yàn)要求，在tobetrans.dat中輸入"THIS PROGRAM IS MY FAVORITE"，字符集和其頻度如下：字符_ABCDEFGHIJKLM頻度1866423223210321154757153220字符NOPQRSTUVWXYZ 頻度20561925051553010112212  程

34、序調(diào)用文件:hfmt.dat      （哈夫曼樹存放文件）codefile.dat  （編碼存放文件）textfile.dat  （譯碼存放文件）tobetrans.dat （將編碼正文存放文件） 提供已測試的測試數(shù)據(jù): 文件一:hfmt.dat內(nèi)容:27 abcdefghijklmnopqrstuvwxyz186 50 -1 -164 44 -1 -123 36 -1 -122 36 -1 -132 38 -1 -1103 47 -1 -121 34 -1 -115 32 -1 -147 41 -1 -157 43 -1 -11 27 -1 -15 30 -1&