贪心算法—Huffman树及 Huffman编码 要求: 1.要求能够对任意指定的文件(不能仅文本文件,是任意!),读出并统计文件中出现的 1 字符及个数; 2. 对此文件中出现的字符进行Huffman编码,并输出。 即:编写一个读取此种格式文件类CHuffman,内部机制采用优先队列,用于建立Huffman树及进行Huffman编码输出,其用法可以如下所示: CHuffman hm("file.dat");//指定文件 hm.CreateTree(); //构建Huffman树 hm. OutputTree(O; //输出此Huffman树 hm.OutputCode(); //对所有字符输出01编码 对于输出树的形式可自行决定(如图形界面或字符界面)。要用c++实现
时间: 2024-02-18 11:05:51 浏览: 37
好的,这里是一个用C++实现的CHuffman类,可以满足您的要求:
```
#include <iostream>
#include <fstream>
#include <queue>
#include <map>
#include <stack>
using namespace std;
class CHuffman {
public:
CHuffman(const char* filename) {
m_filename = filename;
}
void CreateTree() {
ifstream infile(m_filename, ios::in | ios::binary);
if (!infile) {
cerr << "Error: cannot open file " << m_filename << endl;
return;
}
map<unsigned char, int> frequency;
// 统计字符出现的频率
unsigned char c;
while (infile.read((char*)&c, sizeof(unsigned char))) {
frequency[c]++;
}
// 构建Huffman树
priority_queue<Node*, vector<Node*>, Compare> q;
for (auto it = frequency.begin(); it != frequency.end(); it++) {
Node* node = new Node(it->first, it->second);
q.push(node);
}
while (q.size() > 1) {
Node* left = q.top();
q.pop();
Node* right = q.top();
q.pop();
Node* parent = new Node('\0', left->frequency + right->frequency, left, right);
q.push(parent);
}
m_root = q.top();
infile.close();
}
void OutputTree() {
if (!m_root) {
cerr << "Error: Huffman tree does not exist!" << endl;
return;
}
OutputTree(m_root, "");
}
void OutputCode() {
if (!m_root) {
cerr << "Error: Huffman tree does not exist!" << endl;
return;
}
stack<Node*> s;
s.push(m_root);
while (!s.empty()) {
Node* node = s.top();
s.pop();
if (node->left) {
node->left->code = node->code + "0";
s.push(node->left);
}
if (node->right) {
node->right->code = node->code + "1";
s.push(node->right);
}
if (!node->left && !node->right) {
cout << "Character " << node->c << " (ASCII code " << static_cast<int>(node->c) << ") has code " << node->code << endl;
}
}
}
private:
struct Node {
unsigned char c;
int frequency;
Node* left;
Node* right;
string code;
Node(unsigned char c, int frequency) : c(c), frequency(frequency), left(nullptr), right(nullptr) {}
Node(unsigned char c, int frequency, Node* left, Node* right) : c(c), frequency(frequency), left(left), right(right) {}
};
struct Compare {
bool operator() (Node* a, Node* b) const {
return a->frequency > b->frequency;
}
};
void OutputTree(Node* node, string padding) {
if (!node) {
return;
}
if (!node->left && !node->right) {
cout << padding << "Leaf: Character " << node->c << " (ASCII code " << static_cast<int>(node->c) << "), frequency " << node->frequency << endl;
} else {
cout << padding << "Node: frequency " << node->frequency << endl;
OutputTree(node->left, padding + " ");
OutputTree(node->right, padding + " ");
}
}
const char* m_filename;
Node* m_root;
};
```
使用方式如下:
```
CHuffman hm("file.dat");
hm.CreateTree();
hm.OutputTree();
hm.OutputCode();
```
其中,CreateTree()方法用于统计字符频率并构建Huffman树;OutputTree()方法用于输出Huffman树;OutputCode()方法用于输出Huffman编码。
希望能够满足您的需求!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)