tx1053.cpp

杭州电子科技大学在线系统ACM的1053题

#include<stdio.h>
#include<string.h>
typedef struct
{
    char c;
    int n;
    int set;
}node;



void main()
{
    int length,i,j,t,k,count[10000],sum,min1,min2,flag,k0,len[10000],t0,t2;
    node a[10000];
    char s[10000];
    while(scanf("%s",s)&&strcmp(s,"END")){
    length=strlen(s);
    for (i=0;i<10000;i++) count[i]=1;            //权值计数器初始化
    for (i=0;i<length;i++){
        if (s[i]==0) continue;
        for (j=i+1;j<length;j++)
            if (s[i]==s[j]) {count[i]++; s[j]=0;}
                        }
    for (i=0,k=0;i<length;i++)
        if (s[i]){
        a[k].c=s[i];
        a[k].n=count[i];k++;}                    //结构体数组记录权值信息





    for (i=0;i<k;i++)
        a[i].set=i;                        //根结点初始化
        k0=k;
    do{for (i=0;i<k;i++){if (a[i].set==i) {t=i;break;}}  //找出第一个根结点
        
        for (i=t+1,min1=t;i<k;i++)
            if ((a[i].n)<(a[min1].n)&&(a[i].set==i))
                min1=i;                            //找出权值最小的根结点

    
            for(i=0,flag=0;i<k;i++)
                if ((a[i].set==i)&&(i!=min1))
                {flag=1;t2=i;break;}                        //判断是否还有其他根结点

                if(flag){
            for (i=t,min2=t2;i<k;i++){
            
            if ((a[i].n<a[min2].n)&&(i!=min1)&&(a[i].set==i))
                min2=i;}                        //找出权值第二小的根节点
                }
            if (flag){
                a[min1].set=k;
                a[min2].set=k;
                a[k].set=k;
                a[k].n=a[min1].n+a[min2].n;
                k++;}                            //以两个最小的节点构造新节点
    } while (flag);            //构造huffman树
                k=k-1;
        for (i=0;i<10000;i++) len[i]=1;


        for (i=0;i<k0;i++){
            t0=a[i].set;
            while (t0!=k){
                len[i]++;
                t0=a[t0].set;}
        }                        //从叶子节点逆向查找根节点并计算长度



        for (i=0,sum=0;i<k0;i++)
            sum+=a[i].n*len[i];
        printf("%d %d %.1lf\n",length*8,sum,(double)length*8/sum);
    }
}