c++ - 使用stl和没有节点c ++的霍夫曼编码
问题描述
该代码必须为字符串中的字符打印霍夫曼代码,但它为某些字符提供了错误的代码(主要是最后得到代码 1 的字符
#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
struct compare {
bool operator()(pair<char, int> l, pair<char, int> r) {
return r.second > l.second;
}
};
map<char, int> frequencies(string str) {
map<char, int> result;
for (int i = 0; i < str.length(); i++) {
if (result.find(str[i]) != result.end())
result[str[i]]++;
else
result[str[i]] = 1;
}
return result;
}
void print(const map<char, int> a) {
for (map<char, int>::const_iterator it = a.begin(); it != a.end(); it++) {
cout << (it->first) << " " << (it->second) << endl;
}
}
void prints(const map<char, string> a) {
for (map<char, string>::const_iterator it = a.begin(); it != a.end(); it++) {
cout << (it->first) << " " << (it->second) << endl;
}
}
map<char, string> huffman(map<char, int> a) {
priority_queue < pair < char, int >, vector < pair < char, int > >, compare > mappednodes;
pair<char, int> root;
pair<char, int> left, right;
string s = "";
map<char, string> result;
for (map<char, int>::iterator itr = a.begin(); itr != a.end(); itr++) {
mappednodes.push(pair<char, int>(itr->first, itr->second));
}
while (mappednodes.size() != 1) {
left = mappednodes.top();
mappednodes.pop();
right = mappednodes.top();
mappednodes.pop();
root = make_pair('#', left.second + right.second);
mappednodes.push(root);
if (left.first != '#') {
s = "0" + s;
result[left.first] = s;
}
if (right.first != '#') {
s = "1" + s;
result[right.first] = s;
}
}
return result;
}
int main() {
string str;
cout << "enter the string ";
getline(cin, str);
cout << endl;
map<char, int> freq = frequencies(str);
print(freq);
cout << endl;
map<char, string> codes = huffman(freq);
prints(codes);
}
例如对于字符串 sasi 它必须给出
- 0
- 我 10
- 11
但它的给予
- 0
- 我 10
- 110
https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/
以此为基础,却一无所获
解决方案
问题是您只是s
在循环中不断添加字符(“位”)。
推荐阅读
- php - 基本控制器中的 Destroy() 不起作用
- python - Scrapy Selenium Stale“元素不再附加到 DOM”错误
- django - 如何在 Django rest API 检索视图中获取相关对象?
- git - Git local repository deleted when github project is deleted?
- vuetify.js - Vuetify - how to make sticky elements?
- amazon-web-services - 为什么使用 Terraform 解析我的 dynamo_db_table_name 时会出错?
- jmeter - 如何性能测试分析服务
- c++ - 从基于迭代器的 for 循环转换后,如何在 map::find() 中调用方法?
- python - Python 脚本依赖于另一个 .exe。是否可以将两者合并为一个.exe?
- c# - EF Core 3.0 存储过程:多个参数