岭南师范算法设计：Huffman编码与数据结构应用

岭南师范学院2017级软件服务外包专业在蔡广基老师的《算法设计与分析》课程中进行的第四次作业，主要涉及的是算法分析中的Huffman编码问题。作业内容包括以下几个部分： 1. **Huffman树构建**: 这部分要求构建一个Huffman树，这是一种用于数据压缩的二叉树，特别适合于频度低的字符。Huffman树通过合并频率最低的两个节点形成新节点，直到所有节点合并成一棵树。作业中涉及到创建Huffman树的函数`CreateHuffman`，它首先初始化一个空的哈夫曼树，并通过比较每个字符的频率，逐步合并节点，直至形成一棵完全平衡的树。 2. **节点操作**: 函数`FindLetter`是用于查找特定节点的操作，输入是数组`WeightNum`，存储了字符及其对应的频率。该函数根据给定的数据值`data`，在`WeightNum`数组中找到具有较大或等于`data`的节点索引，并更新两个指针`mark`和`mark1`，分别表示当前数据应该插入的位置以及可能的左孩子位置。 3. **字符编码**: Huffman树的一个关键应用是生成字符的编码。在本作业中，对于字符集`{A, C, G, T}`，已知它们的频率分别为0.31, 0.2, 0.09, 0.4。根据Huffman树的特性，频率较低的字符将对应较短的编码。编码规则是自底向上，从根节点到叶子节点，遇到左孩子向左移动，遇到右孩子向右移动。例如，字符A可能的编码是0，字符C可能是10，G可能是11。 4. **代码实现**: 提供的代码片段展示了Huffman树相关的数据结构定义，如`TreeNode`和`Weight`结构体，以及`CreateHuffman`函数的初步定义，其中包括动态内存分配。这部分代码的核心是通过循环迭代构建哈夫曼树的节点，但实际编码的生成并未完成，因为这部分通常需要递归处理以生成完整的编码表。 总结起来，岭南师范学院这次的算法设计与分析作业四主要考察了学生对Huffman编码的理解、构建过程以及其在数据压缩中的应用。学生们需要实现Huffman树的构造算法，理解如何根据字符频率分配编码，以及熟练运用数据结构来管理这个过程。此外，他们还需要了解如何在实际编程中处理动态内存分配和递归调用。