_哈夫曼树编码

《_哈夫曼树编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*哈夫曼树编码*/#include#definen4#definem2*n-1#defineMAXVAL999typedefintdatatype;typedefstruct{floatweight;charc;datatypelchild,rchild,parent;}hufmtree;hufmtreetree[m+1];typedefstruct{charbits[n];/*位串*/charch;/*字符*/intstart;/*编码在位串中的位置*/}codetype;codetypecode[n+1];voidHUFFMAN()/*构造哈夫曼树*/

2、{inti,j,p1,p2;charc;floatsmall1,small2,f;for(i=1;i<=m;i++)/*对2n-1个结点初始化*/{tree[i].parent=0;tree[i].lchild=0;tree[i].rchild=0;tree[i].weight=0.0;tree[i].c='';}printf("输入字符：");for(i=1;i<=n;i++){c=getchar();tree[i].c=c;}printf("输入权值：");for(i=1;i<=n;i++)/*将n个权值放入结构数组tree的前n个分量中*/{scanf("%f",&

3、f);tree[i].weight=f;}for(i=n+1;i<=m;i++)/*选取最小权值和次小权值的两个根结点，并用p1、p2记住这二个根结点在tree中的位置*/{p1=0;p2=0;small1=MAXVAL;small2=MAXVAL;for(j=1;j<=i-1;j++)if(tree[j].parent==0)if(tree[j].weight

4、p2=j;}tree[p1].parent=i;/*将根为tree[p1]和tree[p2]的两棵树合并，使其成为新结点tree[i]的左右孩子*/tree[p2].parent=i;tree[i].lchild=p1;tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight;}}voidHUFFMANCODE(hufmtreetree[],codetypecode[]){inti,j,c,p;codetypecd;for(i=1;i<=n;i++){cd.start=n;c=i;/*从叶子结点出发向上回

5、溯*/cd.ch=tree[i].c;p=tree[i].parent;/*tree[p]是tree[i]的双亲*/for(j=0;j

6、("结点序号双亲结点左孩子右孩子权值");for(i=m;i>=1;i--){printf("%d",i);printf("%10d",tree[i].parent);printf("%10d",tree[i].lchild);printf("%10d",tree[i].rchild);printf("%10.2f",tree[i].weight);}}voidPRINTCODE(codetypecode[]){inti,j;for(i=1;i<=n;i++){printf("%5c",code[i].ch);for(j=0;j

7、ode[i].bits[j]);printf("");}}main(){HUFFMAN();PRINTHUM();HUFFMANCODE(tree,code);printf("字符编码为：");PRINTCODE(code);}