从键盘输入一个数据文件(字符串),储存并统计各字符以及各字符出现的次数,并为这些字符构造一棵哈夫曼树,设计并输出每个字符对应的哈夫曼编码的c++的代码
时间: 2024-03-10 20:48:24 浏览: 60
好的,以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
struct TreeNode {
char ch;
int freq;
TreeNode* left;
TreeNode* right;
TreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct Compare {
bool operator() (const TreeNode* lhs, const TreeNode* rhs) const {
return lhs->freq > rhs->freq;
}
};
void getCharFreq(const string& filename, unordered_map<char, int>& freqMap) {
ifstream file(filename);
if (!file.is_open()) {
cout << "Error opening file!" << endl;
return;
}
char ch;
while (file >> noskipws >> ch) {
freqMap[ch]++;
}
file.close();
}
TreeNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
priority_queue<TreeNode*, vector<TreeNode*>, Compare> pq;
for (auto& p : freqMap) {
pq.push(new TreeNode(p.first, p.second));
}
while (pq.size() > 1) {
TreeNode* node1 = pq.top();
pq.pop();
TreeNode* node2 = pq.top();
pq.pop();
TreeNode* mergeNode = new TreeNode('$', node1->freq + node2->freq);
mergeNode->left = node1;
mergeNode->right = node2;
pq.push(mergeNode);
}
return pq.top();
}
void getHuffmanCode(TreeNode* root, unordered_map<char, string>& codeMap, string code = "") {
if (!root) {
return;
}
if (root->ch != '$') {
codeMap[root->ch] = code;
}
getHuffmanCode(root->left, codeMap, code + '0');
getHuffmanCode(root->right, codeMap, code + '1');
}
void printHuffmanCode(unordered_map<char, string>& codeMap) {
cout << "Huffman codes:" << endl;
for (auto& p : codeMap) {
cout << p.first << ": " << p.second << endl;
}
}
int main() {
string filename = "data.txt";
unordered_map<char, int> freqMap;
getCharFreq(filename, freqMap);
TreeNode* root = buildHuffmanTree(freqMap);
unordered_map<char, string> codeMap;
getHuffmanCode(root, codeMap);
printHuffmanCode(codeMap);
return 0;
}
```
这个程序中,我们首先使用 `getCharFreq()` 函数从指定的文件中读取字符并统计它们的出现次数,然后使用 `buildHuffmanTree()` 函数构建哈夫曼树,最后使用 `getHuffmanCode()` 函数为每个字符生成哈夫曼编码,并使用 `printHuffmanCode()` 函数输出它们。
阅读全文