huffman编码C++代码

Huffman编码是一种用于数据压缩的无损编码算法，它通过构建一颗特殊的树（霍夫曼树）来分配给每个字符一个独特的二进制编码。这里是一个简单的Huffman编码C++实现步骤：

1. 首先，你需要创建一个节点结构，包含频率、字符和左子节点和右子节点。

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode* left, *right;
};

2. 然后定义优先队列（最小堆），存放所有字符及其频率，并实现插入和删除操作。

class PriorityQueue {
    // ... (实现优先队列)
public:
    void insert(HuffmanNode* node);
    HuffmanNode* extract();
};

3. 接下来编写生成Huffman树的函数，通过不断合并频率最低的两个节点直到只剩下一个为止。

HuffmanNode* buildHuffmanTree(PriorityQueue& pq) {
    if (pq.size() == 1) return pq.top(); // 只剩一个就是叶子节点

    HuffmanNode* left = pq.extract();
    HuffmanNode* right = pq.extract();
    HuffmanNode* newNode = new HuffmanNode(left->freq + right->freq, '\0', left, right);
    pq.insert(newNode);

    // 递归合并剩下的节点
    return buildHuffmanTree(pq);
}

4. 最后，你可以遍历Huffman树来生成编码表。

void generateCodes(HuffmanNode* root, std::string code, std::map<char, std::string>& codes) {
    if (!root->left && !root->right) codes[root->ch] = code; // 如果是叶子节点，添加到编码表
    else {
        generateCodes(root->left, code + "0", codes);
        generateCodes(root->right, code + "1", codes);
    }
}

完整代码会包括主函数部分，处理输入数据计算频率，构建并打印编码表。注意这只是一个基础版本，实际应用中可能需要更复杂的数据结构和错误处理。