c语言构建哈夫曼树(附运行结果图).docx

#include<>#include<>#include<>intm,s1,s2;typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefchar*HuffmanCode;//动态分配数组存储哈夫曼编码表voidSelect(HuffmanTreeHT,intn){inti,j;for(i=1;i<=n;i++)if(!HT[i].parent){s1=i;break;}for(j=i+1;j<=n;j++)if(!HT[j].parent){s2=j;break;}for(i=1;i<=n;i++)if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;for(j=1;j<=n;j++)if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;}voidHuffmanCoding(HuffmanTree&HT,HuffmanCodeHC[],int*w,intn){////w存放n个字符的权值(均>0),构造哈夫曼树HT,//并求出n个字符的哈夫曼编码HCinti,j;char*cd;intp;intcdlen;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1;i<=n;i++){//初始化HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i<=m;i++){//初始化HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}puts("\n哈夫曼树的构造过程如下所示:");printf("HT初态:\n结点weightparentlchildrchild");for(i=1;i<=m;i++)printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);for(i=n+1;i<=m;i++){//建哈夫曼树//在HT[1..i-1]中选择parent为0且weight最小的两个结点,//其序号分别为s1和s2。Select(HT,i-1);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;printf("\nselect:s1=%ds2=%d\n",s1,s2);printf("结点weightparentlchildrchild");for(j=1;j<=i;j++)printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].p