卷帘红尘亦爱她 发表于 2024-06-06 22:55
@FishC1 以此I went to a lot of place Disnep s park ...
下面是用C++实现的哈夫曼编码和译码，并输出每个字母的哈夫曼编码的代码：
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
struct Node {
char data;
int freq;
Node* left;
Node* right;
Node(char data, int freq) {
this->data = data;
this->freq = freq;
left = right = NULL;
}
};
struct Compare {
bool operator()(Node* left, Node* right) {
return left->freq > right->freq;
}
};
unordered_map<char, string> huffmanCodes;
void encode(Node* root, string str) {
if (root == nullptr) {
return;
}
if (!root->left && !root->right) {
huffmanCodes = str;
}
encode(root->left, str + "0");
encode(root->right, str + "1");
}
void decode(Node* root, int& index, string str) {
if (root == nullptr) {
return;
}
if (!root->left && !root->right) {
cout << root->data;
return;
}
index++;
if (str == '0') {
decode(root->left, index, str);
} else {
decode(root->right, index, str);
}
}
void buildHuffmanTree(string text) {
unordered_map<char, int> freq;
for (char c : text) {
freq++;
}
priority_queue<Node*, vector<Node*>, Compare> pq;
for (auto pair : freq) {
pq.push(new Node(pair.first, pair.second));
}
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
int sumFreq = left->freq + right->freq;
Node* newNode = new Node('\0', sumFreq);
newNode->left = left;
newNode->right = right;
pq.push(newNode);
}
Node* root = pq.top();
encode(root, "");
delete root;
}
string huffmanEncode(string text) {
string encodedText = "";
for (char c : text) {
encodedText += huffmanCodes;
}
return encodedText;
}
string huffmanDecode(string encodedText) {
string decodedText = "";
int index = -1;
while (index < (int)encodedText.size() - 2) {
decode(root, index, encodedText);
}
return decodedText;
}
int main() {
string text = "I went to a lot of place Disnep s park and summer holiday l made some new friends Do you know who they are Let me tell you they are my favorite books l like books very much like reading science books English books Chinese books cartoon books and so on";
cout << "Original Text: " << text << endl;
buildHuffmanTree(text);
cout << "Huffman Codes: " << endl;
for (auto pair : huffmanCodes) {
cout << pair.first << ": " << pair.second << endl;
}
string encodedText = huffmanEncode(text);
cout << "Encoded Text: " << encodedText << endl;
string decodedText = huffmanDecode(encodedText);
cout << "Decoded Text: " << decodedText << endl;
return 0;
}
请注意，上述代码中的`root`变量需要根据实际的Huffman树来进行定义。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。