多维数组的存储

数组

数组是相同类型数据元素的有序集合,各元素在内存中按下标线性排列。多维数组在内存中按行优先或列优先方式展开成一维存储。

一维数组

一维数组 A[0..n−1]A[0..n-1] 的起始地址为 LOC(a0)LOC(a_0),每个元素占 L 个存储单元,则:

LOC(ai)=LOC(a0)+i×LLOC(a_i) = LOC(a_0) + i \times L

二维数组(行优先)

设二维数组 A[m][n]A[m][n](m 行 n 列),行优先存储时,元素 A[i][j]A[i][j] 的地址为:

LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×LLOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times L

推导:行优先时,第 i 行之前共有 i×ni \times n 个元素,第 i 行第 j 列之前还有 j 个元素,故偏移量为 i×n+ji \times n + j。

二维数组(列优先)

列优先存储时,元素 A[i][j]A[i][j] 的地址为:

LOC(A[i][j])=LOC(A[0][0])+(j×m+i)×LLOC(A[i][j]) = LOC(A[0][0]) + (j \times m + i) \times L

推导:第 j 列之前共有 j×mj \times m 个元素,第 j 列第 i 行之前还有 i 个元素,故偏移量为 j×m+ij \times m + i。

习题

习题 1

二维数组 A[0..4][0..5] 按行优先存储,每个元素占 2 个存储单元,A[0][0] 的地址为 1000,则 A[3][4] 的地址是( )

A. 1034 B. 1040 C. 1044 D. 1048

多维数组行优先存储地址计算

解题思路:

本题考查二维数组按行优先存储时的元素地址计算。先由下标范围确定数组的行列数,再按行优先规则写出偏移量公式,最后把首地址与元素长度代入公式算出目标地址。

详细步骤:

  1. 由 A[0..4][0..5]A[0..4][0..5] 确定该数组为 5 行 6 列,故列数 n=6n = 6。
  2. 行优先存储时元素 A[i][j]A[i][j] 的偏移量为 i×n+ji \times n + j,代入 i=3i = 3、j=4j = 4、n=6n = 6,得偏移 =3×6+4=22= 3 \times 6 + 4 = 22。
  3. 每个元素占 2 个存储单元,故地址 =LOC(A[0][0])+22×2=1000+44=1044= LOC(A[0][0]) + 22 \times 2 = 1000 + 44 = 1044。

最终答案:

C(1044)。

习题 2

多维数组在内存中的存储方式是什么?如何计算元素地址?

多维数组行优先存储列优先存储地址计算

解题思路:

本题考查多维数组的两种线性存储方式及其地址公式。答题时先说明多维数组在内存中只能展平成一维序列存放,再分别写出行优先与列优先的地址计算公式,并解释公式中各符号的含义。

详细步骤:

  1. 说明多维数组在内存中按行优先或列优先的方式线性展开存储。
  2. 写出行优先公式 LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×LLOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times L:第 ii 行之前有 i×ni \times n 个元素,第 ii 行第 jj 列之前还有 jj 个元素。
  3. 写出列优先公式 LOC(A[i][j])=LOC(A[0][0])+(j×m+i)×LLOC(A[i][j]) = LOC(A[0][0]) + (j \times m + i) \times L:第 jj 列之前有 j×mj \times m 个元素,第 jj 列第 ii 行之前还有 ii 个元素。
  4. 说明公式中 mm、nn 分别为行数与列数,LL 为一个元素所占的存储单元长度。

最终答案:

多维数组按行优先或列优先线性展开存储。行优先时 LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×LLOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times L;列优先时 LOC(A[i][j])=LOC(A[0][0])+(j×m+i)×LLOC(A[i][j]) = LOC(A[0][0]) + (j \times m + i) \times L。其中 mm、nn 分别为行数、列数,LL 为元素大小。

发现内容有问题?

告诉我们哪里需要改进。