数组与广义表：数据结构的线性扩展与存储计算

本章节主要探讨了地址计算在数据结构中的应用，特别是在数组和广义表这两种数据结构中。首先，从二维数组和三维数组的存储角度出发，我们了解到： 1. **二维数组**：假设数组 Am×n 每个元素占用 L 个字节，元素 ai,j 的存储地址计算依赖于其所在行和列的位置。ai,j 的地址由基础元素 a00 的地址加上 i 行乘以 n 列再加上 j 个元素占用的空间得出，即：`LOC(aij) = LOC(a00) + (i * n + j) * L`。这种存储方式体现了数组作为线性结构的扩展特性。 2. **三维数组**：三维数组按低下标优先存放时，地址计算更为复杂，但基本原理类似，`LOC(aijk) = LOC(a000) + (i * n * p + j * p + k) * L`，展示了数组维度增加后的地址计算规则。 3. **矩阵的压缩存储**：教学重点之一是矩阵的压缩存储，特别是针对特殊矩阵（如稀疏矩阵）的处理，通过减少非零元素的存储来节省空间，这对于处理大量稀疏数据非常重要。稀疏矩阵通常只存储非零元素及其对应的坐标，而非全矩阵的复制。 4. **数组和广义表的定义与特性**：数组被视为一种线性结构的扩展，其中数据元素自身可以看作是另一个数据结构。一维数组是基础，它的存储地址可以通过简单的公式计算得出，因此是随机存储结构。二维数组则是线性关系的二维扩展，可以看作是多个行向量或列向量的组合。多维数组进一步拓展了这个概念，数据元素可能有多达三个直接前驱和后继。 5. **广义表**：虽然没有具体展开，但广义表作为数据结构的一种，定义了一个更灵活的数据结构，不同于一维数组的简单顺序存储，广义表可能包含其他数据结构作为元素，其存储结构更为复杂，可能涉及到链接存储。 总结来说，这一章节深入探讨了地址计算在数组和广义表的存储策略中，以及如何根据数组的维度扩展进行有效存储，同时提到了矩阵压缩存储对于处理效率的提升。理解这些概念有助于对高级数据结构有更深的理解，并在实际编程和算法设计中做出高效的选择。