[已解决]哈夫曼编码

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++代码示例：

1. #include <iostream>
   
2. #include <queue>
   
3. #include <unordered_map>
   
4. #include <vector>
   
5. 
   
6. // 定义哈夫曼树的节点结构
   
7. struct Node {
   
8.     char ch;
   
9.     int freq;
   
10.     Node *left, *right;
    
11. 
    
12.     Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
    
13. };
    
14. 
    
15. // 比较器，用于优先队列
    
16. struct Compare {
    
17.     bool operator()(Node* l, Node* r) {
    
18.         return l->freq > r->freq;
    
19.     }
    
20. };
    
21. 
    
22. // 生成哈夫曼编码
    
23. void generateHuffmanCodes(Node* root, const std::string& code, std::unordered_map<char, std::string>& huffmanCodes) {
    
24.     if (!root) return;
    
25.    
    
26.     // 叶子节点，存储字符对应的编码
    
27.     if (!root->left && !root->right) {
    
28.         huffmanCodes[root->ch] = code;
    
29.     }
    
30. 
    
31.     // 递归左子树和右子树
    
32.     generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    
33.     generateHuffmanCodes(root->right, code + "1", huffmanCodes);
    
34. }
    
35. 
    
36. // 建立哈夫曼树
    
37. Node* buildHuffmanTree(const std::vector<std::pair<char, int>>& freqList) {
    
38.     std::priority_queue<Node*, std::vector<Node*>, Compare> minHeap;
    
39.    
    
40.     // 创建叶子节点
    
41.     for (const auto& pair : freqList) {
    
42.         minHeap.push(new Node(pair.first, pair.second));
    
43.     }
    
44.    
    
45.     while (minHeap.size() != 1) {
    
46.         Node* left = minHeap.top();
    
47.         minHeap.pop();
    
48.         Node* right = minHeap.top();
    
49.         minHeap.pop();
    
50. 
    
51.         // 创建新的合并节点
    
52.         int sum = left->freq + right->freq;
    
53.         Node* internalNode = new Node('\0', sum);
    
54.         internalNode->left = left;
    
55.         internalNode->right = right;
    
56. 
    
57.         minHeap.push(internalNode);
    
58.     }
    
59. 
    
60.     return minHeap.top(); // 根节点
    
61. }
    
62. 
    
63. int main() {
    
64.     // 输入字符和频率
    
65.     std::vector<std::pair<char, int>> freqList = {
    
66.         {'A', 2}, {'B', 3}, {'C', 6}, {'D', 7},
    
67.         {'E', 10}, {'F', 19}, {'G', 21}, {'H', 32}
    
68.     };
    
69.    
    
70.     Node* root = buildHuffmanTree(freqList);
    
71. 
    
72.     // 哈夫曼编码
    
73.     std::unordered_map<char, std::string> huffmanCodes;
    
74.     generateHuffmanCodes(root, "", huffmanCodes);
    
75. 
    
76.     // 输出各字符的编码
    
77.     for (const auto& pair : freqList) {
    
78.         std::cout << pair.first << ":" << huffmanCodes[pair.first] << "\n";
    
79.     }
    
80. 
    
81.     return 0;
    
82. }

复制代码

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

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

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

跳转到最佳答案楼层

FishC

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

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

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

1. #include <iostream>
   
2. #include <queue>
   
3. #include <unordered_map>
   
4. #include <vector>
   
5. 
   
6. // 定义哈夫曼树的节点结构
   
7. struct Node {
   
8.     char ch;
   
9.     int freq;
   
10.     Node *left, *right;
    
11. 
    
12.     Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
    
13. };
    
14. 
    
15. // 比较器，用于优先队列
    
16. struct Compare {
    
17.     bool operator()(Node* l, Node* r) {
    
18.         return l->freq > r->freq;
    
19.     }
    
20. };
    
21. 
    
22. // 生成哈夫曼编码
    
23. void generateHuffmanCodes(Node* root, const std::string& code, std::unordered_map<char, std::string>& huffmanCodes) {
    
24.     if (!root) return;
    
25.    
    
26.     // 叶子节点，存储字符对应的编码
    
27.     if (!root->left && !root->right) {
    
28.         huffmanCodes[root->ch] = code;
    
29.     }
    
30. 
    
31.     // 递归左子树和右子树
    
32.     generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    
33.     generateHuffmanCodes(root->right, code + "1", huffmanCodes);
    
34. }
    
35. 
    
36. // 建立哈夫曼树
    
37. Node* buildHuffmanTree(const std::vector<std::pair<char, int>>& freqList) {
    
38.     std::priority_queue<Node*, std::vector<Node*>, Compare> minHeap;
    
39.    
    
40.     // 创建叶子节点
    
41.     for (const auto& pair : freqList) {
    
42.         minHeap.push(new Node(pair.first, pair.second));
    
43.     }
    
44.    
    
45.     while (minHeap.size() != 1) {
    
46.         Node* left = minHeap.top();
    
47.         minHeap.pop();
    
48.         Node* right = minHeap.top();
    
49.         minHeap.pop();
    
50. 
    
51.         // 创建新的合并节点
    
52.         int sum = left->freq + right->freq;
    
53.         Node* internalNode = new Node('\0', sum);
    
54.         internalNode->left = left;
    
55.         internalNode->right = right;
    
56. 
    
57.         minHeap.push(internalNode);
    
58.     }
    
59. 
    
60.     return minHeap.top(); // 根节点
    
61. }
    
62. 
    
63. int main() {
    
64.     // 输入字符和频率
    
65.     std::vector<std::pair<char, int>> freqList = {
    
66.         {'A', 2}, {'B', 3}, {'C', 6}, {'D', 7},
    
67.         {'E', 10}, {'F', 19}, {'G', 21}, {'H', 32}
    
68.     };
    
69.    
    
70.     Node* root = buildHuffmanTree(freqList);
    
71. 
    
72.     // 哈夫曼编码
    
73.     std::unordered_map<char, std::string> huffmanCodes;
    
74.     generateHuffmanCodes(root, "", huffmanCodes);
    
75. 
    
76.     // 输出各字符的编码
    
77.     for (const auto& pair : freqList) {
    
78.         std::cout << pair.first << ":" << huffmanCodes[pair.first] << "\n";
    
79.     }
    
80. 
    
81.     return 0;
    
82. }

复制代码

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

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

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