哈夫曼编码译码器c++

以下是一个用C++实现的哈夫曼编码译码器的示例：

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

// 哈夫曼树节点
struct Node {
    char data; // 字符
    int freq; // 频度
    Node* left;
    Node* right;
};

// 比较函数，用于优先队列的排序
struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 创建哈夫曼树
Node* createHuffmanTree(unordered_map<char, int>& freqMap) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    // 将字符和频度转化为节点，并加入优先队列
    for (auto& pair : freqMap) {
        Node* newNode = new Node();
        newNode->data = pair.first;
        newNode->freq = pair.second;
        newNode->left = nullptr;
        newNode->right = nullptr;
        pq.push(newNode);
    }

    // 构建哈夫曼树
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

        Node* parent = new Node();
        parent->data = '\0';
        parent->freq = left->freq + right->freq;
        parent->left = left;
        parent->right = right;

        pq.push(parent);
    }

    return pq.top();
}

// 生成哈夫曼编码
void generateHuffmanCodes(Node* root, string code, unordered_map<char, string>& codes) {
    if (root == nullptr) {
        return;
    }

    if (root->left == nullptr && root->right == nullptr) {
        codes[root->data] = code;
    }

    generateHuffmanCodes(root->left, code + "0", codes);
    generateHuffmanCodes(root->right, code + "1", codes);
}

// 哈夫曼编码
string encode(string text, unordered_map<char, string>& codes) {
    string encodedText = "";
    for (char c : text) {
        encodedText += codes[c];
    }
    return encodedText;
}

// 哈夫曼译码
string decode(string encodedText, Node* root) {
    string decodedText = "";
    Node* curr = root;
    for (char c : encodedText) {
        if (c == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }

        if (curr->left == nullptr && curr->right == nullptr) {
            decodedText += curr->data;
            curr = root;
        }
    }
    return decodedText;
}

int main() {
    // 字符集及频度
    unordered_map<char, int> freqMap = {
        {' ', 44}, {'A', 64}, {'B', 13}, {'C', 42}, {'D', 32}, {'E', 103}, {'F', 21}, {'G', 15},
        {'H', 37}, {'I', 57}, {'J', 1}, {'K', 5}, {'L', 52}, {'M', 20}, {'N', 57}, {'O', 77},
        {'P', 15}, {'Q', 1}, {'R', 84}, {'S', 51}, {'T', 80}, {'U', 23}, {'V', 8}, {'W', 18},
        {'X', 10}, {'Y', 16}, {'Z', 1}, {'.', 1}
    };

    // 创建哈夫曼树
    Node* root = createHuffmanTree(freqMap);

    // 生成哈夫曼编码
    unordered_map<char, string> codes;
    generateHuffmanCodes(root, "", codes);

    // 哈夫曼编码示例
    string text = "HELLO WORLD";
    string encodedText = encode(text, codes);
    cout << "Encoded Text: " << encodedText << endl;

    // 哈夫曼译码示例
    string decodedText = decode(encodedText, root);
    cout << "Decoded Text: " << decodedText << endl;

    return 0;
}