请用C++创建HuffmanTree和编码表
时间: 2023-06-13 14:08:16 浏览: 51
好的,以下是C++实现HuffmanTree和编码表的示例代码:
```c++
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct Node {
char ch;
int freq;
Node* left;
Node* right;
Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};
struct cmp {
bool operator() (Node* a, Node* b) {
return a->freq > b->freq;
}
};
Node* buildHuffmanTree(string s) {
unordered_map<char, int> freqMap;
for (char c : s) {
freqMap[c]++;
}
priority_queue<Node*, vector<Node*>, cmp> pq;
for (auto p : freqMap) {
pq.push(new Node(p.first, p.second));
}
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
Node* parent = new Node('$', left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}
return pq.top();
}
void buildEncodingTable(Node* root, string code, unordered_map<char, string>& encodingTable) {
if (!root) {
return;
}
if (root->ch != '$') {
encodingTable[root->ch] = code;
}
buildEncodingTable(root->left, code + "0", encodingTable);
buildEncodingTable(root->right, code + "1", encodingTable);
}
int main() {
string s = "This is a test string.";
Node* root = buildHuffmanTree(s);
unordered_map<char, string> encodingTable;
buildEncodingTable(root, "", encodingTable);
for (auto p : encodingTable) {
cout << p.first << ": " << p.second << endl;
}
return 0;
}
```
在这个例子中,我们首先通过遍历字符串计算每个字符的出现频率,然后将每个字符和对应的频率构建成一个节点,并用一个优先队列来维护这些节点。每次从队列中取出频率最小的两个节点,将它们合并成一个节点,并将这个新节点加入队列中。当队列中只有一个节点时,我们就构建好了Huffman Tree。接下来,我们对Huffman Tree进行前序遍历,同时记录每个字符对应的编码(向左为0,向右为1),并将其存放在一个哈希表中。最后,我们输出这个哈希表,即得到了编码表。
需要注意的是,这个示例代码中使用了unorderd_map来存放编码表。如果你的编译器不支持C++11的哈希表,可以使用STL库中的map来代替,但需要将编码表的类型改为map<char, string>。