《哈夫曼树的编码与译码.doc》由会员分享,可在线阅读,更多相关《哈夫曼树的编码与译码.doc(4页珍藏版)》请在三一文库上搜索。
1、#include#include#define n 4#define m 2*n-1#define maxval 32769typedef structfloat weight;int lchild,rchild,parent; char ch;huftree;typedef structchar bitsn;int start;codetype;codetype coden;huftree treem;void hufman(huftree tree)/创建哈夫曼树 int i,j,p1,p2; char ch; float small1,small2,f; for(i=0;im;i+)/初
2、始化所有结点 treei.parent=0; treei.lchild=0; treei.rchild=0; treei.weight=0.0; printf(请输入结点的权值:n); for(i=0;in;i+)/输入n个结点的权值 scanf(%f,&f);treei.weight=f; printf(请输入结点的字符:n);scanf(%c,&ch); for(i=0;in;i+)/输入n个结点的权值 scanf(%c,&ch);treei.ch=ch; for(i=n;im;i+)/进行n-1次合并,产生n-1个新结点 p1=0,p2=0;small1=maxval;small2=ma
3、xval;for(j=0;j=i-1;j+)/找出权值最小的两个根结点if(treej.parent=0)if(treej.weightsmall1)/改变最小权与次小权的位置small2=small1;small1=treej.weight;p2=p1;p1=j;/锁定最小权的位置 elseif(treej.weightsmall2)small2=treej.weight;p2=j;/锁定次小权的位置treep1.parent=i+1;/生成的新结点为最小权与次小权的双亲treep2.parent=i+1;treei.lchild=p1+1;treei.rchild=p2+1;treei.w
4、eight=treep1.weight+treep2.weight; void creathufcode(codetype code)/由哈夫曼数构建哈夫曼编码 int i,c,p; codetype cd; for(i=0;in;i+) cd.start=n; c=i+1; p=treei.parent; while(p!=0) cd.start-; if(treep-1.lchild=c) cd.bitscd.start=0; else cd.bitscd.start=1; c=p; p=treep-1.parent; codei=cd; void decode(codetype code
5、,huftree tree)/依次读入电文,根据哈夫曼树译码 int i,b; int flag=-1; i=m-1; printf(请输入电文编码:); scanf(%d,&b); while(b!=flag) if(b=0) i=treei.lchild-1; else i=treei.rchild-1; if(treei.lchild=0)/找到叶节点,输出对应字符 printf(译码后对应的字符:%cn,treei.ch); printf(译码后字符对应的权值:%f,treei.weight); i=m-1; scanf(%d,&b); if(treei.lchild!=0) printf(n errorn);void main()hufman( tree);creathufcode( code); decode( code, tree);