哈夫曼树构造编码译码源程序.doc

#includestdio.h#define maxbit 10 /*定义哈夫曼编码最大长度*/#define maxvalue 10000 /*定义最大权值常量*/#define maxnodenumber 100 /*定义结点最大数目常量*/typedef struct /*定义结点结构*/ float weight; char data; int parent,lchild,rchild; htnode;typedef struct /*定义保存一个叶子结点哈曼编码的结构*/int bitmaxbit; int start; hcodetype;hcodetype cdmaxbit;void main() /*主函数*/void huffmancode(htnode ht,int n); void huffmandecode(hcodetype cd,htnode ht,int n); htnode htmaxnodenumber; int i,j,k1,k2,n,a; float m1,m2; printf( 哈夫曼树的构造及应用n); printf(请输入叶子数目 n: ); /*提示输出叶子结点个数*/ scanf(%d,&n); printf(Please input data and weight:n); /*提示输出各叶子结点的权值*/ for(i=0;i2*n-1;i+) hti.weight=0.00000; hti.data=0; hti.parent=0; hti.lchild=0; hti.rchild=0; for(i=0;in;i+) fflush(stdin); scanf(%c %f,&hti.data,&hti.weight); for(i=0;in-1;i+) m1=maxvalue; m2=maxvalue; k1=0;k2=0; for(j=0;j=0.000001) m2=m1;k2=k1; m1=htj.weight;k1=j; else if(htj.parent=0&(m2-htj.weight)=0.000001) m2=htj.weight;k2=j; htk1.parent=n+i; htk2.parent=n+i; htn+i.weight=htk1.weight+htk2.weight; htn+i.lchild=k1; htn+i.rchild=k2; printf(n构造的哈夫曼树如下：n); printf(n);printf(数组下标 lchild data weight rchlid parent n); for(i=0;i2*n-1;i+) printf( %d %d %c %f %d %dn,i,hti.lchild,hti.data,hti.weight,hti.rchild,hti.parent); printf(The data and the bits is as follows:n); huffmancode(ht,n); /*调用函数*/ printf(请输入一组需要译码的二进制报文(单个数字之间请用空格隔开，如1011应该输入1 0 1 1 ，以-1结尾)：n); huffmandecode(cd,ht,n); /*调用函数*/ void huffmancode(htnode ht,int n)/*对具有n个叶子结点的哈夫曼树ht，求所有叶子结点的哈夫曼编码并输出*/int i,j,c,p,m,k; char ch100; hcodetype cd100; for(i=0;in;i+) c=i;j=maxbit; do j-;p=htc.parent;if(htp.lchild=c) cdi.bitj=0;else cdi.bitj=1;c=p; while(p!=0); cdi.start=+j; for(i=0;in;i+) printf(data:%c bits:,hti.data); for(j=cdi.start;jmaxbit;j+) printf(%d,cdi.bitj); printf(n); void huffmandecode(hcodetype cd,htnode ht,int n) int i,c,p,b;int endflag=-1;i=2*n-2;scanf(%d,&b);printf(译码的结果如下：n);while(b!=endflag) if(b=0) i=hti.lchild; else i=hti.rchild;if(hti.lchild=0) printf