#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); /system(pause); for(i=1;i=n;i+) printf(%4d %4d %sn,i,wi-1,HCi); system(pause); return 0;