C++ 哈夫曼树对文件压缩、加密实现代码

以下是C++实现的哈夫曼树对文件进行压缩和加密的代码：

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

using namespace std;

// 定义哈夫曼树结点
struct TreeNode {
    char c;             // 字符
    int freq;           // 频率
    TreeNode* left;     // 左儿子
    TreeNode* right;    // 右儿子
    TreeNode(char c, int freq, TreeNode* left, TreeNode* right) :
        c(c), freq(freq), left(left), right(right) {}
};

// 定义优先队列比较函数
struct cmp {
    bool operator()(TreeNode* a, TreeNode* b) {
        return a->freq > b->freq;
    }
};

// 生成哈夫曼树
TreeNode* generateHuffmanTree(const string& s) {
    // 统计字符频率
    int freq[256] = { 0 };
    for (char c : s) {
        freq[c]++;
    }

    // 将结点放入优先队列
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            pq.push(new TreeNode(i, freq[i], nullptr, nullptr));
        }
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        TreeNode* left = pq.top();
        pq.pop();
        TreeNode* right = pq.top();
        pq.pop();
        TreeNode* parent = new TreeNode('\0', left->freq + right->freq, left, right);
        pq.push(parent);
    }

    return pq.top();
}

// 生成字符编码表
void generateEncodingTable(TreeNode* root, vector<string>& encodingTable, string code) {
    if (root == nullptr) {
        return;
    }

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

    generateEncodingTable(root->left, encodingTable, code + "0");
    generateEncodingTable(root->right, encodingTable, code + "1");
}

// 压缩文件
void compressFile(const string& inputFile, const string& outputFile, vector<string>& encodingTable) {
    // 读入文件
    ifstream ifs(inputFile, ios::binary);
    string s((istreambuf_iterator<char>(ifs)), istreambuf_iterator<char>());
    ifs.close();

    // 将字符编码转为二进制字符串
    string binaryStr = "";
    for (char c : s) {
        binaryStr += encodingTable[c];
    }

    // 补齐 8 的倍数
    int padding = 8 - binaryStr.size() % 8;
    for (int i = 0; i < padding; i++) {
        binaryStr += "0";
    }

    // 将二进制字符串转为字节流
    vector<char> bytes;
    for (int i = 0; i < binaryStr.size(); i += 8) {
        bytes.push_back(bitset<8>(binaryStr.substr(i, 8)).to_ulong());
    }

    // 写入文件
    ofstream ofs(outputFile, ios::binary);
    ofs.write(&padding, sizeof(padding));
    int size = encodingTable.size();
    ofs.write((char*)&size, sizeof(size));
    for (int i = 0; i < encodingTable.size(); i++) {
        ofs.write(&i, sizeof(char));
        int len = encodingTable[i].size();
        ofs.write((char*)&len, sizeof(len));
        ofs.write(encodingTable[i].c_str(), len);
    }
    ofs.write(bytes.data(), bytes.size());
    ofs.close();
}

// 解压文件
void decompressFile(const string& inputFile, const string& outputFile) {
    // 读入文件
    ifstream ifs(inputFile, ios::binary);
    int padding;
    ifs.read((char*)&padding, sizeof(padding));
    int size;
    ifs.read((char*)&size, sizeof(size));
    vector<string> encodingTable(256);
    for (int i = 0; i < size; i++) {
        char c;
        ifs.read(&c, sizeof(char));
        int len;
        ifs.read((char*)&len, sizeof(len));
        char* buf = new char[len + 1];
        ifs.read(buf, len);
        buf[len] = '\0';
        encodingTable[c] = buf;
        delete[] buf;
    }
    string s((istreambuf_iterator<char>(ifs)), istreambuf_iterator<char>());
    ifs.close();

    // 将字节流转为二进制字符串
    string binaryStr = "";
    for (char c : s) {
        binaryStr += bitset<8>(c).to_string();
    }
    binaryStr = binaryStr.substr(0, binaryStr.size() - padding);

    // 生成反向字符编码表
    vector<char> decodingTable(256, -1);
    for (int i = 0; i < encodingTable.size(); i++) {
        if (!encodingTable[i].empty()) {
            decodingTable[bitset<8>(encodingTable[i]).to_ulong()] = i;
        }
    }

    // 解码
    string decodedStr = "";
    int i = 0;
    while (i < binaryStr.size()) {
        int j = i;
        while (j < binaryStr.size() && decodingTable[bitset<8>(binaryStr.substr(i, j - i + 1)).to_ulong()] == -1) {
            j++;
        }
        decodedStr += decodingTable[bitset<8>(binaryStr.substr(i, j - i + 1)).to_ulong()];
        i = j + 1;
    }

    // 写入文件
    ofstream ofs(outputFile, ios::binary);
    ofs.write(decodedStr.c_str(), decodedStr.size());
    ofs.close();
}

int main() {
    string inputFile = "input.txt";     // 输入文件名
    string compressedFile = "compressed.bin";   // 压缩后的文件名
    string decompressedFile = "decompressed.txt";  // 解压后的文件名

    // 读入文件
    ifstream ifs(inputFile);
    string s((istreambuf_iterator<char>(ifs)), istreambuf_iterator<char>());
    ifs.close();

    // 生成哈夫曼树和编码表
    TreeNode* root = generateHuffmanTree(s);
    vector<string> encodingTable(256);
    generateEncodingTable(root, encodingTable, "");

    // 压缩文件
    compressFile(inputFile, compressedFile, encodingTable);

    // 解压文件
    decompressFile(compressedFile, decompressedFile);

    return 0;
}

以上代码的流程如下：

1. 读入输入文件并统计字符频率。
2. 生成哈夫曼树。
3. 生成字符编码表。
4. 将输入文件的字符编码转为二进制字符串，补齐 8 的倍数，并将二进制字符串转为字节流。
5. 将字符编码表、补齐的位数和字节流写入输出文件。
6. 读入压缩文件并解析字符编码表、补齐的位数和字节流。
7. 将字节流转为二进制字符串，解码并写入输出文件。

注意：以上代码仅供参考，实际使用时还需要考虑错误处理、内存泄漏等问题。