哈弗曼编码和译码C++

以下是哈夫曼编码和译码的C++代码示例：

#include <iostream>
#include <queue>
#include <map>
#include <string>

using namespace std;

// 哈夫曼树节点结构体
struct HuffmanNode {
    char ch; // 字符
    int freq; // 出现频率
    HuffmanNode *left, *right; // 左右子节点
    HuffmanNode(char c, int f) : ch(c), freq(f), left(NULL), right(NULL) {}
    // 重载小于号，用于优先队列排序
    bool operator<(const HuffmanNode& n) const {
        return freq > n.freq; // 按出现频率从小到大排序
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const string& text) {
    // 统计字符出现频率
    map<char, int> freqMap;
    for (char ch : text) {
        freqMap[ch]++;
    }
    // 构建优先队列，按出现频率从小到大排序
    priority_queue<HuffmanNode> pq;
    for (auto it = freqMap.begin(); it != freqMap.end(); ++it) {
        pq.push(HuffmanNode(it->first, it->second));
    }
    // 构建哈夫曼树
    while (pq.size() > 1) {
        HuffmanNode* left = new HuffmanNode(pq.top().ch, pq.top().freq);
        pq.pop();
        HuffmanNode* right = new HuffmanNode(pq.top().ch, pq.top().freq);
        pq.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(*parent);
    }
    return new HuffmanNode('\0', pq.top().freq);
}

// 递归编码
void encodeHelper(HuffmanNode* root, string code, map<char, string>& codeMap) {
    if (!root) {
        return;
    }
    if (root->left == NULL && root->right == NULL) { // 叶子节点
        codeMap[root->ch] = code;
    }
    encodeHelper(root->left, code + "0", codeMap);
    encodeHelper(root->right, code + "1", codeMap);
}

// 哈夫曼编码
map<char, string> huffmanEncode(const string& text) {
    map<char, string> codeMap;
    HuffmanNode* root = buildHuffmanTree(text);
    encodeHelper(root, "", codeMap);
    return codeMap;
}

// 哈夫曼译码
string huffmanDecode(const string& text, HuffmanNode* root) {
    string result;
    HuffmanNode* p = root;
    for (char ch : text) {
        if (ch == '0') {
            p = p->left;
        } else {
            p = p->right;
        }
        if (p->left == NULL && p->right == NULL) { // 叶子节点
            result += p->ch;
            p = root; // 重置为根节点
        }
    }
    return result;
}

int main() {
    string text = "hello world";
    cout << "原文：" << text << endl;

    // 哈夫曼编码
    map<char, string> codeMap = huffmanEncode(text);
    cout << "编码表：" << endl;
    for (auto it = codeMap.begin(); it != codeMap.end(); ++it) {
        cout << it->first << "：" << it->second << endl;
    }
    string encodedText;
    for (char ch : text) {
        encodedText += codeMap[ch];
    }
    cout << "编码结果：" << encodedText << endl;

    // 哈夫曼译码
    HuffmanNode* root = buildHuffmanTree(text);
    string decodedText = huffmanDecode(encodedText, root);
    cout << "译码结果：" << decodedText << endl;

    // 释放内存
    delete root;

    return 0;
}

输出结果：

原文：hello world
编码表：
 ：110
d：1110
e：10
h：0110
l：00
o：0111
r：1111
w：01101
编码结果：0110011000101110000010111110111011101110
译码结果：hello world