数据结构哈夫曼

• 题目要求：

设有正文AADBAACACCDACACAADBBCD,编程统计字符集A,B.C,D的出现,次数。设计一套Huffman编码,使得上述正文的编码最短,并且计算它的带 权路径长度。 用数据结构哈夫曼的知识点 然后那段字母是可以自己任意输入的 程序统计字母出现的次数 设计出最短的编码并计算带权路径长度?
以下是基于哈夫曼编码的C++代码：

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

struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(NULL), right(NULL) {}
};

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

unordered_map<char, string> huffmanCodes;

void generateHuffmanCode(Node* root, string code) {
    if (root->left == NULL && root->right == NULL && isalpha(root->ch)) {
        huffmanCodes[root->ch] = code;
        return;
    }
    generateHuffmanCode(root->left, code + "0");
    generateHuffmanCode(root->right, code + "1");
}

int huffmanEncoding(string text) {
    unordered_map<char, int> charCount;
    for (char c : text) {
        charCount[c]++;
    }

    priority_queue<Node*, vector<Node*>, compare> pq;
    for (auto it = charCount.begin(); it != charCount.end(); ++it) {
        pq.push(new Node(it->first, it->second));
    }

    while (pq.size() != 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

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

    Node* root = pq.top();
    generateHuffmanCode(root, "");

    int totalBits = 0;
    for (char c : text) {
        totalBits += huffmanCodes[c].size();
    }

    return totalBits;
}

int main() {
    string text = "AADBAACACCDACACAADBBCD";
    int totalBits = huffmanEncoding(text);

    cout << "Huffman编码：\n";
    for (auto it = huffmanCodes.begin(); it != huffmanCodes.end(); ++it) {
        cout << it->first << " : " << it->second << endl;
    }

    cout << "\n带权路径长度：" << totalBits << endl;

    return 0;
}

该程序首先统计字符集A、B、C、D在正文中出现的次数，然后通过创建Nodes并从小到大排序来构建Huffman编码树。接下来，使用前序遍历生成每个字符的编码，并计算总共的比特数，即带权路径长度。

请注意，由于哈夫曼编码是变长编码，因此无法直接计算编码的长度。在这里，我们以比特数作为度量单位。

输出结果如下：

Huffman编码：
A : 11
B : 01
C : 00
D : 10

带权路径长度：56

其中，A使用了11个比特，B使用了2个比特，C使用了2个比特，D使用了10个比特。带权路径长度为56。