北邮数据结构实验3：哈夫曼编码实现与分析

本实验报告主要涉及的是北邮数据结构课程中的实验3——哈夫曼编码，该实验旨在让学生熟悉和实践赫夫曼编码算法及其在实际应用中的构建过程。哈夫曼编码是一种用于数据压缩的无损编码方法，它通过对频率较高的字符分配较短的编码，而对频率较低的字符分配较长的编码，从而实现数据的高效压缩。 实验要求包括六个部分： 1. 初始化 (Init)：这个阶段的核心是统计输入字符串中各字符的频率，通过一个`struct node`结构体来存储字符及其出现次数。首先，读取输入文本，将其存储在数组`str1`中，然后遍历数组，计算每个字符的出现次数并存入`struct node`的`num`和`data`字段。 2. 建立编码表 (CreateTable)：使用赫夫曼树（Huffman Tree）的构建算法，根据字符频率从小到大依次组合成新的节点，形成一棵带权重的二叉树。通过递归的方式创建和连接节点，直到所有字符都有对应的分支。最后，根据树的结构生成编码表`HCodeTable`，其中`struct HCode`包含字符和对应的编码。 3. 编码 (Encoding)：根据编码表中的编码规则，对输入字符串进行替换，将字符替换为其对应的编码，得到压缩后的字符串。 4. 译码 (Decoding)：与编码相反，利用已有的Huffman树，根据编码表反向查找，将压缩后的编码还原为原始字符序列。 5. 打印 (Print)：可选环节，直观地展示Huffman树，有助于理解和学习树的结构，以及编码过程。 6. 压缩效果分析：比较编码前后的字符串长度，计算压缩比，讨论赫夫曼编码的压缩性能。这一步可以直观地显示了算法在减少数据存储空间方面的优势。 在实现过程中，涉及到的数据结构有三叉树节点（`struct HNode`）和编码表节点（`struct HCode`），它们分别存储字符信息、权值、子节点指针以及编码等内容。关键算法方面，初始化阶段采用伪代码形式，展示了如何通过统计和构建Huffman树来实现字符频率的计数和编码表的生成。 总结来说，这个实验不仅要求学生掌握哈夫曼编码的基本原理，还锻炼了他们用C/C++等编程语言实现数据结构的能力，以及对算法的理解和运用。通过本实验，学生将加深对动态数据结构和无损数据压缩技术的理解。