哈夫曼编码,构造树

1、单词theofatoandinthatheisatonforhisarebe频度1192677541518462450242195190181174157138124123# include # include# define N 50 /叶子结点数# define M 2*N-1 /数中结点数typedef structchar data5; /结点值int weight; /权重int parent;/双亲结点int lchild;/左孩子结点int rchild;/右孩子结点HTNode;typedef structchar cdN; /存放哈夫曼码int start;HCode;voi

2、d CreateHT(HTNode ht ,int n)/构造哈夫曼树int i,k,lnode,rnode;int min1,min2;for (i=0;i2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;/所有结点的相关初值是-1for (i=n;i2*n-1;i+)/构造哈夫曼树min1=min2=32767;/lnode和rnode为最小权重的两个结点位置 lnode=rnode=-1;for(k=0;k=i-1;k+)if (htk.parent=-1)/只在尚未构造二叉树的结点中找if (htk.weightmin1)min2=min1;rn

3、ode=lnode;min1=htk.weight;lnode=k;else if (htk.weightmin2)min2=htk.weight; rnode=k; htlnode.parent=i; htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;void CreateHCode(HTNode ht,HCode hcd ,int n)/构造哈夫曼编码int i,f,c;HCode hc;for (i=0;in;i+)/根据哈夫曼树求哈夫曼编码hc.star

4、t=n;c=i;f=hti.parent;while (f!=-1)/循序直到树根结点if (htf.lchild=c)/处理左孩子结点hc.cdhc.start-=0;else /处理右孩子结点hc.cdhc.start-=1;c=f;f=htf.parent;hc.start+;/start指向哈夫曼编码最开始字符hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码int i,k;int sum=0,m=0,j;printf(输出哈夫曼编码：n); /输出哈夫曼编码for(i=0;in;i+)j=0; printf(%s:t,

5、hti.data);for (k=hcdi.start;k=n;k+)printf(%c,hcdi.cdk);j+;m+=hti.weight;sum+=hti.weight*j;printf(n);printf(n平均长度=%gn,1.0*sum/m);void main()int n=15,i;char *str=The,of,a,to,and,in,that,he ,is,at,on,for,His,are,be;int fnum=1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123;HTNode htM; HCode hcdN; for (i=0;in;i+) strcpy(hti.data,stri); hti.weight=fnumi;