写一段C++代码【问题描述】使用贪心算法求解Huffman编码问题,具体来说就是,根据每个字符的出现频率,使用最小堆构造最小优先队列,构造出字符的最优二进制表示,即前缀码。 【输入形式】在屏幕上输入字符个数和每个字符的频率。 【输出形式】每个字符的Huffman编码。字符从a开始,依次为b, c, ... 【样例输入】 6 45 13 12 16 9 5 【样例输出】 a 0 b 101 c 100 d 111 e 1101 f 1100
时间: 2024-02-12 08:06:55 浏览: 60
抱歉,我是一个自然语言处理模型,不能直接在屏幕上进行输入输出操作。以下是 C++ 代码实现:
```
#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct TreeNode {
char ch;
int freq;
TreeNode *left, *right;
TreeNode(char c, int f) : ch(c), freq(f), left(NULL), right(NULL) {}
~TreeNode() {
delete left;
delete right;
}
};
struct cmp {
bool operator()(TreeNode* a, TreeNode* b) {
return a->freq > b->freq;
}
};
void getHuffmanCode(TreeNode* root, string code) {
if (root->left == NULL && root->right == NULL) {
cout << root->ch << " " << code << endl;
return;
}
getHuffmanCode(root->left, code + "0");
getHuffmanCode(root->right, code + "1");
}
void huffmanCoding(int n, int freq[]) {
priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
for (int i = 0; i < n; i++) {
pq.push(new TreeNode('a' + i, freq[i]));
}
while (pq.size() > 1) {
TreeNode* left = pq.top();
pq.pop();
TreeNode* right = pq.top();
pq.pop();
TreeNode* parent = new TreeNode('#', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
getHuffmanCode(pq.top(), "");
}
int main() {
int n;
cin >> n;
int freq[n];
for (int i = 0; i < n; i++) {
cin >> freq[i];
}
huffmanCoding(n, freq);
return 0;
}
```
阅读全文