数据结构：哈夫曼树 哈夫曼树的定义： 哈夫曼树的定义与树类似，分为左子树指针和右子树指针，在此基础上额外增加了一个父节点指针，便于叶子节点到根节点遍历，逆向求得哈夫曼编码。 构造哈夫曼树： Select函数： 用于在一组数据中选出两个最小的数。 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0 && i!=(*s1)) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0 && i!=(*s1)) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s2=min; } 构造哈夫曼树： void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) { int m,i,s1,s2; m=2*n-1; //总共的结点数 *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1; i<=n; i++) //1-n号存放叶子结点，初始化 { (*ht)[i].weight=w[i]; (*ht)[i].LChild=0; (*ht)[i].parent=0; (*ht)[i].RChild=0; } for(i=n+1; i<=m; i++) //非叶子结点的初始化 { (*ht)[i].weight=0; (*ht)[i].LChild=0; (*ht)[i].parent=0; (*ht)[i].RChild=0; } //printf(“\哈夫曼树为: ”); for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树 { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2*/ Select(ht,i-1,&s1,&s2); (*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(“%d (%d, %d) ”,(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight); } //printf(” ”); } 哈夫曼编码： 从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码 int CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) { char *cd; //定义的存放编码的空间 int a[100]; int i,start,p,w=0; unsigned int c; hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针 cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间 cd[n-1]=’0′; //从右向左逐位存放编码，首先存放编码结束符 for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码 { a[i]=0; start=n-1; //起始指针位置在最右边 for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码 { if( (*ht)[p].LChild==c) { cd[–start]=’1′; //左分支标1 a[i]++; } else { cd[–start]=’0′; //右分支标0 a[i]++; } } hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(hc[i],&cd[start]); //将cd复制编码到hc } free(cd); // for(i=1; i<=n; i++) // printf(” 权值为%d的哈夫曼编码为：%s ”,(*ht)[i].weight,hc[i]); for(i=1; i<=n; i++) w+=(*ht)[i].weight*a[i]; return w; //printf(” 带权路径为：%d ”,w); } 完整源代码： 运行结果为： 
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/38053.html
