请写出一段程序,在Dev C++上运行,从键盘接收一串电文字符,在程序中构造一颗霍夫曼数,实现霍夫曼编码,用霍夫曼编码生成的代码串进行译码,输出对应的霍夫曼编码。还能翻译由霍夫曼编码生成的代码串,输出对应的电文字符串。
时间: 2024-03-22 07:41:59 浏览: 64
好的,以下是一个在Dev C++上运行的 C++ 示例程序:
```c++
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <utility>
using namespace std;
// 定义节点类
class Node {
public:
int freq;
char ch;
Node* left;
Node* right;
Node(int freq, char ch, Node* left = nullptr, Node* right = nullptr) {
this->freq = freq;
this->ch = ch;
this->left = left;
this->right = right;
}
~Node() {
delete left;
delete right;
}
};
// 定义比较函数
class NodeComparator {
public:
bool operator() (Node* a, Node* b) {
return a->freq > b->freq;
}
};
// 构造霍夫曼树
Node* huffman_tree(string s) {
unordered_map<char, int> freq;
for (char ch : s) {
freq[ch]++;
}
priority_queue<Node*, vector<Node*>, NodeComparator> pq;
for (auto p : freq) {
pq.push(new Node(p.second, p.first));
}
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
pq.push(new Node(left->freq + right->freq, '\0', left, right));
}
return pq.top();
}
// 构造霍夫曼编码
unordered_map<char, string> huffman_code(Node* root) {
unordered_map<char, string> code;
if (root == nullptr) return code;
function<void(Node*, string)> dfs = [&](Node* node, string path) {
if (node->left == nullptr && node->right == nullptr) {
code[node->ch] = path;
return;
}
dfs(node->left, path + "0");
dfs(node->right, path + "1");
};
dfs(root, "");
return code;
}
// 将输入字符串编码为霍夫曼码
string encode(string s, unordered_map<char, string>& code) {
string res = "";
for (char ch : s) {
res += code[ch];
}
return res;
}
// 将霍夫曼码解码为原始字符串
string decode(string encoded, Node* root) {
string res = "";
Node* node = root;
for (char ch : encoded) {
if (ch == '0') {
node = node->left;
} else {
node = node->right;
}
if (node->left == nullptr && node->right == nullptr) {
res += node->ch;
node = root;
}
}
return res;
}
int main() {
string s;
cout << "请输入电文字符串:";
getline(cin, s);
Node* root = huffman_tree(s);
unordered_map<char, string> code = huffman_code(root);
string encoded = encode(s, code);
string decoded = decode(encoded, root);
cout << "霍夫曼编码:" << encoded << endl;
cout << "霍夫曼解码:" << decoded << endl;
delete root;
return 0;
}
```
这个程序中,我们首先定义了一个节点类,它包含字符、频率、左子节点和右子节点属性。我们使用一个 unordered_map 记录输入字符串中每个字符出现的次数,将它们放入一个小根堆中,逐个合并出霍夫曼树。在构造树的过程中,我们使用一个 unordered_map 来记录每个字符的霍夫曼编码。最后,我们使用 encode 函数将输入字符串编码成霍夫曼码,使用 decode 函数将霍夫曼码解码成原始字符串。注意,在程序结束时需要手动释放霍夫曼树的内存。
阅读全文