87 lines
2.2 KiB
C++
87 lines
2.2 KiB
C++
//
|
|
// Created by grtsinry43 on 5/8/25.
|
|
//
|
|
|
|
#include "problem5.h"
|
|
|
|
#include <iostream>
|
|
#include <queue>
|
|
#include <unordered_map>
|
|
#include <vector>
|
|
|
|
// 定义哈夫曼树节点
|
|
struct HuffmanNode {
|
|
char character;
|
|
int frequency;
|
|
HuffmanNode *left;
|
|
HuffmanNode *right;
|
|
|
|
HuffmanNode(char ch, int freq) : character(ch), frequency(freq), left(nullptr), right(nullptr) {}
|
|
};
|
|
|
|
// 比较器，用于优先队列
|
|
struct Compare {
|
|
bool operator()(HuffmanNode *a, HuffmanNode *b) {
|
|
return a->frequency > b->frequency;
|
|
}
|
|
};
|
|
|
|
// 构建哈夫曼树
|
|
HuffmanNode* buildHuffmanTree(const std::unordered_map<char, int> &frequencyTable) {
|
|
std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
|
|
|
|
// 将每个字符和频率插入优先队列
|
|
for (const auto &entry : frequencyTable) {
|
|
pq.push(new HuffmanNode(entry.first, entry.second));
|
|
}
|
|
|
|
// 构建哈夫曼树
|
|
while (pq.size() > 1) {
|
|
HuffmanNode *left = pq.top(); pq.pop();
|
|
HuffmanNode *right = pq.top(); pq.pop();
|
|
|
|
HuffmanNode *merged = new HuffmanNode('\0', left->frequency + right->frequency);
|
|
merged->left = left;
|
|
merged->right = right;
|
|
|
|
pq.push(merged);
|
|
}
|
|
|
|
return pq.top();
|
|
}
|
|
|
|
// 生成哈夫曼编码
|
|
void generateHuffmanCodes(HuffmanNode *root, const std::string &code, std::unordered_map<char, std::string> &huffmanCodes) {
|
|
if (!root) return;
|
|
|
|
if (!root->left && !root->right) {
|
|
huffmanCodes[root->character] = code;
|
|
}
|
|
|
|
generateHuffmanCodes(root->left, code + "0", huffmanCodes);
|
|
generateHuffmanCodes(root->right, code + "1", huffmanCodes);
|
|
}
|
|
|
|
// 主函数
|
|
int problem_5() {
|
|
// 示例字符频率表
|
|
std::unordered_map<char, int> frequencyTable = {
|
|
{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}
|
|
};
|
|
|
|
// 构建哈夫曼树
|
|
HuffmanNode *root = buildHuffmanTree(frequencyTable);
|
|
|
|
// 生成哈夫曼编码
|
|
std::unordered_map<char, std::string> huffmanCodes;
|
|
generateHuffmanCodes(root, "", huffmanCodes);
|
|
|
|
// 输出每个字符的哈夫曼编码
|
|
std::cout << "Huffman Codes:\n";
|
|
for (const auto &entry : huffmanCodes) {
|
|
std::cout << entry.first << ": " << entry.second << "\n";
|
|
}
|
|
|
|
return 0;
|
|
}
|