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

赫夫曼编码是一种可变字长编码，它可以将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示，从而达到压缩数据的目的。下面是用 C++ 实现赫夫曼编码的一种方法：

1. 定义结构体节点，用于表示每个字符和它出现的频率：

struct Node {
    char ch;  // 字符
    int freq;  // 频率
    Node* left;  // 左子节点
    Node* right;  // 右子节点
    Node(char c, int f): ch(c), freq(f), left(nullptr), right(nullptr) {}
};

2. 定义比较器，用于构建最小堆：

struct cmp {
    bool operator() (Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

3. 构建最小堆，并将每个字符作为节点插入堆中：

priority_queue<Node*, vector<Node*>, cmp> min_heap;
unordered_map<char, int> freq_map;  // 统计每个字符的频率
for (char c : input_str) {
    freq_map[c]++;
}
for (auto& kv : freq_map) {
    Node* node = new Node(kv.first, kv.second);
    min_heap.push(node);
}

4. 用最小堆构建赫夫曼树：

while (min_heap.size() > 1) {
    Node* left = min_heap.top();
    min_heap.pop();
    Node* right = min_heap.top();
    min_heap.pop();
    Node* parent = new Node('#', left->freq + right->freq);
    parent->left = left;
    parent->right = right;
    min_heap.push(parent);
}
Node* root = min_heap.top();

5. 根据赫夫曼树构建编码表，并对输入字符串进行编码：

unordered_map<char, string> code_map;  // 存储每个字符的编码
function<void(Node*, string)> dfs = [&](Node* node, string s) {
    if (!node) return;
    if (!node->left && !node->right) {
        code_map[node->ch] = s;
    }
    dfs(node->left, s + "0");
    dfs(node->right, s + "1");
};
dfs(root, "");
string encoded_str;
for (char c : input_str) {
    encoded_str += code_map[c];
}

完整代码如下：

#include <iostream>
#include <queue>
#include <unordered_map>
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) {}
};

struct cmp {
    bool operator() (Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

int main() {
    string input_str = "hello world";
    priority_queue<Node*, vector<Node*>, cmp> min_heap;
    unordered_map<char, int> freq_map;  // 统计每个字符的频率
    for (char c : input_str) {
        freq_map[c]++;
    }
    for (auto& kv : freq_map) {
        Node* node = new Node(kv.first, kv.second);
        min_heap.push(node);
    }
    while (min_heap.size() > 1) {  // 构建赫夫曼树
        Node* left = min_heap.top();
        min_heap.pop();
        Node* right = min_heap.top();
        min_heap.pop();
        Node* parent = new Node('#', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        min_heap.push(parent);
    }
    Node* root = min_heap.top();
    unordered_map<char, string> code_map;  // 存储每个字符的编码
    function<void(Node*, string)> dfs = [&](Node* node, string s) {
        if (!node) return;
        if (!node->left && !node->right) {
            code_map[node->ch] = s;
        }
        dfs(node->left, s + "0");
        dfs(node->right, s + "1");
    };
    dfs(root, "");
    string encoded_str;
    for (char c : input_str) {  // 对输入字符串进行编码
        encoded_str += code_map[c];
    }
    cout << "Encoded string: " << encoded_str << endl;
    return 0;
}