HDU_1053 Entropy

#include <stdio.h>
#include <string.h>
#define N 128
#define inf 0x7fffffff
struct node
{
    int val;    //  
int left, right, parent;
}p[1000];
int f[N];    //        
int len[N];     //       

void hufuman(int n)
{
    int i, min1, min2, pos1, pos2, flag;
    for(i =0; i < n; i++)
    {
        p[i].val = f[i];
        p[i].parent =-1;
        p[i].left =-1;
        p[i].right =-1;
    }
    while(1)    //  Hufuman 
    {
        int mark1 =0, mark2 =0;
        min1 = min2 = inf;
        for(i =0; i < n; i++)        //            
        {
            if(p[i].parent ==-1&& p[i].val < min1)
            {
                if(min1 != min2)
                {
                    min2 = min1;
                    pos2 = pos1;
                    mark2 =1;
                }
                min1 = p[i].val;
                pos1 = i;
                mark1 =1;
            }
            elseif(p[i].parent ==-1&& p[i].val < min2)
            {
                min2 = p[i].val;
                pos2 = i;
                mark2 =1;
            }
        }
        if(mark1 ==0|| mark2 ==0)    //       ，      Hufuman 
break;
        p[n].val = min1 + min2;
        p[pos1].parent = n;
        p[pos2].parent = n;
        p[n].left = pos1;
        p[n].right = pos2;
        p[n].parent =-1;
        n++;
    }
    for(i =0; i < n; i++)
    {
        if(p[i].right !=-1|| p[i].left !=-1)        //         ，         ，            
break;
        flag = i;
        len[i] =1;
        while(p[flag].parent !=-1)
        {
            len[i]++;    //      （         Hufuman  ，      ）
            flag = p[flag].parent;    //  i    ，    
        }
    }
    return;
}
int main()
{
    char str[N];
    int data[N], i;
    while(gets(str) != NULL)
    {
        if(!strcmp(str, "END"))    break;

        memset(data, 0, sizeof(data));
        memset(f, 0, sizeof(f));

        for(i =0; i < strlen(str); i++)
            data[(int)str[i]]++;    //         

        int num =0;
        for(i =0; i <128; i++)
        {
            if(data[i] !=0)
            {
                f[num++] = data[i];    //       num，      f[]
            }
        }
        if(num ==1)
        {
            printf("%d %d 8.0
",strlen(str)*8, f[0]);
            continue;
        }
        hufuman(num);
        int sum =0;
        for(i =0; i < num; i++)
        {
            if(len[i] !=1)
                sum += (len[i]-1)*f[i];        //      = sum（             *        ）
        }
        printf("%d %d %.1f
", strlen(str)*8,sum, strlen(str)*8/(float)sum);
    }
    return0;
}