数组与广义表详解：定义、特点及特殊矩阵压缩存储

"本章介绍了数组和广义表的相关概念，包括数组的定义、特点、二维数组的存储方式，以及特殊矩阵如对称矩阵的压缩存储。此外，还提到了广义表的定义和示例，包括递归广义表的表示。" 在数据结构中，数组是一种基础且重要的数据组织形式。数组被定义为由n个相同类型的数据元素组成的一个有限序列，这些元素存储在连续的内存空间内，形成一种顺序存储结构。数组的一个关键特性是，其元素可以通过索引来随机访问，索引计算公式通常为Loc(ai)=Loc(a0)+i*k，其中k表示每个元素占据的内存大小。 二维数组是数组的扩展，可以视为由多个一维数组组成。在计算机内存中，二维数组可以按照行主序或列主序存储。行主序时，元素的位置遵循Loc(aij)=Loc(a00)+(i×n+j)×k的规则；而列主序则将每一列视为一个整体，按照列的顺序存储。 对于特定类型的矩阵，如对称矩阵，由于其元素的对称性，可以只存储非对角线以下或以上的元素，从而节省存储空间。例如，一个对称矩阵只需要n(n+1)/2个元素的空间就能完全表示。这种存储方法称为压缩存储，尤其适用于元素稀疏的矩阵，如对称矩阵、三角矩阵或稀疏矩阵。 接下来，我们转向广义表的概念。广义表是一种更通用的数据结构，它可以包含任意类型的元素，包括其他广义表。例如，广义表A为空，B为一个有两个元素的列表，C是一个有两个元素的列表，其中一个元素是另一个包含三个元素的列表，D是一个包含三个子表的列表，E是一个递归的广义表，其第二个元素是自身。广义表的图形表示有助于理解其结构，特别是对于递归情况。 数组和广义表是数据结构的基础，它们在算法设计和实现中扮演着重要角色。数组提供了高效且直接的元素访问，而广义表则能灵活地表达复杂的数据关系。了解并熟练掌握这两种数据结构及其操作，对于理解和解决各种计算问题至关重要。