哈夫曼编码代码c++数据结构
时间: 2024-05-19 07:08:44 浏览: 14
哈夫曼编码是一种可变字长编码(VLC)的一种,它是由David A. Huffman在1952年提出的。哈夫曼编码主要应用在数据压缩领域,可以将频率较高的字符用较短的编码表示,而将频率较低的字符用较长的编码表示,从而实现数据的压缩。
以下是一个C++实现的哈夫曼编码代码:
```c++
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
// 定义哈夫曼树节点
struct HuffmanNode {
char ch;
int freq;
HuffmanNode *left, *right;
HuffmanNode(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};
// 定义哈夫曼树节点比较函数
struct HuffmanNodeCmp {
bool operator()(const HuffmanNode* a, const HuffmanNode* b) const {
return a->freq > b->freq;
}
};
// 哈夫曼编码函数
unordered_map<char, string> HuffmanCoding(const string& text) {
// 统计字符出现频率
unordered_map<char, int> freq;
for (char ch : text) {
++freq[ch];
}
// 构建哈夫曼树
priority_queue<HuffmanNode*, vector<HuffmanNode*>, HuffmanNodeCmp> pq;
for (const auto& [ch, f] : freq) {
pq.push(new HuffmanNode(ch, f));
}
while (pq.size() > 1) {
HuffmanNode* left = pq.top(); pq.pop();
HuffmanNode* right = pq.top(); pq.pop();
pq.push(new HuffmanNode('\0', left->freq + right->freq));
pq.top()->left = left;
pq.top()->right = right;
}
// 构建哈夫曼编码表
unordered_map<char, string> codes;
function<void(HuffmanNode*, string)> dfs = [&](HuffmanNode* node, string code) {
if (!node) return;
if (node->ch) codes[node->ch] = code;
dfs(node->left, code + '0');
dfs(node->right, code + '1');
};
dfs(pq.top(), "");
// 返回哈夫曼编码表
return codes;
}
int main() {
string text = "this is an example for huffman encoding";
unordered_map<char, string> codes = HuffmanCoding(text);
for (const auto& [ch, code] : codes) {
cout << ch << ": " << code << endl;
}
return 0;
}
```