费诺编码的C++编程实现

费诺编码（也称为霍夫曼-费诺编码）是一种可变长度编码，用于将一个字符集中的每个字符映射到一系列比特。它是一种无损数据压缩算法，在通信和存储中广泛应用。下面是一个简单的C++程序，演示如何实现费诺编码：

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

struct TreeNode {
    char val;
    int freq;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char v, int f) : val(v), freq(f), left(nullptr), right(nullptr) {}
    ~TreeNode() {
        delete left;
        delete right;
    }
};

struct Compare {
    bool operator()(const TreeNode* a, const TreeNode* b) {
        return a->freq > b->freq;
    }
};

void encode(TreeNode* root, string code, unordered_map<char, string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) {
        codes[root->val] = code;
        return;
    }
    encode(root->left, code + "0", codes);
    encode(root->right, code + "1", codes);
}

string huffman_fano_encoding(string s) {
    // 统计字符频率
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    // 构造哈夫曼树
    priority_queue<TreeNode*, vector<TreeNode*>, Compare> pq;
    for (auto& p : freq) pq.push(new TreeNode(p.first, p.second));
    while (pq.size() > 1) {
        auto left = pq.top(); pq.pop();
        auto right = pq.top(); pq.pop();
        auto parent = new TreeNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    // 生成编码表
    unordered_map<char, string> codes;
    encode(pq.top(), "", codes);
    // 编码字符串
    string encoded = "";
    for (char c : s) encoded += codes[c];
    // 返回编码结果
    return encoded;
}

int main() {
    string s = "Hello, world!";
    string encoded = huffman_fano_encoding(s);
    cout << "Encoded: " << encoded << endl;
    return 0;
}

程序首先统计输入字符串中每个字符出现的频率，然后构造哈夫曼树，生成编码表并将输入字符串编码。在这个实现中，哈夫曼树使用优先队列来维护节点，每次将最小的两个节点合并为一个新的节点，直到只剩下一个根节点。编码表使用一个哈希表来存储每个字符的编码，然后将输入字符串中的每个字符替换为它的编码。