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

3/8/2017来源:ASP.NET技巧人气:485

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

Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic

PRoblem Description

字符的编码方式有多种,除了大家熟悉的ASCII编码,哈夫曼编码(Huffman Coding)也是一种编码方式,它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码,称之为最优编码。哈夫曼编码常被用于数据文件压缩中,其压缩率通常在20%~90%之间。你的任务是对从键盘输入的一个字符串求出它的ASCII编码长度和哈夫曼编码长度的比值。

Input

 输入数据有多组,每组数据一行,表示要编码的字符串。

Output

 对应字符的ASCII编码长度la,huffman编码长度lh和la/lh的值(保留一位小数),数据之间以空格间隔。

Example Input

AAAAABCD
THE_CAT_IN_THE_HAT

Example Output

64 13 4.9
144 51 2.8

Hint

 

Author

 xam
#include <iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<stdlib.h>
#include<algorithm>

using namespace std;
int sum;
int h[10002];

int main()
{
    priority_queue<int,vector<int>,greater<int> >q;//最小元素优先,升序相等于最大堆
    int i,a,b,d[200],alen,c;
    char s[10002];

    while(~scanf("%s",s))
    {
        sum = 0;
        memset(d,0,sizeof(d));
        int len=strlen(s);
        alen = len*8;
        for(i=0;i<len;i++)
        {
           d[s[i]]++;
        }
        for(i=0;i<150;i++)
        {
           if(d[i]!=0)
           {
              q.push(d[i]);
           }
        }
        while(!q.empty())
    {
        a = q.top();
        q.pop();
        if(!q.empty())
        {
           b = q.top();
           q.pop();
           c = a+b;
           q.push(c);
           sum += c;
        }
    }
    printf("%d %d %.1lf\n",alen,sum,1.0*alen/sum);
    }

    return 0;
}
/*题目大意:FJ需要修补牧场的围栏,他需要 N 块长度为 Li 的木头(N planks of woods)。开始时,FJ只有一块无限长的木板,因此他需要把无限长的木板锯成 N 块长度

为 Li 的木板,Farmer Don提供FJ锯子,但必须要收费的,收费的标准是对应每次据出木块的长度,比如说测试数据中 5 8 8,一开始,FJ需要在无限长的木板上锯下长度 21 的木板(5+8+8=21),第二次锯下长度为 5 的木板,第三次锯下长度为 8 的木板,至此就可以将长度分别为 5 8 8 的木板找出


题目可以转化为Huffman树构造问题 :

给定 N planks of woods,

1.   在 N planks 中每次找出两块长度最短的木板,然后把它们合并,加入到集合A中,

2.  在集合中找出两块长度最短的木板,合并加入到集合A中,重复过程,直到集合A中只剩下一个元素

显然,通过每次选取两块长度最短的木板,合并,最终必定可以合并出长度为 Sum(Li)的木板,并且可以保证总的耗费最少
*/


/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 172KB
Submit time: 2017-02-09 10:17:15
****************************************************/