数据压缩（哈夫曼编码）

本文主要是介绍数据压缩（哈夫曼编码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【问题描述】在数据压缩问题中，需要将数据文件转换成由二进制字符0、1组成的二进制串，称之为编码，已知待压缩的数据中包含若干字母（A-Z），为获得更好的空间效率，请设计有效的用于数据压缩的二进制编码，使数据文件压缩后编码总长度最小，并输出这个最小长度值。

【输入形式】待压缩的数据（长度不大于100的大写字母）

【输出形式】编码的最小总长度值

【样例输入】ABACCDA

【样例输出】13

【样例说明】A编码0，B编码110，C编码10，D编码111，ABACCDA的编码为0110010101110

【评分标准】

#include<iostream>
#include<stack>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{string str;cin>>str;int cnt[26]={0};int wpl=0;for(int i=0;str[i];i++){cnt[str[i]-'A']++;}priority_queue<int ,vector<int>,greater<int> >heap;for(int i=0;i<26;i++){if(cnt[i])heap.push(cnt[i]);}while(heap.size()>1){int t1=heap.top();heap.pop();int t2=heap.top();heap.pop();heap.push(t1+t2);wpl=wpl+t1+t2;}cout<<wpl<<endl;return 0;
}

这篇关于数据压缩（哈夫曼编码）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---