哈夫曼编码贪心算法c++实现
时间: 2023-07-11 17:20:42 浏览: 140
贪心算法的C++实现
3星 · 编辑精心推荐
以下是C++中哈夫曼编码的贪心算法实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 哈夫曼树节点
struct Node {
char ch;
int freq;
Node* left;
Node* right;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
// 小根堆比较函数
struct compare {
bool operator()(Node* l, Node* r) { return l->freq > r->freq; }
};
// 生成哈夫曼树
Node* huffmanTree(const string& str) {
// 统计字符频率
vector<int> freq(256, 0);
for (auto& c : str) {
freq[c]++;
}
// 构建小根堆
priority_queue<Node*, vector<Node*>, compare> pq;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
pq.push(new Node(i, freq[i]));
}
}
// 不断合并小根堆中的节点,直到只剩一个节点
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
Node* parent = new Node('#', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 生成哈夫曼编码
void huffmanCode(Node* root, string code, vector<string>& result) {
if (!root) {
return;
}
if (root->ch != '#') {
result[root->ch] = code;
}
huffmanCode(root->left, code + "0", result);
huffmanCode(root->right, code + "1", result);
}
int main() {
string str = "hello world";
Node* root = huffmanTree(str);
vector<string> result(256);
huffmanCode(root, "", result);
// 输出生成的哈夫曼编码
for (int i = 0; i < 256; i++) {
if (!result[i].empty()) {
cout << (char)i << ": " << result[i] << endl;
}
}
return 0;
}
```
在这个实现中,我们首先统计字符串中每个字符出现的频率,并将它们存储在一个大小为256的数组中。然后,我们构建一个小根堆,其中每个节点都代表一个字符及其对应的频率,我们将小根堆中频率最小的两个节点合并为一个新节点,并将它们的和作为新节点的频率。这个过程一直持续到小根堆中只剩下一个节点为止,这个节点就是哈夫曼树的根节点。
接下来,我们沿着哈夫曼树,为每个字符生成一个哈夫曼编码。当我们遍历到一个叶子节点时,我们就将其对应的字符和编码存储在一个vector中。
最后,我们可以输出每个字符的哈夫曼编码。
阅读全文