资源描述：
《c语言构建哈夫曼树(附运行结果图).docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、#include#include#includeintm,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
2、+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){//算法6.13//w存放n个字符的权值(均>0)，构造哈夫曼
3、树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].rchi
4、ld=0;}puts("哈夫曼树的构造过程如下所示：");printf("HT初态:结点weightparentlchildrchild");for(i=1;i<=m;i++)printf("%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].par
5、ent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;printf("select:s1=%ds2=%d",s1,s2);printf("结点weightparentlchildrchild");for(j=1;j<=i;j++)printf("%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild,HT[j].rchild);}//------无栈非递归遍历哈夫曼树，求哈夫曼编码cd=(char*)mallo
6、c(n*sizeof(char));//分配求编码的工作空间p=m;cdlen=0;for(i=1;i<=m;++i)//遍历哈夫曼树时用作结点状态标志HT[i].weight=0;while(p){if(HT[p].weight==0){//向左HT[p].weight=1;if(HT[p].lchild!=0){p=HT[p].lchild;cd[cdlen++]='0';}elseif(HT[p].rchild==0){//登记叶子结点的字符的编码HC[p]=(char*)malloc((cdlen+1)*sizeof(char));cd[cdlen]=' ';strcpy(
7、HC[p],cd);//复制编码(串)}}elseif(HT[p].weight==1){//向右HT[p].weight=2;if(HT[p].rchild!=0){p=HT[p].rchild;cd[cdlen++]='1';}}else{//HT[p].weight==2，退回退到父结点，编码长度减1HT[p].weight=0;p=HT[p].parent;--cdlen;}}}//HuffmanCodingvoidmain(){HuffmanTr
