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

Time Limit: 1000 ms 

Memory Limit: 65536 KiB

   

Problem Description

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

Input

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

Output

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

Sample Input

AAAAABCDTHE_CAT_IN_THE_HAT

Sample Output

64 13 4.9144 51 2.8

 

#include 
    
     #include 
     
      #include
      
       void arrange( int *a, int lt, int rt ){    int key = a[lt], i = lt, j = rt;    if( i >= j ) return ;    while( i < j )    {        while( i < j && a[j] >= key )            j--;        a[i] = a[j];        while( i < j && a[i] <= key )            i++;        a[j] = a[i];    }    a[i] = key;    arrange( a, lt, i-1 );    arrange( a, i+1, rt);}int main(){    int len, i;    char s[500];    int q[1000],t[1000];    while(~scanf("%s",s))    {        int head = 0, tail = 0;        memset( t, 0, sizeof(t) );        len = strlen(s) ;        for( i = 0; i < len; i++ )        {            t[s[i]]++;        }        for( i = 0; i < 500; i++)        {            if( t[i] )            {                q[head++] = t[i];            }        }        arrange( q, 0, head-1 );        int sum = 0;        int a, b;        while( head != tail )        {            a = q[tail++];            if( head != tail )            {                b = q[tail++];                sum += a + b;                q[head++] = a + b;                arrange( q, tail, head-1 );            }        }        printf("%d %d %.1lf\n", len*8, sum, 1.0*len*8/sum );    }    return 0;}