用qt写利用哈夫曼压缩与解压缩文件的C++代码

以下是使用 Qt 编写的哈夫曼压缩与解压缩文件的 C++ 代码示例：

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

using namespace std;

// 定义哈夫曼树节点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    Node(int f) : freq(f), left(nullptr), right(nullptr) {}
    ~Node() {
        delete left;
        delete right;
    }
};

// 定义哈夫曼树节点比较函数
struct NodeCompare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
Node* buildHuffmanTree(const unordered_map<char, int>& freqMap) {
    priority_queue<Node*, vector<Node*>, NodeCompare> pq;
    for (auto& pair : freqMap) {
        pq.push(new Node(pair.first, pair.second));
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node(left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 构建哈夫曼编码表
void buildHuffmanCodeTable(Node* root, string code, unordered_map<char, string>& codeTable) {
    if (!root) {
        return;
    }
    if (root->ch != '\0') {
        codeTable[root->ch] = code;
    }
    buildHuffmanCodeTable(root->left, code + "0", codeTable);
    buildHuffmanCodeTable(root->right, code + "1", codeTable);
}

// 压缩文件
void compressFile(const string& inputFile, const string& outputFile) {
    // 统计每个字符出现的次数
    unordered_map<char, int> freqMap;
    ifstream in(inputFile, ios_base::binary);
    char ch;
    while (in.get(ch)) {
        freqMap[ch]++;
    }
    in.close();

    // 构建哈夫曼树和编码表
    Node* root = buildHuffmanTree(freqMap);
    unordered_map<char, string> codeTable;
    buildHuffmanCodeTable(root, "", codeTable);

    // 将编码表写入压缩文件
    QFile out(outputFile.c_str());
    if (out.open(QIODevice::WriteOnly | QIODevice::Truncate)) {
        for (auto& pair : codeTable) {
            out.write(pair.first);
            out.write(pair.second.c_str(), pair.second.size());
            out.write("\n");
        }
    }
    out.close();

    // 写入压缩后的数据
    bitset<8> bits;
    int bitCount = 0;
    in.open(inputFile, ios_base::binary);
    out.open(outputFile.c_str(), QIODevice::Append);
    while (in.get(ch)) {
        string code = codeTable[ch];
        for (char c : code) {
            bits[bitCount++] = (c == '1');
            if (bitCount == 8) {
                char byte = static_cast<char>(bits.to_ulong());
                out.write(&byte, 1);
                bitCount = 0;
            }
        }
    }
    if (bitCount > 0) {
        char byte = static_cast<char>(bits.to_ulong());
        out.write(&byte, 1);
    }
    in.close();
    out.close();

    // 释放哈夫曼树的内存
    delete root;
}

// 解压缩文件
void decompressFile(const string& inputFile, const string& outputFile) {
    // 读取编码表
    unordered_map<string, char> codeTable;
    ifstream in(inputFile, ios_base::binary);
    char ch;
    string code;
    while (in.get(ch)) {
        if (ch == '\n') {
            codeTable[code] = ch;
            code.clear();
        }
        else {
            code += ch;
        }
    }
    in.close();

    // 解压缩文件
    bitset<8> bits;
    int bitCount = 0;
    in.open(inputFile, ios_base::binary);
    in.seekg(in.tellg() - static_cast<streamoff>(codeTable.size() * 2 + 1));
    QFile out(outputFile.c_str());
    if (out.open(QIODevice::WriteOnly | QIODevice::Truncate)) {
        Node* root = nullptr;
        while (in.read(&ch, 1)) {
            bits = bitset<8>(ch);
            for (int i = 0; i < 8 && (root || i < bitCount); i++) {
                bool bit = bits[i];
                if (!root) {
                    root = new Node(0);
                }
                root = (bit ? root->right : root->left);
                if (root->ch != '\0') {
                    out.write(&root->ch, 1);
                    root = nullptr;
                }
            }
            bitCount = (bitCount + 8) % 8;
        }
        delete root;
    }
    in.close();
    out.close();
}

int main() {
    string inputFile = "input.txt";
    string compressedFile = "compressed.bin";
    string decompressedFile = "output.txt";
    compressFile(inputFile, compressedFile);
    decompressFile(compressedFile, decompressedFile);
    return 0;
}

在这个示例中，我们首先定义了一个 `Node` 结构体来表示哈夫曼树的节点，其中 `ch` 表示节点代表的字符，`freq` 表示该字符出现的次数，`left` 和 `right` 分别表示左右子节点。然后，我们定义了一个 `NodeCompare` 结构体来比较两个节点的大小，以便在构建哈夫曼树时使用优先队列来实现最小堆。接着，我们实现了 `buildHuffmanTree` 函数来构建哈夫曼树，使用了一个哈希表来统计每个字符出现的次数，并且使用优先队列来不断合并出现次数最小的两个节点，直到只剩下一个根节点。然后，我们实现了 `buildHuffmanCodeTable` 函数来构建哈夫曼编码表，使用了递归的方式来遍历哈夫曼树，并且将每个字符对应的编码保存在哈希表中。接着，我们实现了 `compressFile` 函数来压缩文件，首先调用 `buildHuffmanTree` 和 `buildHuffmanCodeTable` 函数来构建哈夫曼树和编码表，然后将编码表写入压缩文件，并且使用位运算和 `bitset` 来将每个字符压缩成其对应的编码。最后，我们实现了 `decompressFile` 函数来解压缩文件，首先读取编码表，然后使用位运算和 `bitset` 来将每个编码解压缩成原始字符，并且将解压缩后的字符写入输出文件中。