哈夫曼编码计算平均码长c++

哈夫曼编码是一种无损压缩数据的方法，其基本思想是利用出现频率较高的字符使用较短的编码，出现频率较低的字符使用较长的编码，以此来达到减少编码长度的目的。计算哈夫曼编码的平均码长需要先计算每个字符在编码中所占的比例，然后再将每个字符的比例与其编码长度相乘，最终将所有字符的结果相加即可。

下面是C++计算平均码长的示例代码：

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

// 定义哈夫曼树节点
struct HuffmanNode {
    char data; // 字符
    int freq; // 频率
    HuffmanNode *left, *right; // 左右子节点
    HuffmanNode(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};

// 定义比较函数
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 计算每个字符的频率
unordered_map<char, int> getCharFreq(string str) {
    unordered_map<char, int> freq;
    for (char c : str) {
        freq[c]++;
    }
    return freq;
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int> freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto p : freq) {
        pq.push(new HuffmanNode(p.first, p.second));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        int sumFreq = left->freq + right->freq;
        HuffmanNode* parent = new HuffmanNode('\0', sumFreq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 计算平均码长
double getAvgCodeLen(HuffmanNode* root, string str) {
    unordered_map<char, string> codes;
    string code;
    // 遍历哈夫曼树，构建编码表
    function<void(HuffmanNode*, string)> traverse = [&](HuffmanNode* node, string code) {
        if (!node) return;
        if (node->data != '\0') codes[node->data] = code;
        traverse(node->left, code + "0");
        traverse(node->right, code + "1");
    };
    traverse(root, "");
    // 计算平均码长
    double sumLen = 0.0;
    for (char c : str) {
        sumLen += codes[c].size();
    }
    return sumLen / str.size();
}

int main() {
    string str = "hello world";
    unordered_map<char, int> freq = getCharFreq(str);
    HuffmanNode* root = buildHuffmanTree(freq);
    double avgLen = getAvgCodeLen(root, str);
    cout << "平均码长为：" << avgLen << endl;
    return 0;
}