c++实现哈夫曼编码压缩

哈夫曼编码是一种常用的数据压缩算法，可以通过将频率较高的字符用较短的二进制位来表示，从而有效地减小数据存储的大小。下面是一个简单的C++实现，实现对字符串的哈夫曼编码压缩和解压缩：

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

using namespace std;

// 哈夫曼树节点结构体
struct HuffmanNode {
    char ch; // 节点对应的字符
    int freq; // 字符出现的频率
    HuffmanNode* left; // 左子节点
    HuffmanNode* right; // 右子节点
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 定义哈夫曼树节点比较函数，用于优先队列排序
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(string s) {
    unordered_map<char, int> freqMap;
    for (char c : s) {
        freqMap[c]++;
    }

    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto& p : freqMap) {
        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->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

// 将哈夫曼树转换为哈夫曼编码表
void buildHuffmanCodeTable(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (!root) return;
    if (root->ch != '$') {
        codeMap[root->ch] = code;
    }
    buildHuffmanCodeTable(root->left, code + "0", codeMap);
    buildHuffmanCodeTable(root->right, code + "1", codeMap);
}

// 压缩字符串
string compress(string s) {
    HuffmanNode* root = buildHuffmanTree(s);

    unordered_map<char, string> codeMap;
    buildHuffmanCodeTable(root, "", codeMap);

    string compressed = "";
    for (char c : s) {
        compressed += codeMap[c];
    }

    return compressed;
}

// 解压缩字符串
string decompress(string s, HuffmanNode* root) {
    string decompressed = "";
    HuffmanNode* node = root;
    for (char c : s) {
        if (c == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->ch != '$') {
            decompressed += node->ch;
            node = root;
        }
    }
    return decompressed;
}

int main() {
    string s = "hello world";
    cout << "Original string: " << s << endl;

    string compressed = compress(s);
    cout << "Compressed string: " << compressed << endl;

    HuffmanNode* root = buildHuffmanTree(s);
    string decompressed = decompress(compressed, root);
    cout << "Decompressed string: " << decompressed << endl;

    return 0;
}

在上面的代码中，我们首先定义了一个 `HuffmanNode` 结构体，用于表示哈夫曼树的节点。然后，我们通过统计字符串中每个字符出现的频率来构建哈夫曼树，并通过哈夫曼树构建哈夫曼编码表。接着，我们可以将原始字符串使用哈夫曼编码进行压缩，并使用哈夫曼树进行解压缩。最后，我们将压缩后的字符串和解压缩后的字符串打印出来，以验证算法的正确性。