本文主要是介绍poj 1521Entropy（哈弗曼编码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天上机课写了这道题，已经是上上周留的作业了，有几天没刷算法题了，哈弗曼编码，贪心求解。。。
思路：
就是建立一个二维数组，一个保存权值w，另一个保存父节点坐标f，然后分别找到权值最小的两个点，生成
一个新的节点加入该数组中，将这两个最小的点从数组中删除一直这样循环，直到找不到两个没有父节点的点为止，就
是说到最后只有一个节点没有父节点。注意输入的字母只有一个的情况，我第一次提交wa就是在这个地方错误的。
构造哈弗曼树的方法是我从网上看来的，觉得这个方法挺好的，寻找两个最小的值时可以用m1，m2来表示，遍历数
组，然后就找出了最小的两个数。一个含有n个数的数组构造哈弗曼树后会变成2*n-1个节点
贴代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
typedef struct
{int w;int f;
}node;
node H[200];
char a[1000];
int b[40];
int huffmantree(int n)//构造哈弗曼树
{int i,j,m1,m2,x1,x2;//m1，m2分别表示当前数组中最小的两个权值，x1，x2分别表示权值最小的两个值的标号for(i=0; i<n-1; i++){m1=m2=INT_MAX;//初始化为最大值x1=x2=0;for(j=0; j<n+i; j++){if(H[j].w<m1&&H[j].f==-1){m2=m1;x2=x1;m1=H[j].w;x1=j;} else if(H[j].w<m2&&H[j].f==-1){m2=H[j].w;x2=j;}}H[x1].f=n+i;//记下父节点H[x2].f=n+i;///记下父节点H[n+i].w=m1+m2;//为新的节点赋值H[n+i].f=-1;//其父节点初始化为-1}//for(i=0; i<2*n-1; i++)//{//printf("%d ",H[i].w);// printf(" F:%d ",H[i].f);//}
// printf("\n");int sum=0;for(i=0; i<n; i++){// printf(" F:%d ",H[i].f);j=i;int s=0;if(H[i].f==-1)continue;while(H[j].f!=-1){j=H[j].f;s++;}//printf(" %d ",s);sum+=s*H[i].w;}//printf("sum=%d\n",sum);return sum;
}
int main()
{int len,i,j,k;while(scanf("%s",a),strcmp("END",a)!=0){k=0;len=strlen(a);memset(b,0,sizeof(b));for(i=0; i<len; i++){b[a[i]-65]++;}for(i=0; i<2*30-1; i++){H[i].w = 0;H[i].f = -1;}for(i=0; i<32;i++){if(b[i]!=0){H[k++].w=b[i];}}// for(i=0; i<k; i++)// {// printf("%d ",H[i].w);//}//printf("\n");int sum=huffmantree(k);if(sum==0)sum=1*len;int s=8*len; double ans=(8*len*1.0)/sum;printf("%d %d %.1f\n",s,sum,ans); }return 0;
}
今天11级的学长回校了，开了个交流会，学长们都挺优秀的，有保研的，有考研的，有工作的，讲的都挺
棒的，这都是努力换来的结果，没有人可以随随便便成功，但是听到他们讲的考研经历，a_jie似乎感受到了考研的
难度，大概想着自己完全做不了这些事情，其实，考研并没有想象的那么难，最难的是自己能不能坚持，知不知道努
力，学习这件事情，只要努力学还是蛮单的，真怕她不知道学习。。。只能祈祷这次她真的觉悟了。。。
这篇关于poj 1521Entropy（哈弗曼编码）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
