数组与稀疏矩阵：二维数组定义及压缩存储

"这篇教学PPT主要讲解了二维数组的定义和稀疏矩阵的概念，以及在数组类型定义、顺序表示和实现方面的知识。" 在计算机科学中，数组是一种基础的数据结构，它允许我们以有序的方式存储和访问相同类型的数据元素。在本资料中，二维数组被详细地阐述。二维数组可以被视为一种表格形式的数据结构，由多个一维数组组成，通常用来模拟矩阵或表格。数据对象D被定义为{aij | 0≤i≤b1-1, 0 ≤j≤b2-1}，这意味着二维数组包含b1行和b2列，其中每行每列都有对应的元素aij。 数据关系部分，R被分为两部分：ROW和COL。ROW集合表示数组中同一列相邻元素之间的关系，即{i | <ai,j,ai+1,j>, 0≤i≤b1-2, 0≤j≤b2-1}，这表示数组中的每一行都是连续的。同样，COL集合表示数组中同一行相邻元素之间的关系，即{i | <ai,j,ai,j+1>, 0≤i≤b1-1, 0≤j≤b2-2}，意味着数组的每一列也是连续的。 接着，文档介绍了抽象数据类型（ADT）Array的基本操作，包括初始化数组（InitArray）、销毁数组（DestroyArray）、获取数组元素的值（Value）以及赋值操作（Assign）。这些操作对于理解和处理数组至关重要。例如，InitArray函数用于创建一个指定维度和边界大小的数组，而DestroyArray函数则负责释放数组占用的内存。Value和Assign函数分别用于读取和修改数组元素。 数组的顺序表示和实现部分，强调了数组在内存中实际上是以一维形式存储的。有两种常见的顺序映射方式，一种是以行优先（行序为主序），这意味着数组的元素按照行来填充内存。例如，二维数组中元素ai,j的位置可以通过基地址（LOC(0,0)）加上行偏移（b2 * i）和列偏移（j）来计算，公式为LOC(i,j)=LOC(0,0)+(b2×i＋j)×a0,1。这种存储方式方便按行访问数组，但不利于按列访问。 稀疏矩阵是另一种重要的概念，尤其当处理大量零元素的矩阵时。在稀疏矩阵的压缩存储中，只存储非零元素可以节省大量内存。这部分内容未在摘要中详细展开，但在实际应用中，如图形学、线性代数等领域，稀疏矩阵的压缩存储方法（如三元组存储、压缩行存储等）是非常关键的。 这份教学PPT提供了关于二维数组的基础知识，包括其定义、数据关系和在内存中的表示，同时引入了稀疏矩阵的概念，这些都是理解和处理多维数据的关键。