哈夫曼树的编码与译码.doc

《哈夫曼树的编码与译码.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#definen4#definem2*n-1#definemaxval32769typedefstruct{floatweight;intlchild,rchild,parent;charch;}huftree;typedefstruct{charbits[n];intstart;}codetype;codetypecode[n];huftreetree[m];voidhufman(huftreetree[])//创建哈夫曼树{inti,j,p1,p2;charch;floatsmall1,small2,f;for(i=

2、0;i

3、产生n-1个新结点{p1=0,p2=0;small1=maxval;small2=maxval;for(j=0;j<=i-1;j++)//找出权值最小的两个根结点{if(tree[j].parent==0){if(tree[j].weight

4、的新结点为最小权与次小权的双亲tree[p2].parent=i+1;tree[i].lchild=p1+1;tree[i].rchild=p2+1;tree[i].weight=tree[p1].weight+tree[p2].weight;}}voidcreathufcode(codetypecode[])//由哈夫曼数构建哈夫曼编码{inti,c,p;codetypecd;for(i=0;i

5、d.start]='0';}elsecd.bits[cd.start]='1';c=p;p=tree[p-1].parent;}code[i]=cd;}}voiddecode(codetypecode[],huftreetree[])//依次读入电文，根据哈夫曼树译码{inti,b;intflag=-1;i=m-1;printf("请输入电文编码：");scanf("%d",&b);while(b!=flag){if(b==0){i=tree[i].lchild-1;}elsei=tree[i].rchild-1;if(tree[i].lchild==0)//找到叶节点，输出对应字符{pr

6、intf("译码后对应的字符:%c",tree[i].ch);printf("译码后字符对应的权值:%f",tree[i].weight);i=m-1;}scanf("%d",&b);}if(tree[i].lchild!=0)printf("error");}voidmain(){hufman(tree);creathufcode(code);decode(code,tree);}