编程实现赫夫曼编码算法

以下是C++实现赫夫曼编码算法的代码，其中包括构造赫夫曼树和求解赫夫曼编码的函数：

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;

// 赫夫曼树结点
struct HuffmanNode {
    int weight; // 权值
    char ch; // 字符
    HuffmanNode *left, *right; // 左右子树
    HuffmanNode(int w, char c = '\0') : weight(w), ch(c), left(nullptr), right(nullptr) {}
};

// 比较器，用于优先队列
struct cmp {
    bool operator() (HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构造赫夫曼树
HuffmanNode* buildHuffmanTree(int* weights, int n) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (int i = 0; i < n; i++) {
        pq.push(new HuffmanNode(weights[i], char('a' + i)));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 递归求解赫夫曼编码
void getHuffmanCode(HuffmanNode* root, string code, map<char, string>& res) {
    if (!root) return;
    if (!root->left && !root->right) {
        res[root->ch] = code;
        return;
    }
    getHuffmanCode(root->left, code + "0", res);
    getHuffmanCode(root->right, code + "1", res);
}

// 求解赫夫曼编码
map<char, string> HuffmanCoding(int* weights, int n) {
    HuffmanNode* root = buildHuffmanTree(weights, n);
    map<char, string> res;
    getHuffmanCode(root, "", res);
    return res;
}

int main() {
    int weights[] = {5, 2, 4, 7, 1, 3, 6};
    int n = sizeof(weights) / sizeof(weights[0]);
    map<char, string> res = HuffmanCoding(weights, n);
    for (auto it = res.begin(); it != res.end(); it++) {
        cout << it->first << ": " << it->second << endl;
    }
    return 0;
}