用c++或者C语言实现Huffman编码

Huffman编码是一种压缩算法，可以将字符集中的字符进行编码，用较少的比特数来表示字符，从而达到压缩数据的目的。

以下是用C++实现Huffman编码的简单示例代码：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

// Huffman编码树节点
struct HuffmanNode {
    char ch;              // 字符
    int weight;           // 权重
    HuffmanNode *left;    // 左子树
    HuffmanNode *right;   // 右子树

    // 构造函数
    HuffmanNode(char c, int w) : ch(c), weight(w), left(nullptr), right(nullptr) {}
};

// 比较函数，用于构建priority_queue
struct Compare {
    bool operator()(HuffmanNode *a, HuffmanNode *b) {
        return a->weight > b->weight;
    }
};

// 构建Huffman编码树
HuffmanNode *buildHuffmanTree(unordered_map<char, int> freq) {
    priority_queue<HuffmanNode *, vector<HuffmanNode *>, Compare> pq;

    // 将字符和出现频率转换为Huffman节点
    for (auto it : freq) {
        pq.push(new HuffmanNode(it.first, it.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();
}

// 递归遍历Huffman编码树，生成Huffman编码
void generateHuffmanCode(HuffmanNode *root, string code, unordered_map<char, string> &table) {
    if (!root) {
        return;
    }

    // 如果当前节点是叶子节点，将编码加入到哈希表
    if (!root->left && !root->right) {
        table[root->ch] = code;
    }

    generateHuffmanCode(root->left, code + "0", table);
    generateHuffmanCode(root->right, code + "1", table);
}

// 将字符串编码为Huffman编码
string encode(string str, unordered_map<char, string> table) {
    string result = "";
    for (char c : str) {
        result += table[c];
    }
    return result;
}

// 将Huffman编码解码为原字符串
string decode(string code, HuffmanNode *root) {
    string result = "";
    HuffmanNode *cur = root;
    for (char c : code) {
        if (c == '0') {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
        if (!cur->left && !cur->right) {
            result += cur->ch;
            cur = root;
        }
    }
    return result;
}

int main() {
    string str = "Hello, Huffman!";
    unordered_map<char, int> freq;
    for (char c : str) {
        freq[c]++;
    }

    HuffmanNode *root = buildHuffmanTree(freq);

    unordered_map<char, string> table;
    generateHuffmanCode(root, "", table);

    cout << "Huffman table:" << endl;
    for (auto it : table) {
        cout << it.first << ": " << it.second << endl;
    }

    string code = encode(str, table);
    cout << "Encoded: " << code << endl;

    string decoded = decode(code, root);
    cout << "Decoded: " << decoded << endl;

    return 0;
}

这个代码实现了Huffman编码和解码的功能，可以自行输入字符串进行测试。