哈夫曼树及哈夫曼编码译码的实现

哈夫曼树及哈夫曼编码译码的实现程序如下：#includestdio.h#includestring.h#includeconio.h#includestdlib.hintmaxline=0;charxx[50][80];intl,L;typedefstruct/*定义结构体*/{intweight;intparent;intlchild,rchild;}tree;treeb[57];intReadDat(void){FILE*fp;inti=0;char*p;if((fp=fopen(in.txt,r))==NULL)return1;while(fgets(xx[i],80,fp)!=NULL){p=strchr(xx[i],'\n');if(p)*p=0;i++;}maxline=i;fclose(fp);return0;}intpinlv(inta[]){inti,j;intL;for(i=0;imaxline;i++){L=strlen(xx[i]);for(j=0;jL;j++)if(xx[i][j]=97&&xx[i][j]=122)a[xx[i][j]-97]++;elseif(xx[i][j]==32)a[26]++;elseif(xx[i][j]==44)a[27]++;elseif(xx[i][j]==46)a[28]++;}}smax(inta[],intlow,inthigh,intmax[]){intmid,M[2],N[2];mid=(high+low)/2;if(high-low==1){if(a[low]a[high]){max[0]=low;max[1]=high;}else{max[0]=high;max[1]=low;}}elseif(high-low==0){max[0]=high;max[1]=57;}else{smax(a,low,mid,max);M[0]=max[0];M[1]=max[1];smax(a,mid+1,high,max);N[0]=max[0];N[1]=max[1];if(a[M[0]]=a[N[0]]&&a[M[1]]=a[N[0]]){max[0]=M[0];max[1]=M[1];}elseif(a[M[0]]=a[N[0]]&&a[M[1]]a[N[0]]){max[0]=M[0];max[1]=N[0];}elseif(a[M[0]]a[N[0]]&&a[M[0]]=a[N[1]]){max[0]=N[0];max[1]=M[0];}elseif(a[M[0]]a[N[0]]&&a[M[0]]a[N[1]]){max[0]=N[0];max[1]=N[1];}}}bhtree(inta[]){inti,j;intmax[2];intc[58]={0};c[57]=4000;l=0;for(i=0;i29;i++){if(a[i]!=0){b[i].weight=a[i];b[i].lchild=0;b[i].rchild=0;c[i]=a[i];l++;}elseif(a[i]==0){b[i].weight=a[i];b[i].lchild=0;b[i].rchild=0;c[i]=4000;}}for(i=29;i29+l-1;i++){smax(c,0,i-1,max);c[max[0]]=4000;c[max[1]]=4000;b[i].weight=b[max[0]].weight+b[max[1]].weight;b[i].lchild=max[0];b[i].rchild=max[1];b[max[0]].parent=i;b[max[1]].parent=i;c[i]=b[i].weight;}}bma(inti,intj,intn,intM[]){intt;t=b[n].parent;if(n==29+l-2)M[j]=2;elseif(n==b[t].lchild){M[j]=0;n=t;bma(i,j+1,n,M);}elseif(n==b[t].rchild){M[j]=1;n=t;bma(i,j+1,n,M);}}main(){inta[29]={0};inti,j,n,k=0,p;intm[29][10];intM[10];FILE*fp;clrscr();for(i=0;i29;i++)for(j=0;j10;j++)m[i][j]=3;ReadDat();pinlv(a);bhtree(a);fp=fopen(out.txt,w);for(i=0;imaxline;i++){L=strlen(xx[i]);for(j=0;jL;j++)fprintf(fp,%c,xx[i][j]);fprintf(fp,\n);}for(i=0;i29;i++){if(a[i]!=0){for(p=0;p10;p++)M[p]=3;k=0;n=i;j=0;bma(i,j,n,M);for(p=0;p10;p++)if(M[p]2)k++;for(p=k-1;p=0;p--)m[i][k-1-p]=M[p];}}for(i=0;i26;i++)if(a[i]!=0){fprintf(fp,%c:,97+i);for(j=0;j10;j++)if(m[i][j]2)fprintf(fp,%d,m[i][j]);fprintf(fp,\n);}if(a[26]!=0){fprintf(fp,:);for(j=0;j10;j++)if(m[26][j]2)fprintf(fp,%d,m[26][j]);fprintf(fp,\n);}if(a[27]!=0){fprintf(fp,,:);for(j=0;j10;j++)if(m[27][j]2)fprintf(fp,%d,m[27][j]);fprintf(fp,\n);}if(a[28]!=0){fprintf(fp,.:);for(j=0;j10;j++)if(m[28][j]2)fprintf(fp,%d,m[28][j]);fprintf(fp,\n);}for(i=0;imaxline;i++){L=strlen(xx[i]);for(j=0;jL;j++){if(xx[i][j]=97&&xx[i][j]=122){k=xx[i][j]-97;for(p=0;p10;p++)if(m[k][p]2)fprintf(fp,%d,m[k][p]);}elseif(xx[i][j]==32){for(p=0;p10;p++)if(m[26][p]2)fprintf(fp,%d,m[26][p]);}elseif(xx[i][j]==44){for(p=0;p10;p++)if(m[27][p]2)fprintf(fp,%d,m[27][p]);}elseif(xx[i][j]==46){for(p=0;p10;p++)if(m[28][p]2)fprintf(fp,%d,m[28][p]);}}fprintf(fp,\n);}}实验结果：