从键盘输入一个数据文件(字符串),储存并统计各字符以及各字符出现的次数,设计并输出每个字符对应的哈夫曼编码的c++的代码
时间: 2024-03-10 14:46:51 浏览: 73
用C++实现的哈夫曼编码
好的,这里是一个C++实现的代码示例:
```c++
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;
// 定义节点类
class Node {
public:
char ch; // 节点对应的字符
int freq; // 节点对应的出现次数
Node* left; // 左子节点
Node* right; // 右子节点
Node(char c = '\0', int f = 0, Node* l = nullptr, Node* r = nullptr)
: ch(c), freq(f), left(l), right(r) {}
// 定义比较函数,用于堆排序
bool operator<(const Node& other) const {
return freq > other.freq;
}
};
// 统计各字符出现次数
unordered_map<char, int> count_chars(const string& s) {
unordered_map<char, int> freq;
for (char c : s) {
freq[c]++;
}
return freq;
}
// 构建哈夫曼树
Node* build_huffman_tree(const unordered_map<char, int>& freq) {
priority_queue<Node> heap;
for (const auto& p : freq) {
Node node(p.first, p.second);
heap.push(node);
}
while (heap.size() > 1) {
Node* left = new Node(heap.top()); heap.pop();
Node* right = new Node(heap.top()); heap.pop();
Node* parent = new Node('\0', left->freq + right->freq, left, right);
heap.push(*parent);
}
Node* root = new Node(heap.top()); heap.pop();
return root;
}
// 生成哈夫曼编码
unordered_map<char, string> generate_huffman_codes(Node* root) {
unordered_map<char, string> codes;
function<void(Node*, string)> dfs = [&codes, &dfs](Node* node, string code) {
if (node == nullptr) {
return;
}
if (node->ch != '\0') {
codes[node->ch] = code;
return;
}
dfs(node->left, code + '0');
dfs(node->right, code + '1');
};
dfs(root, "");
return codes;
}
int main() {
// 读取数据文件
string filename;
cout << "请输入数据文件名:";
cin >> filename;
ifstream fin(filename);
if (!fin) {
cerr << "无法打开文件!" << endl;
return 1;
}
string s((istreambuf_iterator<char>(fin)), istreambuf_iterator<char>());
// 统计各字符出现次数
auto freq = count_chars(s);
// 构建哈夫曼树
auto root = build_huffman_tree(freq);
// 生成哈夫曼编码
auto codes = generate_huffman_codes(root);
// 输出每个字符对应的哈夫曼编码
cout << "字符\t出现次数\t哈夫曼编码" << endl;
for (const auto& p : freq) {
char c = p.first;
int f = p.second;
string code = codes[c];
cout << c << "\t" << f << "\t\t" << code << endl;
}
return 0;
}
```
这段代码首先读取一个数据文件,并使用 `count_chars` 函数统计各字符出现次数。然后,使用 `build_huffman_tree` 函数构建哈夫曼树,并使用 `generate_huffman_codes` 函数生成哈夫曼编码。最后,输出每个字符对应的哈夫曼编码。
注意,在 C++ 中,我们需要手动管理内存,需要在合适的时候释放堆上分配的内存,以避免内存泄漏。在上面的代码中,我们在 `build_huffman_tree` 函数和 `generate_huffman_codes` 函数中分别使用了 `new` 运算符分配了新节点的内存,需要在程序结束后使用 `delete` 运算符释放这些内存。
阅读全文