使用c++编程,并可自由定义变量
时间: 2024-03-21 11:41:15 浏览: 22
好的,下面是一个使用C++实现哈夫曼编码的示例代码,可以自由定义变量:
```c++
#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;
// 定义节点类
class Node {
public:
char ch;
int freq;
Node* left;
Node* right;
Node(char ch, int freq, Node* left = nullptr, Node* right = nullptr) {
this->ch = ch;
this->freq = freq;
this->left = left;
this->right = right;
}
// 定义小于运算符,用于堆排序
bool operator<(const Node& other) const {
return freq > other.freq;
}
};
// 统计字符频率
unordered_map<char, int> count_frequency(string text) {
unordered_map<char, int> freq;
for (char ch : text) {
freq[ch]++;
}
return freq;
}
// 构建哈夫曼树
Node* build_huffman_tree(unordered_map<char, int>& freq) {
priority_queue<Node> pq;
for (auto& p : freq) {
pq.push(Node(p.first, p.second));
}
while (pq.size() > 1) {
Node* left = new Node(pq.top().ch, pq.top().freq, pq.top().left, pq.top().right);
pq.pop();
Node* right = new Node(pq.top().ch, pq.top().freq, pq.top().left, pq.top().right);
pq.pop();
Node* parent = new Node('\0', left->freq + right->freq, left, right);
pq.push(*parent);
}
return new Node(pq.top().ch, pq.top().freq, pq.top().left, pq.top().right);
}
// 生成编码方案
void generate_codes(Node* node, string code, unordered_map<char, string>& codes) {
if (node->left == nullptr && node->right == nullptr) {
codes[node->ch] = code;
return;
}
generate_codes(node->left, code + "0", codes);
generate_codes(node->right, code + "1", codes);
}
// 测试
int main() {
string text = "this is an example of huffman encoding";
unordered_map<char, int> freq = count_frequency(text);
Node* tree = build_huffman_tree(freq);
unordered_map<char, string> codes;
generate_codes(tree, "", codes);
for (auto& p : codes) {
cout << p.first << ": " << p.second << endl;
}
return 0;
}
```
在这个示例代码中,我们使用了C++标准库中的`unordered_map`和`priority_queue`,分别用于统计字符频率和构建哈夫曼树。同时,我们还使用了递归算法生成每个字符的编码方案。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)