Huffman源程序.doc

#include#include#include#define error 0#define ok 1typedef struct unsigned int weight; unsigned int parent,lchild,rchild;htnode,*huffmantree;typedef char*huffmancode;int n,s1,s2;void select(huffmantree &ht,int n,int &s1,int &s2) int i=1; while(hti.parent!=0) i+; s1=i; i+; while(hti.parent!=0) i+; s2=i; for(;i=n;i+) if(hti.parent=0) if(hti.weighthts1.weight) s2=s1; s1=i; else if(hti.weighthts2.weight) s2=i; void huffmancoding(huffmantree &ht,huffmancode &hc, int *w,int n) int c,m,f,i,start; char *cd; if(n=1) return; m=2*n-1; ht=(huffmantree)malloc(m+1)*sizeof(htnode); /0单元未用 huffmantree p=ht+1; /w+; for(i=1;iweight=*w; p-parent=0; p-rchild=0; p-lchild=0; for(;iweight=0; p-parent=0; p-rchild=0; p-lchild=0; for(i=n+1;i=m;i+) /建huffman树(从叶子后开始存内结点) select(ht,i-1,s1,s2); /在ht1i-1选择 hts1.parent=i; hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts1.weight+ hts2.weight; hc=(huffmancode)malloc(n+1)*sizeof(char*); /分配n个字符编码的头指针向量 cd=(char*) malloc(n*sizeof(char); /分配求编码的工作空间(n) cdn-1=0; /编码结束符（从cd0cdn-1为合法空间） for(i=1;i=n;+i) start=n-1; /编码结束符位置 for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)/从叶子到根逆向求编码 if(htf.lchild=c) cd-start=0; else cd-start=1; /c=f; hci=(char *)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间 strcpy(hci,&cdstart); free(cd); for(i=1;i=m;i+) printf(%d %d %d %d %dn,i,hti.weight,hti.parent,hti.lchild,hti.rchild); system(pause); /huffmancodingint main() int *w,i; huffmantree ht; huffmancode hc; printf(output:n); printf(请输入叶子节点数：n); scanf(%d,&n); w=(int *)malloc(n*sizeof(int); hc=(huffmancode)malloc(n*sizeof(huffmancode); printf(请输入各叶子节点的权数：n); for(i=1;i=n;i+) scanf(%d,&wi-1); huffmancoding(ht,hc,w,n); printf(输出编码结果：n); /s