ZOJ 1117 POJ 1521 HU 1053 Huffman符号化

テーマリンク
    
Description
An entropy encoder is a data encoding method achieve lossless data copression by encoding a message with“wasted”or“extra”information removed.In other words,entropy encoding removes information that was not necessary in the first placcurately encode the message.A higdegree of entropy implies a message with a great deal of wasted information;english text encoded in ASCII is an example of a message type that has has hintropy.Already copresed messages、such as JPEG graphics or ZIP archives、have tylittle entropy and do benefit front front.co.co.coront.coront...
 
    文字列を入力し、ハフマン符号化を行い、元の文字列の長さ、符号化後の長さ、二つの長さの比を出力するという意味です.
    Huffmanコードの思想は欲張りです.ここでstlの優先列を使います.prority.queueは山を使って最適化しています.自分でもいっぱい書いてもいいですが、この問題についてはちょっと主犯的な感じがします.stlは確かに強いものだと改めて感じました.
   解題コード

//ZOJ1117 POJ1521 HDU1053  Huffman  
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;
char str[500];
int cnt[260];

struct cmp                                       
{
    bool operator()(int a, int b)
    {
        return a > b;
    }
};
/*      priority_queue<int>           vector<int>        
        ，     ，         cmp，            
class cmp
{
    public:
    bool operator() (int a, int b)
    {
        return a > b;
    }
};
*/
priority_queue <int, vector<int>, cmp> q;

int main()
{
    while (scanf("%s",str) && strcmp(str,"END"))
    {
        int l = strlen(str);
        memset(cnt, 0, sizeof(cnt));      
        //         ，              
        for (int i = 0; i < l; i++)
        {
            cnt[str[i]]++;
        }
        for (int i = 0; i < 260; i++)
        {
            if (cnt[i])
            {
                q.push(cnt[i]);
            }
        }
        int nl = 0;
        if (q.size() == 1)
            nl = l;
        while (q.size() > 1)
        {
            int a = q.top(); q.pop();
            int b = q.top(); q.pop();
            q.push(a+b);
            nl += (a+b);                               
            //            ，     （a+b），          
        }
        q.pop();
        printf("%d %d %.1lf
",8*l, nl, (double)(8*l)/(double)nl);
    }
    return 0;
}