c++求解哈夫曼编码

好的，关于求解哈夫曼编码，我可以给你一些思路和代码实现。

首先，哈夫曼编码是一种可变长度编码，它是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀。哈夫曼编码的基本思想是：将出现频率较高的字符用较短的编码，出现频率较低的字符用较长的编码，从而使整个编码的平均长度最短。

下面是求解哈夫曼编码的基本步骤：

1. 统计每个字符出现的频率。
2. 将每个字符及其频率构建成一个森林（每个节点都是一棵只有一个节点的树）。
3. 从森林中选取两棵根节点权值最小的树合并成一棵新树，新树的权值为两棵树的权值之和。
4. 将新树插入到森林中，并删除原来的两棵树。
5. 重复步骤3和4，直到森林中只剩下一棵树为止。
6. 对于每个字符，从根节点开始遍历哈夫曼树，左子树为0，右子树为1，得到该字符的哈夫曼编码。

下面是 C++ 代码实现：

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

// 定义哈夫曼树节点
struct HuffmanNode {
    char ch; // 字符
    int freq; // 频率
    HuffmanNode *left, *right; // 左右子节点
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于优先队列中的排序
struct cmp {
    bool operator() (HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 统计每个字符出现的频率
map<char, int> getFreq(string s) {
    map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }
    return freq;
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(map<char, int> freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (auto p : freq) {
        pq.push(new HuffmanNode(p.first, p.second));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 递归遍历哈夫曼树，得到每个字符的哈夫曼编码
void getHuffmanCode(HuffmanNode* root, string code, map<char, string>& huffmanCode) {
    if (!root) return;
    if (root->ch != '\0') {
        huffmanCode[root->ch] = code;
    }
    getHuffmanCode(root->left, code + "0", huffmanCode);
    getHuffmanCode(root->right, code + "1", huffmanCode);
}

// 对字符串进行哈夫曼编码
string encode(string s, map<char, string> huffmanCode) {
    string res = "";
    for (char c : s) {
        res += huffmanCode[c];
    }
    return res;
}

// 对哈夫曼编码进行解码
string decode(string s, HuffmanNode* root) {
    string res = "";
    HuffmanNode* cur = root;
    for (char c : s) {
        if (c == '0') {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
        if (cur->ch != '\0') {
            res += cur->ch;
            cur = root;
        }
    }
    return res;
}

int main() {
    string s = "hello world";
    map<char, int> freq = getFreq(s);
    HuffmanNode* root = buildHuffmanTree(freq);
    map<char, string> huffmanCode;
    getHuffmanCode(root, "", huffmanCode);
    string encoded = encode(s, huffmanCode);
    string decoded = decode(encoded, root);
    cout << "原字符串：" << s << endl;
    cout << "哈夫曼编码：" << encoded << endl;
    cout << "解码后字符串：" << decoded << endl;
    return 0;
}