采用哈夫曼编码思想实现文件的压缩和解压功能的c++代码

以下是采用哈夫曼编码思想实现文件的压缩和解压功能的C++代码：

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

using namespace std;

// 定义哈夫曼树的节点结构体
struct HuffmanNode {
    char ch;  // 存储字符
    int freq; // 存储字符出现的频率
    HuffmanNode *left, *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; // 频率越小的节点优先级越高
    }
};

// 根据输入的文件，统计字符出现的频率
map<char, int> getCharFrequency(const string& filename) {
    map<char, int> freq;
    ifstream fin(filename, ios::in | ios::binary);
    char ch;
    while (fin.get(ch)) {
        freq[ch]++;
    }
    fin.close();
    return freq;
}

// 根据字符频率构建哈夫曼树
HuffmanNode* buildHuffmanTree(const map<char, int>& freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto& p : freq) {
        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 generateHuffmanCode(HuffmanNode* root, string code, map<char, string>& huffmanCode) {
    if (!root) return;
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCode[root->ch] = code;
    }
    generateHuffmanCode(root->left, code + "0", huffmanCode);
    generateHuffmanCode(root->right, code + "1", huffmanCode);
}

// 将哈夫曼编码写入压缩文件的头部
void writeHuffmanCode(ofstream& fout, const map<char, string>& huffmanCode) {
    for (auto& p : huffmanCode) {
        fout << p.first << " " << p.second << endl;
    }
}

// 压缩文件
void compressFile(const string& inputFile, const string& outputFile) {
    // 统计字符频率
    map<char, int> freq = getCharFrequency(inputFile);
    // 构建哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freq);
    // 生成哈夫曼编码
    map<char, string> huffmanCode;
    generateHuffmanCode(root, "", huffmanCode);
    // 将哈夫曼编码写入压缩文件的头部
    ofstream fout(outputFile, ios::out | ios::binary);
    writeHuffmanCode(fout, huffmanCode);
    fout << endl;
    // 逐个读取输入文件的字符，将其转换成哈夫曼编码，写入压缩文件中
    ifstream fin(inputFile, ios::in | ios::binary);
    char ch;
    string code;
    while (fin.get(ch)) {
        code += huffmanCode[ch];
        while (code.length() >= 8) {
            bitset<8> b(code.substr(0, 8));
            fout.put((char) b.to_ulong());
            code.erase(0, 8);
        }
    }
    if (!code.empty()) {
        bitset<8> b(code);
        fout.put((char) b.to_ulong());
    }
    fin.close();
    fout.close();
}

// 读取压缩文件的头部，获取哈夫曼编码
void readHuffmanCode(ifstream& fin, map<char, string>& huffmanCode) {
    string line;
    while (getline(fin, line)) {
        if (line.empty()) break;
        char ch;
        string code;
        sscanf(line.c_str(), "%c %s", &ch, &code);
        huffmanCode[ch] = code;
    }
}

// 解压文件
void decompressFile(const string& inputFile, const string& outputFile) {
    // 读取压缩文件的头部，获取哈夫曼编码
    map<char, string> huffmanCode;
    ifstream fin(inputFile, ios::in | ios::binary);
    readHuffmanCode(fin, huffmanCode);
    // 逐个读取压缩文件中的编码，将其转换成字符，写入输出文件中
    ofstream fout(outputFile, ios::out | ios::binary);
    char ch;
    string code;
    HuffmanNode* root = buildHuffmanTree(getCharFrequency(inputFile));
    HuffmanNode* node = root;
    while (fin.get(ch)) {
        bitset<8> b(ch);
        code += b.to_string();
        while (true) {
            if (node->left == nullptr && node->right == nullptr) {
                fout.put(node->ch);
                node = root;
            } else if (code[0] == '0') {
                node = node->left;
                code.erase(0, 1);
            } else {
                node = node->right;
                code.erase(0, 1);
            }
            if (code.empty()) break;
        }
    }
    fin.close();
    fout.close();
}

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

说明：

- `getCharFrequency` 函数用于统计输入文件中每个字符出现的频率。
- `buildHuffmanTree` 函数用于根据字符频率构建哈夫曼树。
- `generateHuffmanCode` 函数用于递归遍历哈夫曼树，生成哈夫曼编码。
- `writeHuffmanCode` 函数用于将哈夫曼编码写入压缩文件的头部。
- `compressFile` 函数用于压缩输入文件。
- `readHuffmanCode` 函数用于读取压缩文件的头部，获取哈夫曼编码。
- `decompressFile` 函数用于解压压缩文件。
- 主函数中的示例代码演示了如何使用上述函数进行文件的压缩和解压。