哈夫曼编码c++
时间: 2023-07-05 12:08:30 浏览: 46
哈夫曼编码是一种压缩算法,它通过将频率较高的字符用较短的编码表示,从而减少了数据的存储空间。下面是一个简单的C++实现:
```c++
#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;
struct Node {
char ch;
int freq;
Node *left, *right;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct cmp {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
unordered_map<char, string> huffmanCodes;
void generateCodes(Node* root, string code) {
if (!root) return;
if (root->ch != '\0') huffmanCodes[root->ch] = code;
generateCodes(root->left, code + "0");
generateCodes(root->right, code + "1");
}
void huffmanEncoding(string s) {
unordered_map<char, int> freq;
for (char c : s) freq[c]++;
priority_queue<Node*, vector<Node*>, cmp> pq;
for (auto p : freq) pq.push(new Node(p.first, p.second));
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
Node* parent = new Node('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
Node* root = pq.top();
generateCodes(root, "");
delete root;
cout << "Huffman Codes:\n";
for (auto p : huffmanCodes) {
cout << p.first << " : " << p.second << endl;
}
cout << "Encoded string:\n";
string encodedString = "";
for (char c : s) encodedString += huffmanCodes[c];
cout << encodedString << endl;
}
int main() {
string s = "hello world";
huffmanEncoding(s);
return 0;
}
```
在上面的实现中,首先使用一个哈希表统计每个字符的出现频率。然后,将每个字符及其出现频率作为一个节点加入到一个小根堆中。接下来,每次从小根堆中弹出两个频率最小的节点,将它们作为左右子节点构造一个新的节点,并将新节点加入到小根堆中。这个过程被称作哈夫曼树的构建。最终,哈夫曼树的根节点就是所有节点的父节点,也是编码的起点。通过递归遍历哈夫曼树,可以生成每个字符对应的哈夫曼编码。最后,将原始字符串中的每个字符都替换为它对应的哈夫曼编码,就得到了压缩后的字符串。