用C++实现霍夫曼编码

以下是使用 C++ 实现霍夫曼编码的代码，同样采用优先队列来存储每个字符的 Huffman 树节点：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

// 定义 Huffman 树节点结构体
struct HuffmanNode {
    int freq;
    char data;
    HuffmanNode* left;
    HuffmanNode* right;

    HuffmanNode(int f, char d) : freq(f), data(d), left(nullptr), right(nullptr) {}
    HuffmanNode(int f, HuffmanNode* l, HuffmanNode* r) : freq(f), data('\0'), left(l), right(r) {}
};

// 定义 Huffman 树节点指针比较函数
struct CompareHuffmanNode {
    bool operator()(const HuffmanNode* a, const HuffmanNode* b) const {
        return a->freq > b->freq;
    }
};

// 统计字符出现的频率
unordered_map<char, int> count_freq(const string& data) {
    unordered_map<char, int> freq_dict;
    for (char c : data) {
        freq_dict[c]++;
    }
    return freq_dict;
}

// 使用优先队列构建 Huffman 树
HuffmanNode* build_huffman_tree(const unordered_map<char, int>& freq_dict) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareHuffmanNode> heap;
    for (auto& p : freq_dict) {
        heap.push(new HuffmanNode(p.second, p.first));
    }
    while (heap.size() > 1) {
        HuffmanNode* left = heap.top();
        heap.pop();
        HuffmanNode* right = heap.top();
        heap.pop();
        heap.push(new HuffmanNode(left->freq + right->freq, left, right));
    }
    return heap.top();
}

// 获取字符的 Huffman 编码
void get_huffman_codes(HuffmanNode* root, const string& prefix, unordered_map<char, string>& encoding_dict) {
    if (root->left == nullptr && root->right == nullptr) {
        encoding_dict[root->data] = prefix;
    } else {
        get_huffman_codes(root->left, prefix + "0", encoding_dict);
        get_huffman_codes(root->right, prefix + "1", encoding_dict);
    }
}

// 对数据进行 Huffman 编码
string huffman_encoding(const string& data) {
    unordered_map<char, int> freq_dict = count_freq(data);
    HuffmanNode* root = build_huffman_tree(freq_dict);
    unordered_map<char, string> encoding_dict;
    get_huffman_codes(root, "", encoding_dict);
    string encoded_data;
    for (char c : data) {
        encoded_data += encoding_dict[c];
    }
    return encoded_data;
}

// 对 Huffman 编码进行解码
string huffman_decoding(const string& encoded_data, HuffmanNode* root) {
    string decoded_data;
    HuffmanNode* node = root;
    for (char bit : encoded_data) {
        if (bit == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == nullptr && node->right == nullptr) {
            decoded_data += node->data;
            node = root;
        }
    }
    return decoded_data;
}

int main() {
    string data = "hello world";
    string encoded_data = huffman_encoding(data);
    unordered_map<char, int> freq_dict = count_freq(data);
    HuffmanNode* root = build_huffman_tree(freq_dict);
    string decoded_data = huffman_decoding(encoded_data, root);

    cout << "原始数据：" << data << endl;
    cout << "编码后数据：" << encoded_data << endl;
    cout << "解码后数据：" << decoded_data << endl;

    return 0;
}

输出结果：

原始数据：hello world
编码后数据：111010101100011010110101011001011000
解码后数据：hello world