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

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

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

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

#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<queue> #include<iomanip> using namespace std; double num[100000]; char ss[100000]; int samechar(string x) { memset(num, 0, sizeof(num)); int flag; int n=0; ss[n]=x[0]; num[n]=1; int l=x.size(); for(int i=1;i<l;i++) { int j; flag=0; for(j=0;j<=n;j++) { if(x[i]==ss[j]) { flag=1; num[j]++; break; } } if(!flag) { n++; ss[n]=x[i]; num[n]=1; } } return n; } int main() { ios::sync_with_stdio(false); string s; while(cin>>s) { int k=samechar(s); for(int i=0;i<=k;i++) { num[i]/=8.0; /// cout<<num[i]<<endl; } int siz=s.size()*8; double last, sum, t; priority_queue<double, vector<double>, greater<double> >p;///定义优先队列p； sum = 0; for(int i=0; i<=k; i++) { p.push(num[i]); } while(!p.empty()) { last = p.top(); p.pop(); if(p.empty()) break; else { t = p.top(); p.pop(); last += t; p.push(last); sum +=last; } } int tree=sum*8; cout<<siz<<" "<<tree<<" "; cout<<fixed<<setprecision(1)<<(double) siz/tree<<endl; } return 0; }

以下为数组模拟优先队列版

#include<iostream> #include<algorithm> #include<string> #include<cstring> #include<queue> #include<iomanip> using namespace std; double num[100000]; ///定义频率数组 char ss[100000]; ///记录出现过的字符 int samechar(string x) ///该函数将不同字符出现的次数记录下来 { memset(num, 0, sizeof(num)); int flag; int n=0; ss[n]=x[0]; num[n]=1; int l=x.size(); for(int i=1;i<l;i++) { flag=0; for(int j=0;j<=n; ++j) { if(x[i]==ss[j]) { flag=1; num[j]++; break; } } if(!flag) { n++; ss[n]=x[i]; num[n]=1; } } return n; } int main() { ios::sync_with_stdio(false); string s; while(cin>>s) { int k=samechar(s); for(int i=0;i<=k;i++) { num[i]/=8.0; } int siz=s.size()*8; double last, sum=0; double p[100000]; ///模拟优先队列 int rear=0, frot=0; for(int i=0; i<=k; i++) { p[rear++]=num[i]; } while(rear>frot) { sort(p+frot, p+rear); last = p[frot++]; if(rear<=frot) break; else { double t = p[frot++]; last += t; p[rear++]=last; sum +=last; } } int tree=sum*8; cout<<siz<<" "<<tree<<" "; cout<<fixed<<setprecision(1)<<(double) siz/tree<<endl; } return 0; }