HDU1053 Entropy 哈夫曼树

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1053

认真读题，别怕题长，此题考查的就是哈夫曼树并求出最小编码值，注意每一次要将数组清0，否则会出错！

AC代码：

#include<iostream>
#include<string.h>
using namespace std;
#define M 1000000
struct node
{int l,r,data,p;
}ha[100];
int main()
{//freopen("d:\\1.txt","r",stdin);char s[10000];int a[30],b[30];while(scanf("%s",s)!=EOF){if(strcmp(s,"END")==0)break;memset(a,0,sizeof(a));  //注意将A清零int i,j,m1,m2,x1,x2,s1=0,h;int l=strlen(s);for(i=0;i<l;i++){if(s[i]!='_')a[s[i]-64]++;elsea[0]++;}int k=0;for(i=0;i<30;i++){if(a[i])b[++k]=a[i];}//构造哈夫曼树memset(ha,0,sizeof(ha));for(i=1;i<=k;i++)ha[i].data=b[i];for(i=1;i<k;i++)//控制扫描的次数
        {m1=m2=M;x1=x2=0;for(j=1;j<k+i;j++){if(ha[j].data<m1&&ha[j].p==0){m2=m1;x2=x1;m1=ha[j].data;x1=j;}else if(ha[j].data<m2&&ha[j].p==0){m2=ha[j].data;x2=j;}}ha[k+i].data=ha[x1].data+ha[x2].data;ha[k+i].l=x1;ha[k+i].r=x2;ha[x1].p=k+i;ha[x2].p=k+i;}if(k==1)//当只有一种字符的时候s1=b[1]*1;else{for(i=1;i<=k;i++){j=i;int x=0;for(;;){h=ha[j].p;j=h;x++;if(h==2*k-1)break;                    }s1+=b[i]*x;}}printf("%d %d %.1lf\n",l*8,s1,l*8*1.0/s1);}return 0;
}