1 / 12 栈、队列和多维数组§2.4 多维数组多维数组是一种常见的数据结构,本节讨论多维数组的逻辑结构、基本运算和存储结构,以及特殊矩阵和稀疏矩阵的压缩存储方法。一、多维组的逻辑结构和运算设有二维数组 A:array[1..m,1..n] of elementype; ┌ a 11 a 12⋯ a 1n ┐│ a 21 a 22⋯ a 2n │A=│ a 21 a 22⋯ a 2n ││ a⋯ a ⋯⋯ a ⋯ │└ a m1 a m2⋯ a mn ┘ 它可看成是由 m个行向量或者 n 个列向量组成的线性表。 也就是说,二维数组可以看成是这样一种推广的线性表,这种线性表的每一个数据元素本身也是一个线性表。对于上述二维数组A,我们可以将 A看成是下述线性表A'=(d 1,d 2, ⋯,d n) 其中每一个数据元素dj 本身也是一个线性表dj =(d 1j ,d 2j , ⋯,d mj) 1 ≤j ≤n。该线性表是二维数组A的第 j 个列向量。同样,也可将二维数组A看成线性表 A"=( β 1, β 2, ⋯, β m), 其中每个 β i 本身也是一个线性表2 / 12 β =( αi1 , αi2 , ⋯, αin ) 1 ≤j ≤m, β i 是二维数组 A 的第 i个行向量。类似地,一个三维数组可以看成是数据元素为二维数组的线性表。一般地,一个 n 维数组可视为其数据元素为n-1 维数组的线性表。二维数组中每个元素aij 均属于两个向量:第i 行的行向量和第j列的列向量。因此,除边界外,每个元素aij 都恰好有两个直接前趋和直接后继:行向量上的直接前趋aij-1 和直接后继 aij+1 ,列向量上的直接前趋 ai-1j 和直接后继 ai+1j 。并且有且仅有一个开始结点a11,它没有直接前趋;有且仅有一个终端结点amn,它没有直接后继。另外,边界上的结点 ( 开始结点和终端结点除外) 只有一个直接前趋或者只有一个直接后继。即除开始结点 a11外,第一行和第一列上的结点: a1j (j=2,...,n),ai1 (i=2,...,m)都只有一个直接前趋;除终端结点amn外,第 m行和第 n列上的结点 amj(j=1,...,n-1),ain(i=1,...,m-1)都只有一个直接后继。同样,三维数组Amnp中的每个元素 aijk 都属于三个向量,每个元素最多可以有三个直接前趋除和三个直接后继。依次类推, m维数组 An1n2...nm 每个元素 ai1i2...im都属于 m个向量, 最多可以有 m个直接前趋除和m个直接后继。数组通常只有两种基本运算——读和写。①读:给定一组下标,读取相应的数据元素。②写:给定一组下标,修改相应的数据元素。值得注意...