c++输入一串字符串，根据字符串中字符出现的频率建立相应的哈夫曼树，并构造哈夫曼编码表。在此基础上： 1. 可以对压缩文件进行压缩（即编码）。 2. 可以对压缩后的二进制编码文件进行解压（即译码）。多组数据，每组数据为1行字符串（只考虑26个小写字母）。 • 当输入字符串为“0”时，输入结束。每组数据输出 2n+3行（n为输入字符串中字符类别的个数）： 1. 第1行：统计字符出现频率，格式为“字符:频度”，每两组字符之间用空格分隔，字符按ASCII码从小到大的顺序排列。 2. 第2行至第2n行：哈夫曼树的存储结构终态（如教材第5章表5.2(b)），每行内的数据用空格分隔。 3. 第2n+1行：每个字符的哈夫曼编码，格式为“字符:编码”，每两组字符之间用空格分隔，字符按ASCII码从小到大的顺序排列。 4. 第2n+2行：编码后的字符串。 5. 第2n+3行：解码后的字符串（与输入字符串相同）。

### C++ 实现哈夫曼树构建、编码和解码 以下是完整的 C++ 实现方案，涵盖了字符频率统计、哈夫曼树的构建、存储结构、编码表生成以及编码与解码的过程。 #### 字符频率统计 为了实现哈夫曼编码，首先需要统计输入字符串中各个字符的出现次数。这可以通过遍历字符串并利用 `std::unordered_map` 来完成[^1]。 ```cpp #include <iostream> #include <queue> #include <unordered_map> #include <string> #include <vector> using namespace std; // 定义哈夫曼树节点 struct HuffmanNode { char character; int frequency; HuffmanNode* left; HuffmanNode* right; HuffmanNode(char c, int f) : character(c), frequency(f), left(nullptr), right(nullptr) {} }; // 自定义比较函数用于优先队列 struct Compare { bool operator()(HuffmanNode* l, HuffmanNode* r) { return l->frequency > r->frequency; } }; ``` #### 哈夫曼树的构建 通过最小堆（优先队列）逐步合并频率最低的两个节点直到只剩下一个根节点，从而形成一棵哈夫曼树[^4]。 ```cpp void buildFrequencyMap(const string& input, unordered_map<char, int>& freqMap) { for (char ch : input) { freqMap[ch]++; } } HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) { priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq; for (auto pair : freqMap) { pq.push(new HuffmanNode(pair.first, pair.second)); } while (pq.size() != 1) { HuffmanNode* left = pq.top(); pq.pop(); HuffmanNode* right = pq.top(); pq.pop(); HuffmanNode* merged = new HuffmanNode('\0', left->frequency + right->frequency); merged->left = left; merged->right = right; pq.push(merged); } return pq.top(); } ``` #### 编码表生成 从根节点出发，沿着左子树标记为 '0'，右子树标记为 '1' 的方式递归生成每个字符对应的二进制编码[^2]。 ```cpp void generateCodes(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCodeTable) { if (!root) return; if (!root->left && !root->right && root->character != '\0') { huffmanCodeTable[root->character] = code; } generateCodes(root->left, code + "0", huffmanCodeTable); generateCodes(root->right, code + "1", huffmanCodeTable); } ``` #### 编码过程 根据生成的编码表将原始字符串转换为其对应的二进制形式[^3]。 ```cpp string encodeString(const string& input, const unordered_map<char, string>& huffmanCodeTable) { string encodedStr = ""; for (char ch : input) { encodedStr += huffmanCodeTable.at(ch); } return encodedStr; } ``` #### 解码过程 按照哈夫曼树的结构逐位解析二进制串还原成原字符串[^3]。 ```cpp string decodeString(string binaryStr, HuffmanNode* root) { string decodedStr = ""; HuffmanNode* current = root; for (char bit : binaryStr) { if (bit == '0') current = current->left; else if (bit == '1') current = current->right; if (!current->left && !current->right) { decodedStr += current->character; current = root; } } return decodedStr; } ``` #### 主程序逻辑 综合以上各部分功能模块编写主函数调用流程。 ```cpp int main() { string input = "sdfcvxgrsdfwerwrgsadddaqqwegx"; // 统计频率 unordered_map<char, int> freqMap; buildFrequencyMap(input, freqMap); cout << "Character Frequencies:" << endl; for (const auto &pair : freqMap) { cout << pair.first << ": " << pair.second << endl; } // 构建哈夫曼树 HuffmanNode* root = buildHuffmanTree(freqMap); // 生成编码表 unordered_map<char, string> huffmanCodeTable; generateCodes(root, "", huffmanCodeTable); cout << "\nHuffman Codes:" << endl; for (const auto &pair : huffmanCodeTable) { cout << pair.first << ": " << pair.second << endl; } // 编码 string encodedStr = encodeString(input, huffmanCodeTable); cout << "\nEncoded String:\n" << encodedStr << endl; // 解码 string decodedStr = decodeString(encodedStr, root); cout << "\nDecoded String:\n" << decodedStr << endl; return 0; } ``` 此代码实现了基于字符串频率的完整哈夫曼编码与解码操作，并输出了详细的中间结果以便验证其正确性。 ---