数组与线性表的推广——数组与广义表存储结构解析

"数组类型与存储结构-第5章 数组与广义表" 在计算机科学中，数组是一种基础且重要的数据结构，它允许我们存储和处理大量具有相同数据类型的数据。数组通常被视为线性表的推广，尤其当数组的元素本身也是线性表时，如二维数组、三维数组等。数组的结构是有序的，每个元素通过一对或多对下标进行唯一标识。 在二维数组中，我们可以将每一行看作是一个线性表，记为αi = (ai1, ai2, ..., ai,n)，其中i表示行索引，而每列也可以视为一个线性表，记为βj = (a1j, a2j, ..., amj)T，这里的T表示转置，j表示列索引。这种排列方式使得数组不仅在行方向上扩展，也在列方向上扩展，进一步体现线性表的特性。 数组的存储结构通常是连续的，这意味着数组的所有元素在内存中占据连续的空间。对于二维数组，数据通常按照行优先或列优先的方式存储。行优先存储方式意味着先存储第一行的所有元素，然后是第二行，以此类推；而列优先则是先存储第一列，再存储第二列，如此这般。这两种方式影响了数组元素的地址计算。 数组的一个显著特点是其固定大小和不可变的下界。一旦数组在程序中被定义，它的大小和每个维度的上下界就固定不变，这意味着我们不能在数组中间插入或删除元素。我们只能通过给定的下标访问、读取或修改数组中的元素。例如，操作包括获取元素的值（Value）和设置元素的值（Assign）。 对于更高维度的数组，如三维或四维数组，它们的抽象数据类型（ADT）定义会包括更多的下标，每个维度的长度也相应增加。在内存中，这些高维数组同样可以被视作一系列一维数组的嵌套，每个一维数组代表一个特定维度的切片。 数组的存储效率高，访问速度快，因为可以通过简单的数学公式直接计算出元素的内存地址。然而，这也导致了数组在动态调整大小方面的局限性。当需要处理稀疏矩阵（大部分元素为零的矩阵）或广义表（可以包含子表的数据结构）时，通常会采用特殊的压缩存储方法来节省空间，例如链式存储或使用三元组表示法。 在本章中，我们将深入探讨二维数组的存储结构和地址变换，了解如何在内存中有效地表示和操作数组。还将讨论特殊矩阵的压缩存储，如稀疏矩阵的存储结构与算法，以及广义表的存储结构和算法。这些内容对于理解数据结构的基本原理和优化算法设计至关重要。