多维数组的存储
数组是相同类型数据元素的有序集合,各元素在内存中按下标线性排列。多维数组在内存中按行优先或列优先方式展开成一维存储。
一维数组
一维数组 A[0..n−1] 的起始地址为 LOC(a0),每个元素占 L 个存储单元,则:
LOC(ai)=LOC(a0)+i×L
二维数组(行优先)
设二维数组 A[m][n](m 行 n 列),行优先存储时,元素 A[i][j] 的地址为:
LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×L
推导:行优先时,第 i 行之前共有 i×n 个元素,第 i 行第 j 列之前还有 j 个元素,故偏移量为 i×n+j。
二维数组(列优先)
列优先存储时,元素 A[i][j] 的地址为:
LOC(A[i][j])=LOC(A[0][0])+(j×m+i)×L
推导:第 j 列之前共有 j×m 个元素,第 j 列第 i 行之前还有 i 个元素,故偏移量为 j×m+i。
行优先和列优先的地址计算公式极易混淆。关键记住:行优先先数”行”,列优先先数”列”。408 考题常给出行优先公式,要求换算出某元素的地址,务必看清题意。
习题
习题 1
二维数组 A[0..4][0..5] 按行优先存储,每个元素占 2 个存储单元,A[0][0] 的地址为 1000,则 A[3][4] 的地址是( )
A. 1034
B. 1040
C. 1044
D. 1048
多维数组行优先存储地址计算
解题思路:
本题考查二维数组按行优先存储时的元素地址计算。先由下标范围确定数组的行列数,再按行优先规则写出偏移量公式,最后把首地址与元素长度代入公式算出目标地址。
详细步骤:
- 由 A[0..4][0..5] 确定该数组为 5 行 6 列,故列数 n=6。
- 行优先存储时元素 A[i][j] 的偏移量为 i×n+j,代入 i=3、j=4、n=6,得偏移 =3×6+4=22。
- 每个元素占 2 个存储单元,故地址 =LOC(A[0][0])+22×2=1000+44=1044。
最终答案:
C(1044)。
习题 2
多维数组在内存中的存储方式是什么?如何计算元素地址?
多维数组行优先存储列优先存储地址计算
解题思路:
本题考查多维数组的两种线性存储方式及其地址公式。答题时先说明多维数组在内存中只能展平成一维序列存放,再分别写出行优先与列优先的地址计算公式,并解释公式中各符号的含义。
详细步骤:
- 说明多维数组在内存中按行优先或列优先的方式线性展开存储。
- 写出行优先公式 LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×L:第 i 行之前有 i×n 个元素,第 i 行第 j 列之前还有 j 个元素。
- 写出列优先公式 LOC(A[i][j])=LOC(A[0][0])+(j×m+i)×L:第 j 列之前有 j×m 个元素,第 j 列第 i 行之前还有 i 个元素。
- 说明公式中 m、n 分别为行数与列数,L 为一个元素所占的存储单元长度。
最终答案:
多维数组按行优先或列优先线性展开存储。行优先时 LOC(A[i][j])=LOC(A[0][0])+(i×n+j)×L;列优先时 LOC(A[i][j])=LOC(A[0][0])+(j×m+i)×L。其中 m、n 分别为行数、列数,L 为元素大小。