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

《哈夫曼树及哈夫曼编码译码的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、哈夫曼树及哈夫曼编码译码的实现程序如下：#include"stdio.h"#include"string.h"#include"conio.h"#include"stdlib.h"intmaxline=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

2、],80,fp)!=NULL){p=strchr(xx[i],'');if(p)*p=0;i++;}maxline=i;fclose(fp);return0;}intpinlv(inta[]){inti,j;intL;for(i=0;i=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]++;

3、}}smax(inta[],intlow,inthigh,intmax[]){intmid,M[2],N[2];mid=(high+low)/2;if(high-low==1){if(a[low]

4、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[

5、2];intc[58]={0};c[57]=4000;l=0;for(i=0;i<29;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;i<29+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[ma

6、x[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};int

7、i,j,n,k=0,p;intm[29][10];intM[10];FILE*fp;clrscr();for(i=0;i<29;i++)for(j=0;j<10;j++)m[i][j]=3;ReadDat();pinlv(a);bhtree(a);fp=fopen("out.txt","w");for(i=0;i