_哈夫曼树编码.doc

/*哈夫曼树编码*/ #include #define n 4 #define m 2*n-1 #define MAXVAL 999 typedef int datatype; typedef struct float weight; char c; datatype lchild,rchild,parent; hufmtree; hufmtree treem+1; typedef struct char bitsn;/*位串*/ char ch;/*字符*/ int start;/*编码在位串中的位置*/ codetype; codetype coden+1; void HUFFMAN( )/*构造哈夫曼树*/ int i,j,p1,p2; char c; float small1,small2,f; for (i=1; i=m;i+)/*对2n-1个结点初始化*/ treei.parent=0; treei.lchild=0; treei.rchild=0; treei.weight=0.0; treei.c=0; printf(输入字符：); for(i=1;i=n;i+) c=getchar(); treei.c=c; printf(输入权值：); for(i=1; i=n;i+)/*将n个权值放入结构数组tree的前n个分量中*/ scanf(%f,&f); treei.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 (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;/*将根为treep1和treep2的两棵树合并，使其成为新结点treei的左右孩子*/ treep2.parent=i; treei.lchild=p1; treei.rchild=p2; treei.weight=treep1.weight+treep2.weight; void HUFFMANCODE(hufmtree tree,codetype code) int i,j,c,p; codetype cd; for (i=1;i=n;i+) cd.start=n; c=i;/*从叶子结点出发向上回溯*/ cd.ch=treei.c; p=treei.parent;/*treep是treei的双亲*/ for (j=0;j=1;i-) printf(%d,i); printf(%10d,treei.parent); printf(%10d,treei.lchild); printf(%10d,treei.rchild); printf(%10.2fn,treei.weight); void PRINTCODE(codetype code) int i,j; for(i=1;i=n;i+) printf(%5c,codei.ch); for(j=0;jn;j+) printf(%c,codei.bitsj); printf(n); main( ) HUFFM