用c++定义Huffman树,实现Huffman编码与译码操作
时间: 2024-06-13 07:06:22 浏览: 11
以下是用C++定义Huffman树,实现Huffman编码与译码操作的示例代码:
```c++
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
// 定义Huffman树节点
struct HuffmanNode {
char ch; // 字符
int freq; // 频率
HuffmanNode* left; // 左子节点
HuffmanNode* right; // 右子节点
HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
// 定义比较函数,用于优先队列
struct Compare {
bool operator()(HuffmanNode* a, HuffmanNode* b) {
return a->freq > b->freq;
}
};
// 构建Huffman树
HuffmanNode* buildHuffmanTree(const string& str) {
// 统计字符频率
unordered_map<char, int> freqMap;
for (char c : str) {
freqMap[c]++;
}
// 将字符频率存入优先队列中
priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
for (auto& p : freqMap) {
pq.push(new HuffmanNode(p.first, p.second));
}
// 构建Huffman树
while (pq.size() > 1) {
HuffmanNode* left = pq.top();
pq.pop();
HuffmanNode* right = pq.top();
pq.pop();
HuffmanNode* parent = new HuffmanNode('$', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
// 生成Huffman编码
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
if (!root) {
return;
}
if (root->ch != '$') {
codeMap[root->ch] = code;
}
generateHuffmanCode(root->left, code + "0", codeMap);
generateHuffmanCode(root->right, code + "1", codeMap);
}
// Huffman编码
string encode(const string& str, unordered_map<char, string>& codeMap) {
string encodedStr;
for (char c : str) {
encodedStr += codeMap[c];
}
return encodedStr;
}
// Huffman译码
string decode(const string& str, HuffmanNode* root) {
string decodedStr;
HuffmanNode* cur = root;
for (char c : str) {
if (c == '0') {
cur = cur->left;
} else {
cur = cur->right;
}
if (cur->ch != '$') {
decodedStr += cur->ch;
cur = root;
}
}
return decodedStr;
}
int main() {
string str = "hello world";
HuffmanNode* root = buildHuffmanTree(str);
unordered_map<char, string> codeMap;
generateHuffmanCode(root, "", codeMap);
string encodedStr = encode(str, codeMap);
cout << "Encoded string: " << encodedStr << endl;
string decodedStr = decode(encodedStr, root);
cout << "Decoded string: " << decodedStr << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)