数组元素存储地址的计算

数组元素存储地址的计算 一维数组

设一维数组A[n]存放在n个连续的存储单元中，每个数组元素占一个存储单元（不妨设为C个连续字节）. 如果数组元素A[0]的首地址是L，则A[1]的首地址是L+C，A[2]的首地址是L+2C，… …，依次类推，对于0in1有：

Loc(A[i])Loc(A[0])i*C

二维数组

二维数组的每个元素含两个下标，如果将二维数组的第一个下标理解为行号，第二个下标理解为列号，然后按行列次序排列个元素，则二维数组呈阵列形状。例如

a11Aa21am1a12a22a1na2n

am2amn它是一个行号为1~m，列号为1~n的二维数组元素阵列。 如何保存二维数组？ 首先要确定一个顺序

a00Ba10a20a01a02a00a01a02a00a01a02a11a12 a21a22a11a12 Ba10a21a22a20a00a01a02a10a11a12 Ba10a21a22a20a11a12a20a21a22

第0行 第1行 第2行

文案

标准

a00Ba10a20

a01a02a00a01a02a00a01a02a11a12 a21a22a11a12 Ba10a21a22a20a00a10a20a01a11a12 Ba10a21a22a20a11a21a02a12a22

第0列 第1列 第2列

a00Ba10a20

a01a02a00a01a02a00a01a02a11a12 a21a22a11a12 Ba10a21a22a20a01a02a00a11a12 Ba10a21a22a20a01a02a11a12 a21a22a11

a00Ba10a20a11a12 Ba10a21a22a20a20a10a21a00a22a01a12a02

1 3 2 4 设count为数组B中元素的个数，则count=9 按行优先存储

… 1 2 3 4 5 6 7 8 9 … a00 a01 a02 a10 a11 a12 a20 a21 a22 第0行 第1行 第2行

文案

标准

按列优先存储

… 1 2 3 4 5 6 7 8 9 … a00 a10 a20 a01 a11 a21 a02 a12 a22 第0列 第1列 第2列

地址如何计算？

所谓按行优先顺序，就是将数组元素按行向量的顺序存储，第i1个行向量存储在第i个行向量之后。

下面我们计算二维数组A[m][n]中任一元素A[i][j]的存储地址，设每个数组元素所占空间为C个连续字节。显然，A[i][j]是第i个行向量B[i]中的第j个元素。

… 1 2 3 4 5 6 7 8 9 … a00 a01 a02 a10 a11 a12 a20 a21 a22 第0行 第1行 第2行

在A[i][j]之前的元素个数为u，分别是A[0][0]，A[0][1]，A[0][2]，…，A[0][n]，A[1][0]，A[1][1]，A[1][2]，…，A[1][n]，…，A[i-1][0]，A[i-1][1]，A[i-1][2]，…，A[i-1][n]，A[i][0]，A[i][1]，A[i][2]，…，A[i][j-1]

设每个数组元素所占空间为C个连续字节。 则

Loc（A[i][j]）=Loc（A[0][0]）+u*C u=?

文案

标准

前i行（第0行到第i-1行）（每行n个元素）的元素个数+第i行的元素个数（A[i][0]到A[i][j-1]）

因此，u=i*n+j 故

Loc（A[i][j]）=Loc（A[0][0]）+u*C

=Loc（A[0][0]）+（i*n+j）*C

按列优先存储

… 1 2 3 4 5 6 7 8 9 … a00 a10 a20 a01 a11 a21 a02 a12 a22 第0列 第1列 第2列

地址如何计算？

在A[i][j]之前的元素个数为v，分别是A[0][0]，A[1][0]，A[2][0]，…，A[m][0]，A[0][1]，A[1][1]，A[2][1]，…，A[m][1]，…，A[0][j-1]，A[1][j-1]，A[2][j-1]，…，A[m][j-1]，A[0][j]，A[1][j]，A[2][j]，…，A[i-1][j]

设每个数组元素所占空间为C个连续字节。 则

Loc（A[i][j]）=Loc（A[0][0]）+v*C v=?

前j列（第0列到第j-1列）（每列m个元素）的元素个数+第j列的元素个数（A[0][j]到A[i-1][j]）

因此，v=j*m+i

文案

标准

故

Loc（A[i][j]）=Loc（A[0][0]）+v*C

=Loc（A[0][0]）+（j*m+i）*C

高维数组

按行优先：“左”下标优先，即第一（最左）下标的下标值较小的元素较先存储，第一个下标值相同者，按第二下标优先存储，对任意的k>1，对第1~（k-1）维相同者，先存储第k维中下标值较小者。 按列优先：“右”下标优先（最后一维下标为最右），先存储第n维下标值较小者，第n维下标值相同者，先存储第n-1维下标值较小者。

