[已解决]哈夫曼编码

yangzhixiaohuli

本题要求字符的哈夫曼编码，注意建立的哈夫曼树严格按照左小右次小的顺序，并且哈夫曼编码时严格按照左‘0’右‘1’进行编码。

输入格式:
输入是各个字符在通信中出现的频率

输出格式:
输出是各个字符的哈夫曼编码，每个字母占一行

输入样例:
A:2
B:3
C:6
D:7
E:10
F:19
G:21
H:32
输出样例:
A:10000
B:10001
C:1001
D:1010
E:1011
F:00
G:01
H:11

这题用C或者C++怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-11-15 16:33:47

要解决这个问题，我们需要建立一个哈夫曼树，然后根据哈夫曼树生成对应字符的编码。以下是一个使用C++的实现思路：

1. 使用一个优先队列（最小堆）来构建哈夫曼树，这样可以方便地按需要的频率顺序提取节点。
2. 对每个字符和它的频率创建一个叶子节点，并将这些节点放入优先队列。
3. 依次从队列中取出两个频率最小的节点，合并它们成一个新节点（其频率为两个子节点频率之和），并将新节点放回队列。
4. 重复步骤3，直到队列中只剩下一个节点，这个节点就是哈夫曼树的根。
5. 根据哈夫曼树，生成每个字符的编码：左子树路径编码为'0'，右子树路径编码为'1'。

下面是一个简化的C++代码示例：

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

// 定义哈夫曼树的节点结构
struct Node {
    char ch;
    int freq;
    Node *left, *right;

    Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};

// 比较器，用于优先队列
struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

// 生成哈夫曼编码
void generateHuffmanCodes(Node* root, const std::string& code, std::unordered_map<char, std::string>& huffmanCodes) {
    if (!root) return;
    
    // 叶子节点，存储字符对应的编码
    if (!root->left && !root->right) {
        huffmanCodes[root->ch] = code;
    }

    // 递归左子树和右子树
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}

// 建立哈夫曼树
Node* buildHuffmanTree(const std::vector<std::pair<char, int>>& freqList) {
    std::priority_queue<Node*, std::vector<Node*>, Compare> minHeap;
    
    // 创建叶子节点
    for (const auto& pair : freqList) {
        minHeap.push(new Node(pair.first, pair.second));
    }
    
    while (minHeap.size() != 1) {
        Node* left = minHeap.top();
        minHeap.pop();
        Node* right = minHeap.top();
        minHeap.pop();

        // 创建新的合并节点
        int sum = left->freq + right->freq;
        Node* internalNode = new Node('\0', sum);
        internalNode->left = left;
        internalNode->right = right;

        minHeap.push(internalNode);
    }

    return minHeap.top(); // 根节点
}

int main() {
    // 输入字符和频率
    std::vector<std::pair<char, int>> freqList = {
        {'A', 2}, {'B', 3}, {'C', 6}, {'D', 7},
        {'E', 10}, {'F', 19}, {'G', 21}, {'H', 32}
    };
    
    Node* root = buildHuffmanTree(freqList);

    // 哈夫曼编码
    std::unordered_map<char, std::string> huffmanCodes;
    generateHuffmanCodes(root, "", huffmanCodes);

    // 输出各字符的编码
    for (const auto& pair : freqList) {
        std::cout << pair.first << ":" << huffmanCodes[pair.first] << "\n";
    }

    return 0;
}

**说明：**
- `Node`结构用于表示哈夫曼树的节点。
- `Compare`比较器用于在优先队列中排序。
- `buildHuffmanTree`函数用于构建哈夫曼树。
- `generateHuffmanCodes`函数用于递归生成各字符的哈夫曼编码。
- 主程序部分用于处理输入数据并输出结果。

这段代码读入字符频率后，会按哈夫曼编码规则输出各字符的编码。确保算法正确无误，并调整输入数据格式以确保程序能处理。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

要解决这个问题，我们需要建立一个哈夫曼树，然后根据哈夫曼树生成对应字符的编码。以下是一个使用C++的实现思路：

1. 使用一个优先队列（最小堆）来构建哈夫曼树，这样可以方便地按需要的频率顺序提取节点。
2. 对每个字符和它的频率创建一个叶子节点，并将这些节点放入优先队列。
3. 依次从队列中取出两个频率最小的节点，合并它们成一个新节点（其频率为两个子节点频率之和），并将新节点放回队列。
4. 重复步骤3，直到队列中只剩下一个节点，这个节点就是哈夫曼树的根。
5. 根据哈夫曼树，生成每个字符的编码：左子树路径编码为'0'，右子树路径编码为'1'。

下面是一个简化的C++代码示例：

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

// 定义哈夫曼树的节点结构
struct Node {
    char ch;
    int freq;
    Node *left, *right;

    Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
};

// 比较器，用于优先队列
struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

// 生成哈夫曼编码
void generateHuffmanCodes(Node* root, const std::string& code, std::unordered_map<char, std::string>& huffmanCodes) {
    if (!root) return;
    
    // 叶子节点，存储字符对应的编码
    if (!root->left && !root->right) {
        huffmanCodes[root->ch] = code;
    }

    // 递归左子树和右子树
    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}

// 建立哈夫曼树
Node* buildHuffmanTree(const std::vector<std::pair<char, int>>& freqList) {
    std::priority_queue<Node*, std::vector<Node*>, Compare> minHeap;
    
    // 创建叶子节点
    for (const auto& pair : freqList) {
        minHeap.push(new Node(pair.first, pair.second));
    }
    
    while (minHeap.size() != 1) {
        Node* left = minHeap.top();
        minHeap.pop();
        Node* right = minHeap.top();
        minHeap.pop();

        // 创建新的合并节点
        int sum = left->freq + right->freq;
        Node* internalNode = new Node('\0', sum);
        internalNode->left = left;
        internalNode->right = right;

        minHeap.push(internalNode);
    }

    return minHeap.top(); // 根节点
}

int main() {
    // 输入字符和频率
    std::vector<std::pair<char, int>> freqList = {
        {'A', 2}, {'B', 3}, {'C', 6}, {'D', 7},
        {'E', 10}, {'F', 19}, {'G', 21}, {'H', 32}
    };
    
    Node* root = buildHuffmanTree(freqList);

    // 哈夫曼编码
    std::unordered_map<char, std::string> huffmanCodes;
    generateHuffmanCodes(root, "", huffmanCodes);

    // 输出各字符的编码
    for (const auto& pair : freqList) {
        std::cout << pair.first << ":" << huffmanCodes[pair.first] << "\n";
    }

    return 0;
}

**说明：**
- `Node`结构用于表示哈夫曼树的节点。
- `Compare`比较器用于在优先队列中排序。
- `buildHuffmanTree`函数用于构建哈夫曼树。
- `generateHuffmanCodes`函数用于递归生成各字符的哈夫曼编码。
- 主程序部分用于处理输入数据并输出结果。

这段代码读入字符频率后，会按哈夫曼编码规则输出各字符的编码。确保算法正确无误，并调整输入数据格式以确保程序能处理。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。