多维数组与广义表:数据结构的扩展与存储实现

需积分: 32 1 下载量 184 浏览量 更新于2024-08-22 收藏 700KB PPT 举报
在"多维数组-数据结构(清华大学版)——数组和广义表"这一章节中,主要探讨了数组和广义表这两种重要的数据结构。数组被定义为具有固定大小和维度的有序集合,其中元素按照一定的顺序存储在内存中。一维数组是最基础的形式,它由一系列相同类型的数据元素组成,存储在连续的内存空间,通过索引直接访问,如公式Loc(ai) = Loc(a0) + i*L所示,表明一维数组是随机存储结构。 二维数组是对一维数组的扩展,它是按行和列组织的数据,每个元素都有两个坐标,形成一对下标,表示为m行n列。二维数组可以视为由行向量和列向量构成,既可以看作是m个行向量组成的向量,也可以视为n个列向量组成的向量。在三维及以上数组(即多维数组)中,除了边界,每个数据元素最多有三个直接前驱和三个直接后继,这种结构是非线性的,因为它允许更多的直接邻接关系。 教学重点之一是矩阵的压缩存储,包括特殊矩阵(如对角矩阵、稀疏矩阵等)的处理,以及广义表的定义和存储结构。广义表作为一种非线性数据结构,其数据元素本身也是一个数据结构,这使得它在逻辑结构上扩展了线性数据的特性。尽管数组和广义表在逻辑上都可以看作线性结构的扩展,但它们的数据元素性质不同,数组元素是基本的原子数据,而广义表元素则可能包含子结构。 本章内容旨在深入理解数组和广义表的内部构造、存储方式和适用场景,强调了它们在数据结构中的核心地位,并通过实例演示了如何高效地利用这些数据结构进行数据操作和管理。这对于理解和设计高效的算法以及解决实际问题具有重要意义。