Huffman编码和译码

Huffman编码和译码，在C++环境下的优秀代码，对编译环境有一定要求

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <iomanip>

using namespace std;

// 信源结构体
struct Source {
    char symbol;      // 信源符号
    double probability;  // 信源概率
};

// 节点结构体
struct Node {
    double probability;  // 节点概率
    string code;         // 节点对应的编码
    Node* left;          // 左子节点
    Node* right;         // 右子节点
    
    Node(double p) : probability(p), left(nullptr), right(nullptr) {}
};

// 比较器
struct CompareNodes {
    bool operator()(const Node* a, const Node* b) const {
        return a->probability > b->probability;
    }
};

// 构建哈夫曼树
Node* buildHuffmanTree(const vector<Source>& sources) {
    priority_queue<Node*, vector<Node*>, CompareNodes> pq;

    // 创建叶子节点并加入优先队列
    for (const auto& source : sources) {
        Node* node = new Node(source.probability);
        node->code += source.symbol;
        pq.push(node);
    }

    // 合并节点直到只剩下一个根节点
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

        Node* parent = new Node(left->probability + right->probability);
        parent->left = left;
        parent->right = right;

        pq.push(parent);
    }

    // 返回根节点
    return pq.top();
}

// 递归地遍历哈夫曼树，构建编码
void buildCodes(Node* root, string code, map<char, string>& codes) {
    if (root == nullptr)
        return;

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

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

// 输出信源的码长、码字和熵
void printEncodingDetails(const vector<Source>& sources, const map<char, string>& codes) {
    double entropy = 0.0;
    double avgCodeLength = 0.0;
	
	cout << "-----------------------------" << endl;
    cout << "消息\t概率\t码长\t码字" << endl;
    cout << "-----------------------------" << endl;

    for (const auto& source : sources) {
        string code = codes.at(source.symbol);
        int codeLength = code.length();
        double sourceEntropy = -log2(source.probability);

        entropy += source.probability * sourceEntropy;
        avgCodeLength += source.probability * codeLength;

        cout << setw(4) << source.symbol << "\t";
        cout << setw(6) << fixed << setprecision(2) << source.probability << "\t";
        cout << setw(4) << codeLength << "\t";
        cout << code << endl;
    }

    cout << "-----------------------------" << endl;
    cout << "信源熵: H(X) = -∑(p(x)log2(p(x))) = " << fixed << setprecision(2) << entropy << " bits" << endl;
    cout << "平均码长: L(X) = ∑(p(x)l(x)) = " << fixed << setprecision(2) << avgCodeLength << " bits" << endl;
    cout << "编码效率: E(X) = (H(X) / L(X)) * 100.0 = " << fixed << setprecision(2) << (entropy / avgCodeLength * 100.0) << "%" << endl;
}

// 译码函数
string decode(string encodedText, Node* root) {
    string decodedText;

    Node* current = root;
    for (char bit : encodedText) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }

        if (current->left == nullptr && current->right == nullptr) {
            decodedText += current->code;
            current = root;
        }
    }

    return decodedText;
}

int main() {
    int numSources;

    cout << "请输入消息个数：";
    cin >> numSources;

    vector<Source> sources(numSources);
    for (int i = 0; i < numSources; i++) {
        cout << "请输入第 " << (i + 1) << " 个消息符号：";
        cin >> sources[i].symbol;
        cout << "请输入第 " << (i + 1) << " 个消息概率：";
        cin >> sources[i].probability;
    }

    // 构建哈夫曼树和编码表
    Node* root = buildHuffmanTree(sources);
    map<char, string> codes;
    buildCodes(root, "", codes);

    // 输出编码信息
    printEncodingDetails(sources, codes);

    // 进行译码
    while (1) {
        char judge;
        cout << "\n是否进行译码（y/n）：";
        cin >> judge; 
        if (judge == 'y') {
            cout << "\n请输入要译码的二进制序列：";
            string encodedText;
            cin >> encodedText;
            string decodedText = decode(encodedText, root);
            cout << "译码结果：" << decodedText << endl;
        }
        else {
            break;
        }
    }
    // 释放动态分配的内存
    delete root;

    return 0;
}