三维数组D[3][3][4]的顺序存储次序是

元素表示为D[i][j][k] 其中，0≤i≤2，0≤j≤2，0≤k≤3，

可以把它看作一维数组

B1[3] = { D[0][3][4]，D[1][3][4]，D[2][3][4] }

D[0][3][4]

i=0

D[0][0][0]，D[0][0][1]，D[0][0][2]，D[0][0][3] D[0][1][0]，D[0][1][1]，D[0][1][2]，D[0][1][3] D[0][2][0]，D[0][2][1]，D[0][2][2]，D[0][2][3]

D[1][0][0]，D[1][0][1]，D[1][0][2]，D[1][0][3] D[1][1][0]，D[1][1][1]，D[1][1][2]，D[1][1][3] D[1][2][0]，D[1][2][1]，D[1][2][2]，D[1][2][3]

D[2][0][0]，D[2][0][1]，D[2][0][2]，D[2][0][3] D[2][1][0]，D[2][1][1]，D[2][1][2]，D[2][1][3] D[2][2][0]，D[2][2][1]，D[2][2][2]，D[2][2][3]

D[1][3][4]

i=1

D[2][3][4]

i=2

文案

标准

For x=0 to 2 do For y=0 to 2 do For z=0 to 3 do D[i][j][k]的地址：

Loc（D[i][j][k]）=Loc（D[0][0][0]）+w*C 第一个下标的变化：0到i-1，共i*3*4个元素

第一个下标为i时，第二个下标的变化：0到j-1，共j*4个元素 第一个下标为i，第二个下标为j时，第三个下标的变化：0到k-1，共k个元素 w= i*3*4+j*4+k

Loc（D[i][j][k]）=Loc（D[0][0][0]）+w*C

=Loc（D[0][0][0]）+（i*3*4+j*4+k）*C

For z=0 to 3 do For y=0 to 2 do For x=0 to 2 do

a00a10a20a01a11a21a02a12a22

文案

标准

D[3][3][0] k=0

D[3][3][1] k=1

D[3][3][2] k=2

D[3][3][3] k=3

D[0][0][0]，D[1][0][0]，D[2][0][0] D[0][1][0]，D[1][1][0]，D[2][1][0] D[0][2][0]，D[1][2][0]，D[2][2][0]

D[0][0][1]，D[1][0][1]，D[2][0][1] D[0][1][1]，D[1][1][1]，D[2][1][1] D[0][2][1]，D[1][2][1]，D[2][2][1]

D[0][0][2]，D[1][0][2]，D[2][0][2] D[0][1][2]，D[1][1][2]，D[2][1][2] D[0][2][2]，D[1][2][2]，D[2][2][2]

D[0][0][3]，D[1][0][3]，D[2][0][3] D[0][1][3]，D[1][1][3]，D[2][1][3] D[0][2][3]，D[1][2][3]，D[2][2][3]

j=0 j=1 j=2 j=0 j=1 j=2 j=0 j=1 j=2 j=0 j=1 j=2

For z=0 to 3 do For y=0 to 2 do For x=0 to 2 do D[i][j][k]的地址：

Loc（D[i][j][k]）=Loc（D[0][0][0]）+w*C 第三个下标的变化：0到k-1，共k*3*3个元素

第三个下标为k时，第二个下标的变化：0到j-1，共j*3个元素 第三个下标为k，第二个下标为j时，第一个下标的变化：0到i-1，共i个元素 w= k*3*3+j*3+i

Loc（D[i][j][k]）=Loc（D[0][0][0]）+w*C

=Loc（D[0][0][0]）+（k*3*3+j*3+i）*C

文案

标准

n维数组a[m1][m2][mn] For l1=0 to m11 do For l2=0 to m21 do

… … … …

For ln=0 to mn1 do

Loc(i1,i2,,in)Loc(0,0,,0)s*C

s = ?

l1的变化：0~i1-1，共i1*m2*m3*…*mn=i1*mp个元素

p2nl1等于i1时，l2的变化：0~i2-1，共i2*m3*…*mn=i2*mp个元素

p3nl3的变化：l2等于i2时，l1等于i1时，0~i3-1，共i3*m4*…*mn=i3*mpp4n个元素

… … … …

l1等于i1时，l2等于i2时，…，ln1等于in1时，ln的变化：0~in-1，

共in个元素 故

s=i1*mp+i2*mp+i3*mp+…+in1*mn+in

p2p3p4nnn( ik*mp)in

k1pk1n1nLoc(i1,i2,,in)Loc(0,0,,0)s*C

Loc(0,,0){( ik*mp)in}*C

k1pk1n1n文案