用c++代码实现哈夫曼编码
时间: 2024-05-19 20:09:13 浏览: 17
哈夫曼编码是一种可变字长编码(VLC)的一种方法,主要用于数据压缩。C++可以通过以下步骤实现哈夫曼编码:
1. 构建哈夫曼树
2. 根据哈夫曼树生成哈夫曼编码表
3. 使用哈夫曼编码表对原始数据进行编码
以下是一个简单的C++实现示例:
```
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
// 定义哈夫曼树节点
struct TreeNode {
char ch;
int freq;
TreeNode *left;
TreeNode *right;
TreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
~TreeNode() {
if (left != nullptr) delete left;
if (right != nullptr) delete right;
}
};
// 定义比较函数
struct Compare {
bool operator()(const TreeNode *lhs, const TreeNode *rhs) const {
return lhs->freq > rhs->freq;
}
};
// 构建哈夫曼树
TreeNode *buildHuffmanTree(const unordered_map<char, int> &freqMap) {
priority_queue<TreeNode *, vector<TreeNode *>, Compare> pq;
for (const auto &[ch, freq] : freqMap) {
pq.push(new TreeNode(ch, freq));
}
while (pq.size() > 1) {
auto left = pq.top();
pq.pop();
auto right = pq.top();
pq.pop();
auto parent = new TreeNode('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
auto root = pq.top();
pq.pop();
return root;
}
// 生成哈夫曼编码表
void generateHuffmanCode(const TreeNode *root, string code, unordered_map<char, string> &codeMap) {
if (root == nullptr) return;
if (root->left == nullptr && root->right == nullptr) {
codeMap[root->ch] = code;
return;
}
generateHuffmanCode(root->left, code + "0", codeMap);
generateHuffmanCode(root->right, code + "1", codeMap);
}
// 对原始数据进行编码
string encode(const string &input, const unordered_map<char, string> &codeMap) {
string output;
for (const auto &c : input) {
output += codeMap.at(c);
}
return output;
}
int main() {
// 统计字符出现频率
string input = "hello world";
unordered_map<char, int> freqMap;
for (const auto &c : input) {
freqMap[c]++;
}
// 构建哈夫曼树
auto root = buildHuffmanTree(freqMap);
// 生成哈夫曼编码表
unordered_map<char, string> codeMap;
generateHuffmanCode(root, "", codeMap);
// 对原始数据进行编码
string encoded = encode(input, codeMap);
// 输出结果
cout << "Encoded: " << encoded << endl;
for (const auto &[ch, code] : codeMap) {
cout << ch << ": " << code << endl;
}
// 释放内存
delete root;
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)