哈夫曼编码c++
时间: 2023-07-05 07:22:13 浏览: 62
以下是C++实现的哈夫曼编码:
```cpp
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
// 哈夫曼树节点
struct HuffmanNode {
char data; // 字符
int freq; // 字符出现频率
HuffmanNode *left, *right; // 左右子节点
HuffmanNode(char data, int freq) {
this->data = data;
this->freq = freq;
left = right = nullptr;
}
// 用于优先队列排序规则
bool operator<(const HuffmanNode& other) const {
return freq > other.freq;
}
};
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
priority_queue<HuffmanNode> pq;
for (auto& pair : freqMap) {
pq.push(HuffmanNode(pair.first, pair.second));
}
while (pq.size() > 1) {
HuffmanNode *left = new HuffmanNode(pq.top().data, pq.top().freq);
pq.pop();
HuffmanNode *right = new HuffmanNode(pq.top().data, pq.top().freq);
pq.pop();
HuffmanNode *parent = new HuffmanNode('$', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(*parent);
}
return new HuffmanNode(pq.top().data, pq.top().freq);
}
// 构建字符到哈夫曼编码的映射表
void buildEncodingMap(HuffmanNode* root, string code, unordered_map<char, string>& encodingMap) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
encodingMap[root->data] = code;
}
buildEncodingMap(root->left, code + "0", encodingMap);
buildEncodingMap(root->right, code + "1", encodingMap);
}
// 哈夫曼编码
string huffmanEncode(string s) {
unordered_map<char, int> freqMap;
for (char c : s) {
freqMap[c]++;
}
HuffmanNode *root = buildHuffmanTree(freqMap);
unordered_map<char, string> encodingMap;
buildEncodingMap(root, "", encodingMap);
string encodedStr = "";
for (char c : s) {
encodedStr += encodingMap[c];
}
return encodedStr;
}
// 哈夫曼解码
string huffmanDecode(string encodedStr, HuffmanNode* root) {
string decodedStr = "";
HuffmanNode *current = root;
for (char c : encodedStr) {
if (c == '0') {
current = current->left;
} else {
current = current->right;
}
if (current->left == nullptr && current->right == nullptr) {
decodedStr += current->data;
current = root;
}
}
return decodedStr;
}
int main() {
string s = "Hello, world!";
string encodedStr = huffmanEncode(s);
cout << "Encoded string: " << encodedStr << endl;
HuffmanNode *root = buildHuffmanTree(unordered_map<char, int>());
string decodedStr = huffmanDecode(encodedStr, root);
cout << "Decoded string: " << decodedStr << endl;
return 0;
}
```
注意:该实现中使用了C++11的特性,如果编译器不支持,需要做相应的修改。