数据结构 赫夫曼编码c++

赫夫曼编码是一种可变长度编码，常用于数据压缩中。以下是C++实现赫夫曼编码的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <fstream>
using namespace std;

// 赫夫曼树的节点
struct Node {
    char ch;
    int freq;
    Node *left, *right;
    Node(char _ch, int _freq, Node *_left = nullptr, Node *_right = nullptr) : ch(_ch), freq(_freq), left(_left), right(_right) {}
};

// 定义比较器
struct cmp {
    bool operator() (const Node *a, const Node *b) const {
        return a->freq > b->freq;
    }
};

// 构建赫夫曼树
Node* buildHuffmanTree(const string& str) {
    // 统计字符出现频率
    map<char, int> freq;
    for (char ch : str) {
        freq[ch]++;
    }

    // 将每个字符作为一个节点插入最小堆中
    priority_queue<Node*, vector<Node*>, cmp> heap;
    for (auto& p : freq) {
        heap.push(new Node(p.first, p.second));
    }

    // 依次取出堆顶的两个节点，合并成一个新节点
    while (heap.size() > 1) {
        Node *left = heap.top();
        heap.pop();
        Node *right = heap.top();
        heap.pop();
        Node *parent = new Node('\0', left->freq + right->freq, left, right);
        heap.push(parent);
    }

    // 返回赫夫曼树的根节点
    return heap.top();
}

// 生成赫夫曼编码
void generateHuffmanCode(Node *root, map<char, string>& code, string path = "") {
    if (!root) {
        return;
    }
    if (!root->left && !root->right) {
        code[root->ch] = path;
    }
    generateHuffmanCode(root->left, code, path + "0");
    generateHuffmanCode(root->right, code, path + "1");
}

// 将赫夫曼编码写入文件
void writeHuffmanCodeToFile(const string& filename, const string& str, const map<char, string>& code) {
    ofstream ofs(filename, ios::out);
    for (char ch : str) {
        ofs << code.at(ch);
    }
    ofs.close();
}

// 将二进制文件解码成文本文件
void decodeHuffmanCode(const string& inputFilename, const string& outputFilename, Node *root) {
    ifstream ifs(inputFilename, ios::in | ios::binary);
    ofstream ofs(outputFilename, ios::out);
    char byte;
    Node *p = root;
    while (ifs.get(byte)) {
        for (int i = 0; i < 8; i++) {
            if (byte & (1 << (7 - i))) {
                p = p->right;
            } else {
                p = p->left;
            }
            if (!p->left && !p->right) {
                ofs << p->ch;
                p = root;
            }
        }
    }
    ifs.close();
    ofs.close();
}

int main() {
    string str = "hello, world!";

    // 构建赫夫曼树
    Node *root = buildHuffmanTree(str);

    // 生成赫夫曼编码
    map<char, string> code;
    generateHuffmanCode(root, code);

    // 将赫夫曼编码写入文件
    writeHuffmanCodeToFile("output.bin", str, code);

    // 将二进制文件解码成文本文件
    decodeHuffmanCode("output.bin", "output.txt", root);

    return 0;
}

该程序将字符串"hello, world!"进行赫夫曼编码，并将编码后的二进制数据写入到文件output.bin中。然后，程序将读取output.bin文件并解码成文本文件output.txt。在解码的过程中，程序通过遍历二进制数据的每一位，依次移动赫夫曼树的节点，直到找到一个叶子节点，即可将该节点对应的字符输出到文本文件中。