c++哈夫曼树对文件进行压缩、解压的代码

以下是C++中基于哈夫曼树进行文件压缩、解压的示例代码：

#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <bitset>

using namespace std;

struct HuffmanNode {
    char c;
    int freq;
    HuffmanNode *left, *right;
    HuffmanNode(char c, int freq) : c(c), freq(freq), left(nullptr), right(nullptr) {}
    ~HuffmanNode() {
        delete left;
        delete right;
    }
};

struct compare {
    bool operator()(const HuffmanNode* a, const HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

class HuffmanTree {
private:
    HuffmanNode* root;
    unordered_map<char, int> freq_map;

    void build_freq_map(const string& str) {
        for (char c : str) {
            freq_map[c]++;
        }
    }

    void build_tree() {
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, compare> pq;
        for (auto& p : freq_map) {
            pq.push(new HuffmanNode(p.first, p.second));
        }
        while (pq.size() > 1) {
            auto left = pq.top(); pq.pop();
            auto right = pq.top(); pq.pop();
            auto parent = new HuffmanNode('\0', left->freq + right->freq);
            parent->left = left;
            parent->right = right;
            pq.push(parent);
        }
        root = pq.top();
    }

    void build_encoding_table(unordered_map<char, string>& encoding_table, HuffmanNode* node, string code) {
        if (!node) return;
        if (node->c != '\0') {
            encoding_table[node->c] = code;
        }
        build_encoding_table(encoding_table, node->left, code + "0");
        build_encoding_table(encoding_table, node->right, code + "1");
    }

public:
    HuffmanTree(const string& str) : root(nullptr) {
        build_freq_map(str);
        build_tree();
    }

    ~HuffmanTree() {
        delete root;
    }

    unordered_map<char, string> build_encoding_table() {
        unordered_map<char, string> encoding_table;
        build_encoding_table(encoding_table, root, "");
        return encoding_table;
    }

    void compress(const string& input_file, const string& output_file) {
        ifstream ifs(input_file, ios::binary);
        if (!ifs) {
            cerr << "Failed to open input file!" << endl;
            return;
        }
        ofstream ofs(output_file, ios::binary);
        if (!ofs) {
            cerr << "Failed to open output file!" << endl;
            return;
        }

        // 构建编码表
        auto encoding_table = build_encoding_table();

        // 计算压缩后的文件头
        int header_size = sizeof(int) + freq_map.size() * (sizeof(char) + sizeof(int));
        char* header = new char[header_size];
        int pos = 0;
        memcpy(&header[pos], &freq_map.size(), sizeof(int)); pos += sizeof(int);
        for (auto& p : freq_map) {
            memcpy(&header[pos], &p.first, sizeof(char)); pos += sizeof(char);
            memcpy(&header[pos], &p.second, sizeof(int)); pos += sizeof(int);
        }

        // 写入文件头
        ofs.write(header, header_size);

        // 压缩文件内容
        char c;
        string code;
        while (ifs.get(c)) {
            code += encoding_table[c];
            while (code.size() >= 8) {
                char byte = bitset<8>(code.substr(0, 8)).to_ulong();
                ofs.write(&byte, sizeof(char));
                code = code.substr(8);
            }
        }
        if (!code.empty()) {
            char byte = bitset<8>(code + string(8 - code.size(), '0')).to_ulong();
            ofs.write(&byte, sizeof(char));
        }

        ifs.close();
        ofs.close();
    }

    void decompress(const string& input_file, const string& output_file) {
        ifstream ifs(input_file, ios::binary);
        if (!ifs) {
            cerr << "Failed to open input file!" << endl;
            return;
        }
        ofstream ofs(output_file, ios::binary);
        if (!ofs) {
            cerr << "Failed to open output file!" << endl;
            return;
        }

        // 读取文件头
        int header_size;
        ifs.read(reinterpret_cast<char*>(&header_size), sizeof(int));
        char* header = new char[header_size];
        ifs.read(header, header_size);
        int pos = 0;
        int freq_map_size;
        memcpy(&freq_map_size, &header[pos], sizeof(int)); pos += sizeof(int);
        unordered_map<char, int> freq_map;
        for (int i = 0; i < freq_map_size; ++i) {
            char c;
            int freq;
            memcpy(&c, &header[pos], sizeof(char)); pos += sizeof(char);
            memcpy(&freq, &header[pos], sizeof(int)); pos += sizeof(int);
            freq_map[c] = freq;
        }
        delete[] header;

        // 构建哈夫曼树
        priority_queue<HuffmanNode*, vector<HuffmanNode*>, compare> pq;
        for (auto& p : freq_map) {
            pq.push(new HuffmanNode(p.first, p.second));
        }
        while (pq.size() > 1) {
            auto left = pq.top(); pq.pop();
            auto right = pq.top(); pq.pop();
            auto parent = new HuffmanNode('\0', left->freq + right->freq);
            parent->left = left;
            parent->right = right;
            pq.push(parent);
        }
        root = pq.top();

        // 解压文件内容
        HuffmanNode* node = root;
        int bit_count = 0;
        char byte;
        while (ifs.get(byte)) {
            bitset<8> bits(byte);
            for (int i = 7; i >= 0; --i) {
                if (bits[i] == 0) {
                    node = node->left;
                } else {
                    node = node->right;
                }

                if (node->c != '\0') {
                    ofs.write(&node->c, sizeof(char));
                    node = root;
                }

                if (++bit_count == 8 * header_size + node->freq) break;
            }
            if (bit_count == 8 * header_size + node->freq) break;
        }

        ifs.close();
        ofs.close();
    }
};

int main() {
    string input_file = "input.txt";
    string compressed_file = "compressed.bin";
    string decompressed_file = "decompressed.txt";

    // 压缩文件
    HuffmanTree huffman_tree("abracadabra");
    huffman_tree.compress(input_file, compressed_file);

    // 解压文件
    huffman_tree.decompress(compressed_file, decompressed_file);

    return 0;
}

在上面的示例中，我们首先定义了一个`HuffmanNode`结构体，用于表示哈夫曼树的节点。每个节点包含一个字符`c`和该字符在原始文本中出现的频率`freq`，以及指向左右子节点的指针`left`和`right`。

接着，我们定义了一个`HuffmanTree`类，用于构建哈夫曼树，并提供压缩和解压文件的功能。在构建哈夫曼树时，我们使用了一个优先队列`pq`，将每个字符的频率作为优先级进行排序。每次从队列中取出两个频率最小的节点，合并成一个新的节点，然后将新节点加入队列。当队列中只剩下一个节点时，即为哈夫曼树的根节点。

在压缩文件时，我们首先构建了编码表`encoding_table`，将每个字符映射到对应的二进制编码。然后，我们计算压缩后的文件头，并将其写入输出文件中。文件头包含了字符频率的数量以及每个字符和频率的信息。接着，我们读取输入文件中的每个字符，并将其转换为对应的二进制编码，然后将编码写入输出文件中。

在解压文件时，我们首先读取文件头，并使用其中的字符频率信息构建哈夫曼树。然后，我们读取压缩后的文件内容，并按位进行解码。每次读取一个二进制位时，我们通过遍历哈夫曼树找到对应的字符，并将其写入输出文件中。当我们写入的字符数量等于原始文本中的字符数量时，解压过程结束。