请写出一段c++程序,从键盘接收一串电文字符,在程序中构造一颗霍夫曼数,实现霍夫曼编码,用霍夫曼编码生成的代码串进行译码,输出对应的霍夫曼编码。还能翻译由霍夫曼编码生成的代码串,输出对应的电文字符串。
时间: 2024-03-22 16:41:45 浏览: 57
以下是使用C++实现霍夫曼编码和译码的程序:
```c++
#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <cstring>
using namespace std;
struct Node {
char ch;
int freq;
Node *left, *right;
Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {};
};
struct Compare {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
void generateCodes(Node* root, string code, map<char, string>& codes) {
if (!root) {
return;
}
if (root->ch != '$') {
codes[root->ch] = code;
}
generateCodes(root->left, code + "0", codes);
generateCodes(root->right, code + "1", codes);
}
Node* buildHuffmanTree(string s) {
int n = s.length();
map<char, int> freq;
for (int i = 0; i < n; i++) {
freq[s[i]]++;
}
priority_queue<Node*, vector<Node*>, Compare> pq;
for (auto p : freq) {
pq.push(new Node(p.first, p.second));
}
while (pq.size() > 1) {
Node* x = pq.top();
pq.pop();
Node* y = pq.top();
pq.pop();
Node* z = new Node('$', x->freq + y->freq);
z->left = x;
z->right = y;
pq.push(z);
}
return pq.top();
}
string encode(string s, map<char, string> codes) {
string ans = "";
for (char c : s) {
ans += codes[c];
}
return ans;
}
string decode(string s, Node* root) {
string ans = "";
Node* curr = root;
for (char c : s) {
if (c == '0') {
curr = curr->left;
} else {
curr = curr->right;
}
if (curr->ch != '$') {
ans += curr->ch;
curr = root;
}
}
return ans;
}
int main() {
string s = "hello world";
Node* root = buildHuffmanTree(s);
map<char, string> codes;
generateCodes(root, "", codes);
string encoded = encode(s, codes);
string decoded = decode(encoded, root);
cout << "Original String: " << s << endl;
cout << "Encoded String: " << encoded << endl;
cout << "Decoded String: " << decoded << endl;
return 0;
}
```
该程序首先读入一串电文字符,然后使用该字符构建一颗霍夫曼树。接着,程序使用霍夫曼树生成每个字符的霍夫曼编码,并将编码存储在一个映射表中。程序使用该表将原始字符串编码为一个二进制串。程序还能将该二进制串解码为原始字符串。
阅读全文