费诺编码的C++编程实现
时间: 2023-11-08 16:06:06 浏览: 40
费诺编码是一种将字符编码为可变长度的编码方法,在压缩算法中被广泛使用。以下是一个C++实现:
```c++
#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;
struct Node {
char ch;
int freq;
Node* left;
Node* right;
Node(char ch, int freq) {
this->ch = ch;
this->freq = freq;
left = right = nullptr;
}
};
struct Compare {
bool operator()(Node* l, Node* r) {
return l->freq > r->freq;
}
};
void encode(Node* root, string str, map<char, string>& huffCode) {
if (root == nullptr) {
return;
}
if (!root->left && !root->right) {
huffCode[root->ch] = str;
}
encode(root->left, str + "0", huffCode);
encode(root->right, str + "1", huffCode);
}
void decode(Node* root, int& index, string str) {
if (root == nullptr) {
return;
}
if (!root->left && !root->right) {
cout << root->ch;
return;
}
index++;
if (str[index] == '0') {
decode(root->left, index, str);
} else {
decode(root->right, index, str);
}
}
void buildHuffmanTree(string text) {
map<char, int> freq;
for (char ch : text) {
freq[ch]++;
}
priority_queue<Node*, vector<Node*>, Compare> pq;
for (auto pair : freq) {
pq.push(new Node(pair.first, pair.second));
}
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
int sum = left->freq + right->freq;
pq.push(new Node('\0', sum));
}
Node* root = pq.top();
map<char, string> huffCode;
encode(root, "", huffCode);
cout << "Huffman Codes are:\n" << endl;
for (auto pair : huffCode) {
cout << pair.first << " " << pair.second << endl;
}
cout << "\nOriginal string was:\n" << text << endl;
string str = "";
for (char ch : text) {
str += huffCode[ch];
}
cout << "\nEncoded string is:\n" << str << endl;
int index = -1;
cout << "\nDecoded string is:\n";
while (index < (int) str.size() - 2) {
decode(root, index, str);
}
}
int main() {
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}
```
这个实现使用了一个优先队列来构建哈夫曼树,并使用递归来创建编码和解码函数。