#include<iostream> #include<map> #include<vector> #include<cstdio> #include<queue> #include<cstring> using namespace std; /********** Begin **********/ // 函数，结构体，全局变量定义区 /********** End **********/ int main(void){ /********** Begin **********/ /********** End **********/ return 0; }

### C++ 实现 Huffman 编码树并计算最短编码长度 以下是一个完整的 C++ 程序，用于实现 Huffman 编码树以及根据输入字符频率计算最短编码长度。程序分为以下几个部分：定义节点类、构建 Huffman 树、生成编码表以及最终计算总编码长度。 #### 节点定义 在 C++ 中，我们可以通过结构体 `Node` 来表示 Huffman 树的节点。每个节点包含字符、频率、左子节点指针和右子节点指针。 ```cpp #include <iostream> #include <vector> #include <queue> #include <unordered_map> #include <string> using namespace std; // 定义 Huffman 树节点 struct Node { char character; // 字符 int frequency; // 出现频率 Node* left; // 左子节点 Node* right; // 右子节点 Node(char ch, int freq) : character(ch), frequency(freq), left(nullptr), right(nullptr) {} ~Node() { delete left; delete right; } bool operator<(const Node& other) const { return this->frequency > other.frequency; // 重载小于运算符以支持优先队列按频率升序排列 } }; ``` #### 构建 Huffman 树 通过最小堆（优先队列）来动态构建 Huffman 树。每次从堆中取出两个频率最低的节点，合并成一个新节点后再放回堆中，直到堆中仅剩下一个节点为止。 ```cpp // 构建 Huffman 树 Node* buildHuffmanTree(unordered_map<char, int>& frequencies) { priority_queue<Node> minHeap; for (auto pair : frequencies) { minHeap.push(Node(pair.first, pair.second)); } while (minHeap.size() != 1) { Node* left = new Node(minHeap.top()); minHeap.pop(); Node* right = new Node(minHeap.top()); minHeap.pop(); Node* combined = new Node('\0', left->frequency + right->frequency); combined->left = left; combined->right = right; minHeap.push(*combined); } return new Node(minHeap.top()); } ``` #### 生成编码表 递归遍历 Huffman 树，记录从根节点到叶子节点的路径作为编码值，并将其存入编码表中。 ```cpp // 生成编码表 void generateCodes(Node* root, string code, unordered_map<char, string>& codes) { if (!root) return; if (!root->left && !root->right && root->character != '\0') { codes[root->character] = code; } generateCodes(root->left, code + "0", codes); // 向左走标记为 "0" generateCodes(root->right, code + "1", codes); // 向右走标记为 "1" } ``` #### 计算最短编码长度 根据生成的编码表和原始字符频率，计算总的编码长度。 ```cpp int calculateMinEncodedLength(const unordered_map<char, string>& codes, const unordered_map<char, int>& frequencies) { int totalLength = 0; for (auto pair : frequencies) { char ch = pair.first; int freq = pair.second; if (codes.find(ch) != codes.end()) { totalLength += codes.at(ch).length() * freq; } } return totalLength; } ``` #### 主函数 主函数负责读取输入数据、调用上述功能模块并输出结果。 ```cpp int main() { int n; cin >> n; unordered_map<char, int> frequencies; for (int i = 0; i < n; ++i) { char ch; int freq; cin >> ch >> freq; frequencies[ch] = freq; } Node* huffmanRoot = buildHuffmanTree(frequencies); unordered_map<char, string> codes; generateCodes(huffmanRoot, "", codes); int minLength = calculateMinEncodedLength(codes, frequencies); cout << "Minimum encoded length: " << minLength << endl; delete huffmanRoot; // 清理内存 return 0; } ``` --- ###