哈夫曼编码与解码的C++实现:建立哈夫曼树、进行哈夫曼编码与解码
时间: 2023-07-08 07:25:12 浏览: 79
好的,以下是哈夫曼编码与解码的C++实现代码:
```c++
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
// 定义哈夫曼树的节点结构体
struct TreeNode {
char data; // 字符
int weight; // 权重
TreeNode* left; // 左子节点
TreeNode* right; // 右子节点
TreeNode(char d, int w): data(d), weight(w), left(nullptr), right(nullptr) {}
};
// 定义哈夫曼树节点的比较函数
struct cmp {
bool operator()(const TreeNode* a, const TreeNode* b) const {
return a->weight > b->weight;
}
};
// 建立哈夫曼树
TreeNode* buildHuffmanTree(const string& text) {
// 统计每个字符在字符串中出现的次数
unordered_map<char, int> charFreq;
for (char c : text) {
charFreq[c]++;
}
// 将每个字符的出现次数和字符本身存入优先队列中
priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
for (auto p : charFreq) {
pq.push(new TreeNode(p.first, p.second));
}
// 不断取出优先队列中的两个最小节点,合并成一个新节点,再将新节点放回优先队列中
while (pq.size() > 1) {
TreeNode* left = pq.top();
pq.pop();
TreeNode* right = pq.top();
pq.pop();
TreeNode* parent = new TreeNode('\0', left->weight + right->weight);
parent->left = left;
parent->right = right;
pq.push(parent);
}
// 最后的队列头即为整个哈夫曼树的根节点
return pq.top();
}
// 哈夫曼编码
void encodeHuffman(TreeNode* root, string code, unordered_map<char, string>& huffmanCode) {
if (!root) {
return;
}
if (!root->left && !root->right) {
huffmanCode[root->data] = code;
return;
}
encodeHuffman(root->left, code + "0", huffmanCode);
encodeHuffman(root->right, code + "1", huffmanCode);
}
// 哈夫曼解码
string decodeHuffman(TreeNode* root, string huffmanCode) {
string decodeText = "";
TreeNode* cur = root;
for (char c : huffmanCode) {
if (c == '0') {
cur = cur->left;
} else {
cur = cur->right;
}
if (!cur->left && !cur->right) {
decodeText += cur->data;
cur = root;
}
}
return decodeText;
}
int main() {
string text = "this is a test text";
TreeNode* root = buildHuffmanTree(text);
unordered_map<char, string> huffmanCode;
encodeHuffman(root, "", huffmanCode);
for (auto p : huffmanCode) {
cout << p.first << ": " << p.second << endl;
}
string huffmanCodeText = "";
for (char c : text) {
huffmanCodeText += huffmanCode[c];
}
cout << "Huffman code: " << huffmanCodeText << endl;
string decodeText = decodeHuffman(root, huffmanCodeText);
cout << "Decode text: " << decodeText << endl;
return 0;
}
```
上述代码首先实现了哈夫曼树的建立,然后通过递归实现了哈夫曼编码和解码。在编码时,对于每个字符,我们都可以通过哈夫曼树得到其对应的哈夫曼编码;在解码时,我们只需要从根节点开始,依次遍历哈夫曼树,直到遇到叶子节点,就可以得到该叶子节点所代表的字符。最终输出的结果是原始字符串的哈夫曼编码和解码后的字符串。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)