文章
20
粉丝
224
获赞
57
访问
138.6k
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
struct node {
int x;
// 定义优先队列的比较关系,这里我们定义的是小根堆
bool operator < (const node& a) const {
return x > a.x;
}
};
int main() {
char text[100];
while (scanf("%s", text) != EOF) {
if (strcmp(text, "END") != 0) {
int len = strlen(text);
map<char, int> m;
// 使用 map 来存储每个字符及对应出现的次数
for (int i = 0; i < len; ++i) {
char key = text[i];
++m[key];
}
map<char, int>::iterator iter;
priority_queue<node> q;
// 将每个字符出现的次数存储进优先队列中
for (iter = m.begin(); iter != m.end(); ++iter) q.push(node{iter->second});
int huffman = 0;
// 如果优先队列一开始就只有一个元素,则说明此字符串只有一种字符,对应的哈夫曼编码长度则是字符串的长度
if (q.size() == 1) huffman = len;
// 否则计算此哈夫曼树的带权路径长度,即 WPL
else {
while (q.size() > 1) {
node num1 = q.top();
q.pop();
node num2 = q.top();
q.pop();
...
登录后发布评论
<script>
alert("测试");
</script>