用Ｃ＋＋写一个哈夫曼编码程序

以下是用C++实现哈夫曼编码的程序：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 哈夫曼树的节点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;

    Node(char ch, int freq, Node* left = nullptr, Node* right = nullptr) : ch(ch), freq(freq), left(left), right(right) {}
};

struct Compare {
    bool operator()(Node* left, Node* right) {
        return left->freq > right->freq;
    }
};

// 建立哈夫曼树
Node* buildHuffmanTree(const string& str) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    // 统计字符的频率
    unordered_map<char, int> freq;
    for (char c : str) {
        freq[c]++;
    }

    // 把每个字符的频率作为节点的权值，加入优先队列
    for (auto& p : freq) {
        pq.push(new Node(p.first, p.second));
    }

    // 依次取出队列中的前两个节点，组成一个新节点，直到队列中只有一个节点为止
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();

        Node* right = pq.top();
        pq.pop();

        Node* parent = new Node('\0', left->freq + right->freq, left, right);
        pq.push(parent);
    }

    return pq.top();
}

// 将字符与二进制编码映射保存在哈希表中
void buildEncodingMap(Node* root, string& code, unordered_map<char, string>& encodingMap) {
    if (!root) {
        return;
    }

    if (!root->left && !root->right) {
        encodingMap[root->ch] = code;
    }

    if (root->left) {
        code.push_back('0');
        buildEncodingMap(root->left, code, encodingMap);
        code.pop_back();
    }

    if (root->right) {
        code.push_back('1');
        buildEncodingMap(root->right, code, encodingMap);
        code.pop_back();
    }
}

// 哈夫曼编码
string huffmanEncode(const string& str) {
    Node* root = buildHuffmanTree(str);

    unordered_map<char, string> encodingMap;
    string code;
    buildEncodingMap(root, code, encodingMap);

    string encodedStr;
    for (char c : str) {
        encodedStr += encodingMap[c];
    }

    return encodedStr;
}

// 哈夫曼解码
string huffmanDecode(const string& str, Node* root) {
    string decodedStr;
    Node* p = root;
    for (char c : str) {
        if (c == '0') {
            p = p->left;
        } else {
            p = p->right;
        }

        if (!p->left && !p->right) {
            decodedStr += p->ch;
            p = root;
        }
    }

    return decodedStr;
}

int main() {
    string str = "Huffman coding is a data compression algorithm.";
    cout << "原始字符串：" << str << endl;

    string encodedStr = huffmanEncode(str);
    cout << "编码后的字符串：" << encodedStr << endl;

    Node* root = buildHuffmanTree(str);
    string decodedStr = huffmanDecode(encodedStr, root);
    cout << "解码后的字符串：" << decodedStr << endl;

    return 0;
}

该程序先构建哈夫曼树，然后通过遍历哈夫曼树得到每个字符的二进制编码，最后将原始字符串转换为二进制编码。接着进行解码，通过遍历哈夫曼树对二进制编码进行解码。