huffman树.doc

#include #include #includeint m,s1,s2;typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char * HuffmanCode;void Select(HuffmanTree HT,int n) int i,j; for(i=1;i=n;i+) if(HTi.parent=0) s1=i; break; for(j=i+1;j=n;j+) if(HTj.parent=0) s2=j; break; for(i=1;iHTi.weight) if(s2!=i) s1=i; for(j=1;jHTj.weight) if(s1!=j) s2=j; if(s1s2) int temp=s1; s1=s2; s2=temp;void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) int i;char *cd;int p;int cdlen;if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); for (i=1; i=n; i+) HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; printf(构造过程显示：n); for(i=1;i=m;i+) printf(%4d%4d%4d%4d%4dn,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild);system(pause);for(i=n+1;i=m;i+)/求hafuman编码 Select(HT,i-1); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; cd = (char *)malloc(n*sizeof(char);p=m;cdlen=0;for(i=1;i=m;i+) HTi.weight=0;while(p) if(HTp.weight=0) HTp.weight=1; if(HTp.lchild!=0) p=HTp.lchild; cdcdlen+=0; else if(HTp.rchild=0) HCp=(char *)malloc(cdlen+1)*sizeof(char); cdcdlen=0; strcpy(HCp,cd); else if(HTp.weight=1) HTp.weight=2; if(HTp.rchild!=0) p=HTp.rchild; cdcdlen+=1; else HTp.weight=0; p=HTp.parent; -cdlen; int main()HuffmanTree HT;HuffmanCode HC;int *w,n,i;printf(请输入节点数：n);scanf(%d,&n);HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode);w=(int *)malloc(n*sizeof(int);printf(请输入节点的权值：n);for(i=0;in;i+) scanf(%d,&wi);HuffmanCoding(HT,HC,w,n); pr