C++实现哈夫曼编码和解码

哈夫曼编码（Huffman Coding）是一种基于字符出现频率的无损数据压缩算法。在哈夫曼编码中，出现频率高的字符被赋予较短的编码，出现频率低的字符被赋予较长的编码，从而实现数据的压缩。下面是使用C++实现哈夫曼编码和解码的示例代码。

**哈夫曼树的实现**

首先需要实现哈夫曼树的数据结构和相关的操作。

#include <iostream>
#include <queue>
#include <vector>
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 CompareNode {
    bool operator()(HuffmanNode *a, HuffmanNode *b) {
        return a->freq > b->freq;
    }
};

// 创建哈夫曼树
HuffmanNode *createHuffmanTree(string s) {
    int freq[256] = {0}; // 统计每个字符出现的次数
    for (char c : s) {
        freq[c]++;
    }
    priority_queue<HuffmanNode *, vector<HuffmanNode *>, CompareNode> q;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            q.push(new HuffmanNode(i, freq[i]));
        }
    }
    while (q.size() > 1) { // 构造哈夫曼树
        HuffmanNode *left = q.top(); q.pop();
        HuffmanNode *right = q.top(); q.pop();
        HuffmanNode *parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        q.push(parent);
    }
    return q.top();
}

// 销毁哈夫曼树
void destroyHuffmanTree(HuffmanNode *root) {
    if (root) {
        destroyHuffmanTree(root->left);
        destroyHuffmanTree(root->right);
        delete root;
    }
}

上面的代码中，用一个整型数组 `freq` 来统计每个字符出现的次数，然后用一个优先队列 `q` 存储所有出现过的字符。在构造哈夫曼树的过程中，每次从 `q` 中取出出现频率最小的两个字符节点（即 `freq` 数组中出现次数最少的两个字符），将它们作为左右子节点组成一个新的父节点，并将这个新的父节点插入到 `q` 中。最终，`q` 中只剩下一个节点，它就是哈夫曼树的根节点。

**哈夫曼编码的实现**

接着，我们需要实现哈夫曼编码的过程，将输入的字符串编码成压缩后的二进制字符串。

#include <unordered_map>
#include <bitset>

// 生成哈夫曼编码表
void generateHuffmanCodeTable(HuffmanNode *root, string code, unordered_map<char, string> &table) {
    if (root->left == nullptr && root->right == nullptr) {
        table[root->ch] = code;
        return;
    }
    generateHuffmanCodeTable(root->left, code + "0", table);
    generateHuffmanCodeTable(root->right, code + "1", table);
}

// 对字符串进行哈夫曼编码
string encode(string s) {
    HuffmanNode *root = createHuffmanTree(s); // 创建哈夫曼树
    unordered_map<char, string> table; // 哈夫曼编码表
    generateHuffmanCodeTable(root, "", table); // 生成编码表
    string encoded = "";
    for (char c : s) {
        encoded += table[c]; // 将每个字符转换为对应的哈夫曼编码
    }
    destroyHuffmanTree(root); // 销毁哈夫曼树
    return encoded;
}

上面的代码中，`generateHuffmanCodeTable()` 函数用来生成哈夫曼编码表，它递归遍历哈夫曼树，将每个字符的编码存储到 `table` 中。`encode()` 函数用来对输入的字符串进行编码，它先创建哈夫曼树，然后调用 `generateHuffmanCodeTable()` 函数生成编码表，最后将每个字符转换为对应的哈夫曼编码。

**哈夫曼解码的实现**

最后，我们需要实现哈夫曼解码的过程，将压缩后的二进制字符串解码成原始的字符串。

// 对哈夫曼编码进行解码
string decode(string encoded, HuffmanNode *root) {
    string decoded = "";
    HuffmanNode *node = root;
    for (char bit : encoded) {
        if (bit == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == nullptr && node->right == nullptr) {
            decoded += node->ch;
            node = root;
        }
    }
    return decoded;
}

上面的代码中，`decode()` 函数用来对压缩后的二进制字符串进行解码，它逐位遍历输入的字符串，根据每个字符是 '0' 还是 '1'，向左或向右遍历哈夫曼树，直到找到叶子节点。找到叶子节点后，将该节点对应的字符加入到解码后的字符串中，并将当前节点重新指向哈夫曼树的根节点。

**完整代码**

下面是完整的哈夫曼编码和解码的示例代码。

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_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 CompareNode {
    bool operator()(HuffmanNode *a, HuffmanNode *b) {
        return a->freq > b->freq;
    }
};

// 创建哈夫曼树
HuffmanNode *createHuffmanTree(string s) {
    int freq[256] = {0}; // 统计每个字符出现的次数
    for (char c : s) {
        freq[c]++;
    }
    priority_queue<HuffmanNode *, vector<HuffmanNode *>, CompareNode> q;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            q.push(new HuffmanNode(i, freq[i]));
        }
    }
    while (q.size() > 1) { // 构造哈夫曼树
        HuffmanNode *left = q.top(); q.pop();
        HuffmanNode *right = q.top(); q.pop();
        HuffmanNode *parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        q.push(parent);
    }
    return q.top();
}

// 销毁哈夫曼树
void destroyHuffmanTree(HuffmanNode *root) {
    if (root) {
        destroyHuffmanTree(root->left);
        destroyHuffmanTree(root->right);
        delete root;
    }
}

// 生成哈夫曼编码表
void generateHuffmanCodeTable(HuffmanNode *root, string code, unordered_map<char, string> &table) {
    if (root->left == nullptr && root->right == nullptr) {
        table[root->ch] = code;
        return;
    }
    generateHuffmanCodeTable(root->left, code + "0", table);
    generateHuffmanCodeTable(root->right, code + "1", table);
}

// 对字符串进行哈夫曼编码
string encode(string s) {
    HuffmanNode *root = createHuffmanTree(s); // 创建哈夫曼树
    unordered_map<char, string> table; // 哈夫曼编码表
    generateHuffmanCodeTable(root, "", table); // 生成编码表
    string encoded = "";
    for (char c : s) {
        encoded += table[c]; // 将每个字符转换为对应的哈夫曼编码
    }
    destroyHuffmanTree(root); // 销毁哈夫曼树
    return encoded;
}

// 对哈夫曼编码进行解码
string decode(string encoded, HuffmanNode *root) {
    string decoded = "";
    HuffmanNode *node = root;
    for (char bit : encoded) {
        if (bit == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == nullptr && node->right == nullptr) {
            decoded += node->ch;
            node = root;
        }
    }
    return decoded;
}

int main() {
    string s = "hello world";
    cout << "Original string: " << s << endl;
    string encoded = encode(s);
    cout << "Encoded string: " << encoded << endl;
    string decoded = decode(encoded, createHuffmanTree(s));
    cout << "Decoded string: " << decoded << endl;
    return 0;
}