C++实现哈夫曼编码：字符频率统计、树构建、编码解码

本文将详细讲解用C++实现哈夫曼编码的步骤，包括字符频率统计、哈夫曼树构建、编码和解码过程。代码示例清晰易懂，并附带必要的说明和解释。

1. 代码实现

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

// 定义哈夫曼树节点类
class HuffmanNode {
public:
    char data;              // 存储字符
    int freq;               // 存储字符出现频率
    HuffmanNode* left;      // 指向左子节点的指针
    HuffmanNode* right;     // 指向右子节点的指针

    // 构造函数
    HuffmanNode(char c, int f) : data(c), freq(f), left(nullptr), right(nullptr) {}
    // 拷贝构造函数，用于优先队列中的元素比较
    HuffmanNode(const HuffmanNode& rhs) : data(rhs.data), freq(rhs.freq), left(rhs.left), right(rhs.right) {}
};

// 定义比较函数，用于优先队列中的元素比较
class Compare {
public:
    bool operator()(const HuffmanNode* lhs, const HuffmanNode* rhs) const {
        return lhs->freq > rhs->freq;
    }
};

// 定义哈夫曼树类
class HuffmanTree {
public:
    // 建立哈夫曼树
    void build(const string& s) {
        unordered_map<char, int> freq;              // 存储字符频率的哈希表
        for (char c : s) freq[c]++;                 // 统计每个字符的出现频率
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;    // 用于构建哈夫曼树的优先队列
        // 将每个字符的频率初始化为一个节点，并加入优先队列中
        for (auto it = freq.begin(); it != freq.end(); it++) {
            HuffmanNode* node = new HuffmanNode(it->first, it->second);
            pq.push(node);
        }
        // 通过不断取出优先队列中最小的两个节点，合并成一个新节点，直到队列中只剩一个节点，即为哈夫曼树的根节点
        while (pq.size() > 1) {
            HuffmanNode* left = pq.top(); pq.pop();
            HuffmanNode* right = pq.top(); pq.pop();
            HuffmanNode* parent = new HuffmanNode('�', left->freq + right->freq);
            parent->left = left;
            parent->right = right;
            pq.push(parent);
        }
        root = pq.top();
    }

    // 哈夫曼编码
    void encode(const string& s) {
        unordered_map<char, string> code;           // 存储字符编码的哈希表
        encodeHelper(root, '', code);               // 递归地生成每个字符的编码
        cout << 'Huffman Code:' << endl;
        for (char c : s) cout << code[c] << ' ';    // 输出每个字符的编码
        cout << endl;
    }

    // 哈夫曼解码
    void decode(const string& s) {
        string result;
        HuffmanNode* curr = root;
        for (char c : s) {
            if (c == '0') curr = curr->left;
            else curr = curr->right;
            if (!curr->left && !curr->right) {     // 遇到叶子节点，输出对应字符并回到根节点
                result += curr->data;
                curr = root;
            }
        }
        cout << 'Decoded string: ' << result << endl;
    }

private:
    HuffmanNode* root;      // 指向根节点的指针

    // 递归地生成每个字符的编码
    void encodeHelper(HuffmanNode* node, string code, unordered_map<char, string>& table) {
        if (!node->left && !node->right) {     // 遇到叶子节点，将字符和对应的编码存入哈希表
            table[node->data] = code;
            return;
        }
        encodeHelper(node->left, code + '0', table);
        encodeHelper(node->right, code + '1', table);
    }
};

int main() {
    string s;
    cout << 'Input a string: ';
    getline(cin, s);
    HuffmanTree tree;
    tree.build(s);
    cout << 'Character frequencies:' << endl;
    unordered_map<char, int> freq;              // 存储字符频率的哈希表
    for (char c : s) freq[c]++;                 // 统计每个字符的出现频率
    for (auto it = freq.begin(); it != freq.end(); it++) {
        cout << it->first << ': ' << it->second << endl;
    }
    tree.encode(s);
    cout << 'Input a Huffman code: ';
    getline(cin, s);
    tree.decode(s);
    return 0;
}

2. 代码解释

类定义
- HuffmanNode 类：表示哈夫曼树中的节点，包含字符 data、频率 freq 以及指向左右子节点的指针 left 和 right。
- Compare 类：用于比较两个节点的频率，在优先队列中使用。
- HuffmanTree 类：表示哈夫曼树，包含构建树 build、编码 encode 和解码 decode 等方法。
构建哈夫曼树 build 方法
- 统计字符串中每个字符出现的频率，并存储在 freq 哈希表中。
- 使用优先队列 pq，按照频率从小到大存储节点。
- 循环取出频率最小的两个节点，合并成一个新的节点，并将新的节点加入优先队列。
- 重复上述步骤，直到优先队列中只剩下一个节点，该节点即为哈夫曼树的根节点。
哈夫曼编码 encode 方法
- 使用 encodeHelper 函数递归地遍历哈夫曼树，生成每个字符的编码。
- 将字符和对应的编码存储在 code 哈希表中。
- 输出每个字符的编码。
哈夫曼解码 decode 方法
- 从编码字符串的第一个字符开始，根据当前字符是 '0' 还是 '1'，分别向左或向右子节点移动。
- 当遇到叶子节点时，输出该节点的字符，并将当前节点移动到根节点。
- 重复上述步骤，直到解码完整个编码字符串。

3. 总结

本文介绍了用C++实现哈夫曼编码的完整步骤，代码示例清晰易懂。哈夫曼编码是一种高效的数据压缩算法，在实际应用中具有重要价值。希望本文能帮助您理解哈夫曼编码的原理和实现方法。

注意：

上述代码中使用了unordered_map和priority_queue等STL容器，如果您的编译器不支持C++11及以上的标准，需要将其替换为其他容器或手写实现。
为了提高可读性，代码中使用了注释来解释每个部分的功能和逻辑。
可以根据实际需要修改代码，例如增加错误处理机制、优化代码效率等。

希望本文对您有所帮助。如果您有任何问题，请随时留言。