数据结构与算法：哈夫曼数编码

Question

【实验题目】:本实验要求输入一串电文字符实现哈夫曼编码，输出每个字符出现的频率和其对应的哈夫曼编码。(用C或者C++实现均可) 要实现本设计的要求，必须实现以下功能: (1)电文字符串中字符的个数及每个字符出现频率的统计。 (2)哈夫曼树的建立。 (3)哈夫曼编码的生成。 (4)对电文编码。由于本书理论篇中给出的哈夫曼树的建立和哈夫曼编码的算法，下面简单分析电文字符串的统计。假设电文字符串只包含英文字母(不区分大小写)，该算法的实现思想是定义一个含有 26个元素的临时整型数组，用来存储每个字母出现的次数。首先将电文中的字母全部转换为大写字母，因为大写字母的 ASCII码与整数1~26之间相差为 64，因此在算法中使用字母减去64作为统计数组的下标对号入座，然后用一个循环判断统计各类字符个数的数组元素是否为零，若不为零，表示该字符在电文中出现，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个字符数组的元素中。

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个哈夫曼编码的程序，我们可以按照以下步骤进行：

1. 统计字符频率。
2. 构建优先队列（最小堆）。
3. 建立哈夫曼树。
4. 生成哈夫曼编码。
5. 对电文进行编码。

以下是完整的C++代码实现：

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>

// 定义节点类
struct Node {
    char data;
    int freq;
    Node* left;
    Node* right;

    Node(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
};

// 比较函数用于最小堆
bool compareNodes(Node* n1, Node* n2) {
    return n1->freq > n2->freq;
}

// 创建一个新的哈夫曼节点
Node* createNode(char ch, int freq) {
    return new Node(ch, freq);
}

// 合并两个最小节点
Node* mergeNodes(Node* node1, Node* node2) {
    Node* newNode = createNode('\0', node1->freq + node2->freq);
    newNode->left = node1;
    newNode->right = node2;
    return newNode;
}

// 从优先队列中删除最小节点
Node* extractMin(std::priority_queue<Node*, std::vector<Node*>, decltype(&compareNodes)> &pq) {
    Node* minNode = pq.top();
    pq.pop();
    return minNode;
}

// 哈夫曼树构建函数
Node* buildHuffmanTree(const std::vector<std::pair<char, int>>& frequencyTable) {
    std::priority_queue<Node*, std::vector<Node*>, decltype(&compareNodes)> pq;

    for (const auto& pair : frequencyTable) {
        Node* newNode = createNode(pair.first, pair.second);
        pq.push(newNode);
    }

    while (pq.size() != 1) {
        Node* node1 = extractMin(pq);
        Node* node2 = extractMin(pq);

        Node* newNode = mergeNodes(node1, node2);
        pq.push(newNode);
    }

    return pq.top();
}

// 生成哈夫曼编码
std::unordered_map<char, std::string> generateCodes(Node* root, std::string code) {
    if (root == nullptr)
        return {};

    if (root->data != '\0') {
        huffmanCodes[root->data] = code;
    }

    generateCodes(root->left, code + "0");
    generateCodes(root->right, code + "1");

    return huffmanCodes;
}

// 电文编码
std::string encodeText(const std::string& text, const std::unordered_map<char, std::string>& huffmanCodes) {
    std::string encodedText;
    for (char c : text) {
        encodedText += huffmanCodes[tolower(c)];
    }
    return encodedText;
}

int main() {
    // 输入电文字符串
    std::string inputText;
    std::cout << "Enter the text: ";
    std::getline(std::cin, inputText);

    std::unordered_map<char, int> frequencyTable;
    for (char c : inputText) {
        frequencyTable[toupper(c)]++;
    }

    // 排序频率表，确保字符按频率降序排列
    std::vector<std::pair<char, int>> sortedFrequencyTable(frequencyTable.begin(), frequencyTable.end());
    std::sort(sortedFrequencyTable.begin(), sortedFrequencyTable.end(),
              [](const std::pair<char, int>& a, const std::pair<char, int>& b) { return a.second > b.second; });

    // 建立哈夫曼树
    Node* huffmanRoot = buildHuffmanTree(sortedFrequencyTable);

    // 生成哈夫曼编码
    std::unordered_map<char, std::string> huffmanCodes;
    huffmanCodes = generateCodes(huffmanRoot, "");

    // 输出字符及其频率
    std::cout << "Character Frequency:\n";
    for (const auto& pair : sortedFrequencyTable) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

    // 输出哈夫曼编码
    std::cout << "Huffman Codes:\n";
    for (const auto& pair : huffmanCodes) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

    // 对电文编码
    std::string encodedText = encodeText(inputText, huffmanCodes);
    std::cout << "Encoded Text: " << encodedText << "\n";

    return 0;
}

这段代码首先统计了输入文本中每个字符的频率，然后根据频率构建了一个哈夫曼树，接着生成了哈夫曼编码，并最终对整个输入文本进行了编码。注意，此代码仅适用于英文字符，且不考虑空格和其他非字母字符。如果你需要处理其他字符类型，可以适当修改代码。