要求用c++写出这个程序

Question

用数据结构哈夫曼的知识点 然后那段字母是可以自己任意输入的 程序统计字母出现的次数 设计出最短的编码并计算带权路径长度 代码最好简单易懂

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

以下是一个用C++编写的程序，用于统计给定字符串中字符集A、B、C、D的出现次数，并根据Huffman编码算法生成最短编码并计算带权路径长度。

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

// Huffman树节点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较函数，用于优先队列中的节点排序
struct NodeCompare {
    bool operator()(const Node* a, const Node* b) {
        return a->freq > b->freq;
    }
};

// 统计字符集A、B、C、D的出现次数
map<char, int> getCharacterFrequency(const string& str) {
    map<char, int> freq;
    for (char c : str) {
        if (c == 'A' || c == 'B' || c == 'C' || c == 'D') {
            freq[c]++;
        }
    }
    return freq;
}
// 根据字符集的频率构建Huffman树
Node* buildHuffmanTree(const map<char, int>& freq) {
    priority_queue<Node*, vector<Node*>, NodeCompare> pq;

    // 创建Huffman树的叶节点
    for (const auto& pair : freq) {
        Node* node = new Node(pair.first, pair.second);
        pq.push(node);
    }

    // 构建Huffman树
    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);
    }

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

// 生成Huffman编码
void generateHuffmanCode(Node* root, string code, map<char, string>& codes) {
    if (root == nullptr) {
        return;
    }

    if (root->ch != '$') {  // 到达叶节点
        codes[root->ch] = code;
    }

    generateHuffmanCode(root->left, code + "0", codes);
    generateHuffmanCode(root->right, code + "1", codes);
}
// 计算带权路径长度
int calculateWeightedPathLength(const map<char, int>& freq, const map<char, string>& codes) {
    int weightedPathLength = 0;

    for (const auto& pair : freq) {
        char ch = pair.first;
        int freq = pair.second;
        string code = codes.at(ch);
        weightedPathLength += freq * code.length();
    }

    return weightedPathLength;
}

// 打印Huffman编码
void printHuffmanCode(const map<char, string>& codes) {
    for (const auto& pair : codes) {
        cout << "字符 " << pair.first << " 编码为 " << pair.second << endl;
    }
}

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

    // 统计字符集的出现次数
    map<char, int> freq = getCharacterFrequency(text);

    // 构建Huffman树
    Node* root = buildHuffmanTree(freq);

    // 生成Huffman编码
    map<char, string> codes;
    generateHuffmanCode(root, "", codes);

    // 计算带权路径长度
    int weightedPathLength = calculateWeightedPathLength(freq, codes);

    // 打印Huffman编码和带权路径长度
    printHuffmanCode(codes);
    cout << "带权路径长度为 " << weightedPathLength << endl;

    // 释放Huffman树内存
    // 这里可以实现一个析构函数递归释放内存，也可以使用后续遍历手动释放内存

    return 0;
}

该程序首先统计给定字符串中字符集A、B、C、D的出现次数。然后根据字符集的频率构建Huffman树。利用Huffman树生成字符集的Huffman编码。最后根据频率和编码计算带权路径长度，并打印Huffman编码和带权路径长度。

注意：程序中没有实现Huffman树的内存释放部分，你可以根据实际情况自行实现。