数组与广义表：逻辑结构与存储实现

"本资料主要讲解了数组和广义表这两种数据结构，内容包括数组的定义、表示和实现，特别关注了矩阵的压缩存储，以及广义表的定义与存储结构。教学重点在于理解矩阵的压缩存储技术。资料覆盖了一维、二维及多维数组的概念，强调了数组作为随机存取结构的特性，并介绍了广义表这一更复杂的数据结构。" 在计算机科学中，数组是一种基础且重要的数据结构，它允许我们以有序的方式存储和访问数据。在清华大学版的数据结构课程中，数组被详细阐述，包括其性质和不同维度的表现形式。 1. **数组的性质**： - **固定数量的数据元素**：数组在创建时就指定了大小，一旦定义，其元素数量不会改变。 - **相同数据类型**：数组的所有元素都具有相同的类型，确保了数据的一致性。 - **唯一下标**：每个元素都有一个唯一的下标来标识其位置，使得访问变得直接。 - **随机存取**：由于下标的特性，可以快速访问数组中的任何元素，无需遍历。 2. **一维数组**：一维数组是线性数据结构的特例，可以视为一个有限的元素序列，所有元素存储在连续的内存空间中。通过下标i和元素占用的存储单位数L，可以计算出任一元素的地址，实现了随机存取。 3. **二维数组**：二维数组是将一维数组扩展到二维空间，可以看作是由行向量和列向量组成的。每个元素由一对下标标识，分别对应行和列，这使得在行和列方向上都可以找到直接前驱和后继元素。 4. **多维数组**：进一步扩展，三维及以上数组被称为多维数组，其中的数据元素可能有多个直接前驱和后继。这种结构在处理复杂问题时非常有用，如图像处理中的像素矩阵。 5. **矩阵的压缩存储**：在处理特殊矩阵（如对角矩阵、三角矩阵）或稀疏矩阵（大部分元素为零）时，为了节省存储空间，会采用压缩存储技术。例如，对于稀疏矩阵，只存储非零元素及其对应的行和列索引，显著减少了存储需求。 6. **广义表的定义与存储结构**：广义表是比数组更灵活的数据结构，它的数据元素可以是其他数据结构，如列表或数组。广义表的存储通常采用链式结构，便于处理嵌套和异构数据。 这些概念是理解高级数据结构和算法的基础，对编程和软件开发至关重要。学习这些内容有助于提升解决复杂问题的能力，特别是在处理大量数据和优化算法效率时。