#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>#definen6//n个叶子结点#definem2*n-1//m个结点#definesizesizeof(HTNode)typedefstruct{unsignedintweight;unsignedintparent;unsignedintlchild;unsignedintrchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//赫夫曼树初始化voidinithf(HuffmanTreeT){inti;HuffmanTreep;T=(HuffmanTree)malloc((m+1)*size);//动态分配数组孀储for(i=1;i<=m;p++,i++){p=T+i;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}}//输入权重voidinputhf(HuffmanTreeT){inti;intw;for(i=1;i<=n;i++){scanf("%d",&w);T[i].weight=w;}}//得到权值最小的两个结点voidselectmin(HuffmanTreeT,intk,int*s1,int*s2){inti=1;HuffmanTreep=T;intsmall1,small2;small1=p[i].weight;small2=small1;for(;i<=k;i++){if(T[i].parent==0)if(T[i].weight<small1){small2=small1;small1=T[i].weight;*s2=*s1;*s1=i;}elseif(T[i].weight<small2){small2=T[i].weight;*s2=i;}}}//建赫夫曼树voidcreathftree(HuffmanTreeT){inti,s1,s2;inithf(T);inputhf(T);for(i=n+1;i<=m;i++){selectmin(T,i-1,&s1,&s2);//得到权值最小的两个结点T[s1].parent=i;T[s2].parent=T[s1].parent;T[i].lchild=s1;T[i].rchild=s2;//建树T[i].weight=T[s1].weight+T[s2].weight;//加入新的权值}}//遍历赫夫曼树voidshow(HuffmanTreeT){inti;printf("weight\tparent\tlchild\trchild\n");for(i=1;i<=m;i++){printf("%d\t%d\t%d\t%d",(T+i)->weight,(T+i)->parent,(T+i)->lchild,(T+i)->rchild);printf("\n");}}//从叶子到根逆向求每个字符的赫夫曼编码voidcreathfcode(HuffmanTreeT,HuffmanCodeHC){inti,f,c,start;char*cd;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的指针数组cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';//编码结束符for(i=1;i<=n;i++)//逐个字符球求赫夫曼编码{start=n-1;//编码结束符位置for(c=i,f=T[i].parent;f!=0;c=f,f=T[f].parent)//从叶子到根逆向求编码if(T[f].lchild==c){start--;cd[start]='0';}else{start--;cd[start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符分配编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码（串）到HC}free(cd);}//s输出赫夫曼编码表voidprint(HuffmanTreeT,HuffmanCodeHC){inti;printf("weight\tcode\n");for(i=1;i<=n;i++){printf("%d\t%