数据结构实验之二叉树六：哈夫曼编码

Problem Description
字符的编码方式有多种，除了你们熟悉的ASCII编码，哈夫曼编码(Huffman Coding)也是一种编码方式，它是可变字长编码。该方法彻底依据字符出现几率来构造出平均长度最短的编码，称之为最优编码。哈夫曼编码常被用于数据文件压缩中，其压缩率一般在20%～90%之间。你的任务是对从键盘输入的一个字符串求出它的ASCII编码长度和哈夫曼编码长度的比值。
Input
输入数据有多组，每组数据一行，表示要编码的字符串。
Output
对应字符的ASCII编码长度la，huffman编码长度lh和la/lh的值(保留一位小数)，数据之间以空格间隔。
Sample Input
AAAAABCD
THE_CAT_IN_THE_HAT
Sample Output
64 13 4.9
144 51 2.8ios

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
#define maxsize 255
using namespace std;
typedef long long int ll;
int n,m,b[255];
char a[255];
int main()
{
    while(scanf("%s",a)!=EOF)
    {
        memset(b,0,sizeof(b));
        priority_queue<int,vector<int>,greater<int> > q;
        n=strlen(a);
        for(int i=0; i<n; i++)
            b[a[i]]++;
        for(int i=0; i<255; i++)
            if(b[i]) q.push(b[i]);
        int sum=0;
        while(!q.empty())
        {
            int x1=q.top();
            q.pop();
            if(!q.empty())
            {
                int x2=q.top();
                q.pop();
                sum=sum+x1+x2;
                q.push(x1+x2);
            }
        }
        double c=n*8.0/sum;
        printf("%d %d %.1lf\n",n*8,sum,c); //printf("%d %d %.1lf\n",n*8,sum,n*8*1.0/sum);会RE

    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define INF 0x3f3f3f3f
#include <algorithm>
#define maxsize 255
using namespace std;
typedef long long int ll;
int n,m,b[255];
char a[255];
typedef struct
{
    int *elem;
    int top;
} stack;
void creat(stack *s)
{
    s->elem=new int [maxsize];
    s->top=-1;
}
void push(stack *s,int x)
{
    s->elem[++s->top]=x;
}
void pop(stack *s)
{
    s->top--;
}
int get(stack *s)
{
    return s->elem[s->top];
}
int empty(stack *s)
{
    if(s->top==-1) return 1;
    return 0;
}
void sort(stack *s,int l,int r)
{
    int i=l,j=r;
    int x=s->elem[l];
    if(l>=r) return;
    while(i<j)
    {
        while(i<j&&s->elem[j]<=x) j--;
        s->elem[i]=s->elem[j];
        while(i<j&&s->elem[i]>=x) i++;
        s->elem[j]=s->elem[i];
    }
    s->elem[i]=x;
    sort(s,i+1,r);
    sort(s,l,i-1);
}
int main()
{
    stack s;
    creat(&s);
    while(gets(a)!=NULL)
    {
        int sum=0;
        memset(b,0,sizeof(b));
        n=strlen(a);
        for(int i=0; i<n; i++)
            b[(int)a[i]]++;
        for(int i=0; i<=255; i++)
            if(b[i]) push(&s,b[i]);
        sort(&s,0,s.top);
        while(!empty(&s))
        {
            int x1=get(&s);
            pop(&s);
            if(!empty(&s))
            {
                int x2=get(&s);
                pop(&s);
                sum=sum+x1+x2;
                push(&s,x1+x2);
                sort(&s,0,s.top);
            }
        }
        printf("%d %d %.1lf\n",n*8,sum,n*8*1.0/sum);//这里这样写就过了，莫名其妙，上面就RE了？？？
        s.top=-1;
    }
    return 0;
}