[数据结构基础]使用顺序存储方式存储多维数组时特定元素存储地址的计算方法

前言

本文将分析并给出将一维数组、二维数组和三维数组使用顺序存储方式存储时确定给定的某个数组元素在内存中的存储地址的计算方法，以作参考。

正文

在本文中，我们约定：

(1) 所有数组中元素的下标【默认】都是从 $1$ 开始计算，而不是从 $0$ 开始计算，即一维数组的第一个元素为 $A_{1}$, 二维数组的第一个元素为 $A_{11}$, 三维数组的第一个元素为 $A_{111}$.

(2) 每个元素都占据相同的存储空间，这个存储空间的大小为 $L$.

一维数组

一维数组本质上就是以顺序存储方式存储的线性表，如图 1 所示：

假设一维数组中每个元素占 $L$ 个存储单元，则元素 $A_{i}$ 的存储位置为：

$$
LOC[A_{i}] = LOC[A_{1}] + (i – l) \times L.
$$

二维数组

二维数组有两种存储方式，分别是按行优先存储（行主序）和按列优先存储（列主序）。

行主序的存储方式如图 2 所示：

假设这个二维数组有 $m$ 行 $n$ 列，则在以行主序的方式顺序存储的情况下，元素 $A_{ij}$ 的存储位置为：

$$
LOC[A_{ij}] = LOC[A_{11}] + [n \times (i – 1) + (j-1)] \times L.
$$

上面的公式可以理解为：

先把元素 $A_{ij}$ 所在的第 $i$ 行前面的 $i-1$ 行的元素个数算出来，为：$n \times (i-1)$, 再加上元素 $A_{ij}$ 所在的行前面的 $j-1$ 个元素。这样就得到了元素 $A_{ij}$ 前面的（不包括元素 $A_{ij}$ 但包括元素 $A_{11}$）所有元素的个数，于是 $[n \times (i – 1) + (j-1)] \times L$ 就是元素 $A_{ij}$ 前面的所有元素所占据的存储空间的大小。事实上，$[n \times (i – 1) + (j-1)] \times L$ 表示的是元素 $A_{(i-1)(j-1)}$ 的地址，因此，再加上元素 $A_{11}$ 所占据的存储空间之后，$LOC[A_{11}] + [n \times (i – 1) + (j-1)] \times L$ 表示的就是元素 $A_{ij}$ 的地址。

列主序的存储方式如图 3 所示：

假设这个二维数组有 $m$ 行 $n$ 列，则在以列主序的方式顺序存储的情况下，元素 $A_{ij}$ 的存储位置为：

$$
LOC[A_{ij}] = LOC[A_{11}] + [m \times (j-1) + (i-1)] \times L.
$$

对于使用列主序方式存储的 $m$ 行 $n$ 列的二维数组 $A_{mn}$, 我们只需要将其看作是以行主序方式存储的 $n$ 行 $m$ 列的二维数组 $A_{nm}$ 即可使用前面的行主序地址计算公式计算：把 $n$ 换成 $m$, 把 $i$ 换成 $j$, 把 $j$ 换成 $i$ 即可。

三维数组

假设有三维数组 $A_{r \times m \times n}$, 每个元素占 $L$ 个存储单元，则元素 $A_{ijk}$ 的存储地址为：

$$
LOC[A_{ijk}] = LOC[A_{111}] + [(i-1) \times m \times n + (j-1) \times n + (k-1)] \times L.
$$

其中，$(j-1) \times n + (k-1)$ 为元素 $A_{ijk}$ 所在“第 $i$ 层”中位于元素 $A_{ijk}$ 前面的元素个数（此时可按二维数组理解），$(i-1) \times m \times n$ 为元素 $A_{ijk}$ 所在的“第 $i$ 层”上面的 $i-1$ 层所含元素的个数。

EOF