使用c++写代码使得输入字符串,输出字符串的哈夫曼编码; 输入文本文件(英文),输出哈夫曼编码文件
时间: 2023-06-27 08:02:03 浏览: 142
以下是使用C++实现输入字符串输出哈夫曼编码的代码:
```c++
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <fstream>
using namespace std;
// 哈夫曼树节点
struct HuffmanNode {
char ch; // 字符
int freq; // 出现频率
HuffmanNode *left, *right; // 左右子节点
HuffmanNode(char c, int f) {
ch = c;
freq = f;
left = right = nullptr;
}
// 用于优先队列排序
bool operator<(const HuffmanNode& other) const {
return freq > other.freq;
}
};
// 哈夫曼树
class HuffmanTree {
private:
HuffmanNode* root; // 根节点
unordered_map<char, string> codes; // 字符对应的哈夫曼编码
void buildCodes(HuffmanNode* node, string code) {
if (!node) return;
if (node->ch != '\0') codes[node->ch] = code;
buildCodes(node->left, code + "0");
buildCodes(node->right, code + "1");
}
public:
HuffmanTree(string s) {
unordered_map<char, int> freq;
for (char c : s) freq[c]++;
priority_queue<HuffmanNode> pq;
for (auto& p : freq) pq.push(HuffmanNode(p.first, p.second));
while (pq.size() > 1) {
HuffmanNode* left = new HuffmanNode(pq.top().ch, pq.top().freq);
pq.pop();
HuffmanNode* right = new HuffmanNode(pq.top().ch, pq.top().freq);
pq.pop();
HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(*parent);
}
root = new HuffmanNode(pq.top().ch, pq.top().freq);
buildCodes(root, "");
}
~HuffmanTree() {
deleteTree(root);
}
void deleteTree(HuffmanNode* node) {
if (!node) return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
string getCode(char c) {
return codes[c];
}
string encode(string s) {
string code;
for (char c : s) code += getCode(c);
return code;
}
};
int main() {
string s;
cout << "请输入待编码字符串:" << endl;
getline(cin, s);
HuffmanTree tree(s);
string code = tree.encode(s);
cout << "哈夫曼编码结果:" << endl;
cout << code << endl;
ofstream file("output.txt");
if (file.is_open()) {
file << code;
file.close();
cout << "已输出至文件 output.txt" << endl;
}
else cout << "无法打开文件" << endl;
return 0;
}
```
这段代码会先让用户输入待编码的字符串,然后根据该字符串构建哈夫曼树,并输出每个字符对应的哈夫曼编码。最后将编码结果输出至文件 output.txt 中。
需要注意的是,如果要从文件中读取文本进行编码,可以使用 ifstream 类来读取文件,并将读取到的字符串传递给 HuffmanTree 的构造函数。
阅读全文