用c++实现哈夫曼编码

哈夫曼编码是一种前缀编码方式，在通信领域广泛应用。下面是使用 C++ 实现哈夫曼编码的基本步骤：

1. 定义一个结构体来表示哈夫曼树的节点：

struct Node {
    char ch;  // 字符
    int weight; // 权重
    Node *left, *right;  // 左右子树指针
};

2. 定义一个比较函数，用于建立小根堆：

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

3. 定义一个函数，用于构建哈夫曼树：

Node* buildHuffmanTree(map<char, int>& mp) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (auto iter : mp) {
        Node* node = new Node;
        node->ch = iter.first;
        node->weight = iter.second;
        node->left = node->right = nullptr;
        pq.push(node);
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node;
        parent->ch = '\0';
        parent->weight = left->weight + right->weight;
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    Node* root = pq.top();
    pq.pop();
    return root;
}

4. 定义一个递归函数，用于生成哈夫曼编码：

void generateHuffmanCode(Node* root, string code, map<char, string>& huffmanCode) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCode[root->ch] = code;
        return;
    }
    generateHuffmanCode(root->left, code + "0", huffmanCode);
    generateHuffmanCode(root->right, code + "1", huffmanCode);
}

5. 定义一个函数，用于压缩字符串：

string compress(string str, map<char, string>& huffmanCode) {
    string compressedStr = "";
    for (char ch : str) {
        compressedStr += huffmanCode[ch];
    }
    return compressedStr;
}

6. 定义一个函数，用于解压字符串：

string decompress(string compressedStr, Node* root) {
    string originalStr = "";
    Node* node = root;
    for (char ch : compressedStr) {
        if (ch == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == nullptr && node->right == nullptr) {
            originalStr += node->ch;
            node = root;
        }
    }
    return originalStr;
}

完整代码如下：

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

struct Node {
    char ch;
    int weight;
    Node *left, *right;
};

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

Node* buildHuffmanTree(map<char, int>& mp) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (auto iter : mp) {
        Node* node = new Node;
        node->ch = iter.first;
        node->weight = iter.second;
        node->left = node->right = nullptr;
        pq.push(node);
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node;
        parent->ch = '\0';
        parent->weight = left->weight + right->weight;
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    Node* root = pq.top();
    pq.pop();
    return root;
}

void generateHuffmanCode(Node* root, string code, map<char, string>& huffmanCode) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCode[root->ch] = code;
        return;
    }
    generateHuffmanCode(root->left, code + "0", huffmanCode);
    generateHuffmanCode(root->right, code + "1", huffmanCode);
}

string compress(string str, map<char, string>& huffmanCode) {
    string compressedStr = "";
    for (char ch : str) {
        compressedStr += huffmanCode[ch];
    }
    return compressedStr;
}

string decompress(string compressedStr, Node* root) {
    string originalStr = "";
    Node* node = root;
    for (char ch : compressedStr) {
        if (ch == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->left == nullptr && node->right == nullptr) {
            originalStr += node->ch;
            node = root;
        }
    }
    return originalStr;
}

int main() {
    string str = "hello world";
    map<char, int> mp;
    for (char ch : str) {
        mp[ch]++;
    }
    Node* root = buildHuffmanTree(mp);
    map<char, string> huffmanCode;
    generateHuffmanCode(root, "", huffmanCode);
    string compressedStr = compress(str, huffmanCode);
    cout << "Compressed string: " << compressedStr << endl;
    string originalStr = decompress(compressedStr, root);
    cout << "Original string: " << originalStr << endl;
    return 0;
}