数组与广义表：压缩存储与矩阵运算

"这篇资料主要讲述了数组和广义表的相关概念，特别是数组的顺序表示和压缩存储，以及在实际编程语言如C和FORTRAN中的实现方式。" 在计算机科学中，数组是一种基本的数据结构，它由相同类型的元素集合组成，这些元素可以通过一个或多个索引来访问。数组的定义通常是固定的大小，具有明确的上下界，便于处理和操作。在多维数组中，例如二维数组，可以视为由行向量或列向量组成的结构。在C语言中，二维数组的定义可以转换为一维数组的嵌套形式。 数组的顺序表示是将其元素按照一定的顺序排列成一维序列，以便在内存中存储。有两类常见的顺序存储方式：行优先顺序和列优先顺序。行优先顺序是将数组的每一行连续存储，例如，一个二维数组会先存储第一行的所有元素，然后是第二行，以此类推。这种方式在PASCAL和C语言中常见。相反，列优先顺序则是先存储所有列的第一个元素，然后是第二列，直到最后一列，这种方式在FORTRAN中常用。 特别地，对于某些特定类型的矩阵，如对称矩阵，可以使用压缩存储来节省空间。对称矩阵的下三角部分包含了全部信息，因为上三角部分与之对称。因此，只需存储下三角部分，通过下标关系可以计算出对角线以上部分的元素位置。在给定的例子中，公式`LOC(aij)`用于计算矩阵元素`aij`在压缩存储数组`sa`中的位置，这允许高效访问对称矩阵的元素。 此外，广义表（Generalized List）是一种更通用的数据结构，它可以包含不同类型的元素或者子列表。广义表的存储结构通常采用链式存储，因为它能灵活地表示嵌套和不同类型的元素。与数组不同，广义表支持插入和删除操作，因此更适合动态变化的数据集合。 数组和广义表是线性数据结构的特例，它们在不同的场景中各有优势。数组提供快速的随机访问，而广义表则提供了更丰富的表达能力和结构灵活性。了解并熟练掌握这两种数据结构及其在不同编程语言中的实现，对于理解和编写高效的算法至关重要。