基于哈夫曼树的数据压缩算法代码

以下是基于哈夫曼树的数据压缩算法的C++代码：

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

using namespace std;

// 定义哈夫曼树节点
struct HuffmanNode {
    char ch;                // 字符
    int freq;               // 频率
    HuffmanNode* left;      // 左子树
    HuffmanNode* right;     // 右子树

    HuffmanNode(char ch, int freq) {
        this->ch = ch;
        this->freq = freq;
        left = nullptr;
        right = nullptr;
    }

    // 定义比较运算符，用于优先队列排序
    bool operator<(const HuffmanNode& other) const {
        return freq > other.freq;
    }
};

// 建立哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
    // 构建优先队列，按照频率从小到大排序
    priority_queue<HuffmanNode> minHeap;
    for (auto& pair : freqMap) {
        minHeap.push(HuffmanNode(pair.first, pair.second));
    }

    // 循环取出两个频率最小的节点，合并为一个新节点，并将新节点加入队列
    while (minHeap.size() > 1) {
        HuffmanNode* left = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
        minHeap.pop();
        HuffmanNode* right = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
        minHeap.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        minHeap.push(*parent);
    }

    // 队列中剩余的节点即为根节点
    HuffmanNode* root = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
    root->left = minHeap.top().left;
    root->right = minHeap.top().right;

    return root;
}

// 生成哈夫曼编码表
void generateHuffmanCodeTable(HuffmanNode* root, string code, unordered_map<char, string>& codeTable) {
    if (root == nullptr) {
        return;
    }

    if (root->left == nullptr && root->right == nullptr) {
        codeTable[root->ch] = code;
        return;
    }

    generateHuffmanCodeTable(root->left, code + "0", codeTable);
    generateHuffmanCodeTable(root->right, code + "1", codeTable);
}

// 压缩数据
string compressData(string data) {
    // 统计字符频率
    unordered_map<char, int> freqMap;
    for (char ch : data) {
        freqMap[ch]++;
    }

    // 建立哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);

    // 生成哈夫曼编码表
    unordered_map<char, string> codeTable;
    generateHuffmanCodeTable(root, "", codeTable);

    // 压缩数据
    string compressedData;
    for (char ch : data) {
        compressedData += codeTable[ch];
    }

    return compressedData;
}

// 解压数据
string decompressData(string compressedData, HuffmanNode* root) {
    string decompressedData;
    HuffmanNode* node = root;

    for (char bit : compressedData) {
        if (bit == '0') {
            node = node->left;
        } else {
            node = node->right;
        }

        if (node->left == nullptr && node->right == nullptr) {
            decompressedData += node->ch;
            node = root;
        }
    }

    return decompressedData;
}

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

    // 压缩数据
    string compressedData = compressData(data);
    cout << "Compressed data: " << compressedData << endl;

    // 解压数据
    string decompressedData = decompressData(compressedData, buildHuffmanTree(unordered_map<char, int>()));
    cout << "Decompressed data: " << decompressedData << endl;

    return 0;
}

以上代码中，首先统计字符频率，然后建立哈夫曼树，生成哈夫曼编码表，最后根据编码表压缩数据。在解压数据时，根据哈夫曼树的结构和编码表进行反向解码。