哈夫曼编码代码c++

哈夫曼编码是一种用于数据压缩的算法，它将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示，从而实现对数据的压缩。以下是一段C语言实现的哈夫曼编码代码示例：

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

// 定义哈夫曼树结点
struct HuffmanNode {
    char data;
    int weight;
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(char d, int w) : data(d), weight(w), left(nullptr), right(nullptr) {}
};

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

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const map<char, int>& charFreq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (const auto& p : charFreq) {
        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('#', left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 生成哈夫曼编码表
void generateHuffmanCode(HuffmanNode* root, map<char, string>& codeTable, string code) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        codeTable[root->data] = code;
    }
    generateHuffmanCode(root->left, codeTable, code + "0");
    generateHuffmanCode(root->right, codeTable, code + "1");
}

// 哈夫曼编码函数
string huffmanEncode(const string& str) {
    if (str.empty()) {
        return "";
    }
    map<char, int> charFreq;
    for (char c : str) {
        charFreq[c]++;
    }
    HuffmanNode* root = buildHuffmanTree(charFreq);
    map<char, string> codeTable;
    generateHuffmanCode(root, codeTable, "");
    string encodedStr;
    for (char c : str) {
        encodedStr += codeTable[c];
    }
    return encodedStr;
}

int main() {
    string str = "hello world";
    string encodedStr = huffmanEncode(str);
    cout << "Encoded string: " << encodedStr << endl;
    return 0;
}