数据结构第五章讲义：数组、压缩存储与广义表

"《数据结构》第五章讲义主要涵盖了数组和广义表的基本概念、存储结构以及相关操作。这章的学习目标包括掌握数组的定义、运算和顺序存储结构，理解特殊矩阵的压缩存储和稀疏矩阵的三元组表示，以及如何在这些存储结构下进行矩阵运算。同时，还需要掌握广义表的定义、存储结构和基本操作，包括表头和表尾的分析方法。学习的重点是数组的行为主存储结构中地址的计算，矩阵压缩存储时的下标变换，三元组表示稀疏矩阵时的运算处理，以及广义表的定义和存储结构。难点在于三元组表示稀疏矩阵的运算处理和广义表的递归算法。" 在这章中，数组是一种基本的数据结构，它是由一组具有相同类型且下标不同的变量构成。数组的定义强调了元素的统一类型、固定的维数和边界，以及简单的操作，如初始化、销毁、存取和修改元素。一维数组通过单个下标访问，二维数组则引入了行和列的关系，而N维数组则有多个下标来定义其位置。 数组的顺序存储表示是将多维数组排列成一维序列，并存入计算机的一维存储空间中。这种存储方式简化了物理存储，但需要知道元素在内存中的位置，这通常通过数组的下标计算得出。例如，在行主序存储方式中，二维数组的元素按照行优先的顺序存放。 对于特殊矩阵，如稀疏矩阵，当非零元素较少时，为了节省存储空间，可以使用压缩存储，如三元组表示。在这种表示法中，只存储非零元素的行号、列号和值，这简化了矩阵运算，但需要处理下标变换以进行正确计算。 广义表是一种更灵活的数据结构，它可以包含不同类型的数据元素，甚至其他广义表。广义表的定义包含了头元素和尾元素的概念，它的存储结构可以是链式或线性的，取决于具体实现。广义表的操作可能涉及递归，特别是在处理包含子表的情况。 学习的难点在于理解和实现三元组表示的稀疏矩阵运算，这通常涉及复杂的下标映射和计算。另外，广义表的递归算法可能对初学者来说较为复杂，需要深入理解递归和数据结构之间的关系。 这一章内容要求学生不仅要有扎实的理论基础，还要具备一定的实践能力，能够实现和优化数据结构的存储和操作。通过深入学习，可以为后续的算法设计和复杂数据处理打下坚实的基础。