如何使用C++语言实现赫夫曼编码的实现

赫夫曼编码是一种前缀编码，它将字符用不等长的编码表示，使得出现频率高的字符编码短，出现频率低的字符编码长。下面是使用C++语言实现赫夫曼编码的实现方法：

1.定义赫夫曼树结构体

struct HuffmanNode {
    char ch;              // 字符
    int weight;           // 权值
    int parent, lchild, rchild;  // 父节点、左子节点、右子节点
};

2.定义优先队列

priority_queue<HuffmanNode, vector<HuffmanNode>, function<bool(HuffmanNode, HuffmanNode)>> pq([](HuffmanNode a, HuffmanNode b) {
    return a.weight > b.weight; // 小根堆，队列头部为权值最小的节点
});

3.构建赫夫曼树

void buildHuffmanTree(HuffmanNode* huffmanTree, int n) {
    for (int i = 0; i < n; i++) {
        pq.push(huffmanTree[i]);
    }

    for (int i = n; i < 2 * n - 1; i++) {
        HuffmanNode left = pq.top();
        pq.pop();
        HuffmanNode right = pq.top();
        pq.pop();
        huffmanTree[i].weight = left.weight + right.weight;
        huffmanTree[i].lchild = left.ch == '\0' ? left.lchild : i - 1;
        huffmanTree[i].rchild = right.ch == '\0' ? right.lchild : i - 2;
        huffmanTree[i].parent = -1;
        pq.push(huffmanTree[i]);
    }
}

4.生成赫夫曼编码

void generateHuffmanCode(HuffmanNode* huffmanTree, int n) {
    for (int i = 0; i < n; i++) {
        int cur = i;
        string tmp = "";
        while (huffmanTree[cur].parent != -1) {
            int parent = huffmanTree[cur].parent;
            if (huffmanTree[parent].lchild == cur) {
                tmp += '0';
            } else {
                tmp += '1';
            }
            cur = parent;
        }
        reverse(tmp.begin(), tmp.end());
        huffmanTree[i].code = tmp;
    }
}

完整代码如下：