武汉理工大哈夫曼树实验：构建256叶二叉树与编码流程

在武汉理工大学数据结构与算法综合实验中，学生们被要求利用哈夫曼树进行字节重复次数的压缩。实验的核心目标是构建一颗有256个叶子节点的哈夫曼树，其中每个节点代表一种不同的字节，重复次数作为权值。这个过程涉及以下几个关键步骤： 1. **数据预处理**： 首先，统计256种不同字节的重复次数，用整型数组weight[]存储这些信息。这一步骤通过遍历输入文件计算各个字节出现的频率。 2. **二叉树存储结构**： 实验采用结构体来表示节点，例如`{int weight; int child;}`，并使用数组存储所有节点，采用静态二叉链表的方式来组织树形结构。这有助于高效地插入和查找节点。 3. **Huffman编码**： Huffman编码是通过构造哈夫曼树实现的，每个节点的两个子节点对应一个'0'和一个'1'，从而形成编码规则。在这个过程中，创建HuffmanTree[]数组，通过选择最小权值的两个节点合并成一个新的节点，并更新其权重和子节点指针。 4. **核心算法设计**： - `creatHuffman`函数实现了哈夫曼树的生成，通过不断选择最小权值的节点进行合并，直到只剩下一个根节点（即哈夫曼树）。这个过程通常采用优先队列（如最小堆）来辅助操作。 - `HuffmanCoding`函数则负责根据生成的哈夫曼树进行编码。从最后一个非叶子节点开始，遍历树，每个节点的左子节点对应'0'，右子节点对应'1'，并将编码写入到bianma数组中。 5. **文件头和内存缓冲区**： 在压缩文件时，除了实际的数据，还需要保存原文件长度和256种字节的权值，这些信息用于解压缩。定义一个内存缓冲区pBuffer用于存储压缩后的数据，其大小取决于原始文件压缩后的结果。 6. **文件操作**： 压缩过程将数据按照Huffman编码规则写入缓冲区，而解压时则是根据相同的编码规则读取缓冲区中的数据并重构原始文件。文件头信息确保了正确解码。 整个实验不仅考察了学生对数据结构（尤其是二叉树和哈夫曼树）的理解，还涉及了算法设计（如优先队列和动态构建哈夫曼树），以及文件操作和数据压缩的基本原理。通过这个实验，学生能够提高他们的编程技能，理解如何在实际应用中使用算法优化数据存储和传输。