数组元素存储地址的计算(精选.)
- 格式:doc
- 大小:284.00 KB
- 文档页数:9
数组元素存储地址的计算 一维数组
设一维数组A[n]存放在n 个连续的存储单元中,每个数组元素占一个存储单元(不妨设为C 个连续字节). 如果数组元素A[0]的首地址是L ,则A[1]的首地址是L+C ,A[2]的首地址是L+2C ,… …,依次类推,对于01≤≤-i
n 有:
C i A Loc i A Loc *])0[(])[(+=
二维数组
二维数组的每个元素含两个下标,如果将二维数组的第一个下标理解为行号,第二个下标理解为列号,然后按行列次序排列个元素,则二维数组呈阵列形状。例如
mn
m m n
n a a a a a a a a a A 21
222
2111211=
它是一个行号为1~m ,列号为1~n 的二维数组元素阵列。 如何保存二维数组? 首先要确定一个顺序
222120
121110
020100a a a a a a a a a B = 222120
121110020100a a a a a a a a a B = 22
2120
121110
020100a a a a a a a a a B = 2221
20
12
11
10
02
01
00
a a a a a a a a a
第0行 第1行 第2行
222120
121110
020100a a a a a a a a a B = 2221
20
121110020100a
a a
a
a a a
a a B =
22
2120
121110
020100a a a a a a a a a B =
2212
02
21
11
01
20
10
00
a a a a a a a a a
第0列 第1列 第2列
222120
121110
020100a a a a a a a a a B = 221202a a a a a B = B =
B B 021*******
00
21
10
20
a a a a a a a a a
设count 为数组B 中元素的个数,则count=9 按行优先存储
按列优先存储
地址如何计算?
所谓按行优先顺序,就是将数组元素按行向量的顺序存储,第1
i
个行向量存储在第i个行向量之后。
下面我们计算二维数组A m n
[][]中任一元素A[i][j]的存储地址,设每个数组元素所占空间为C个连续字节。显然,A[i][j]是第i个行向量B[i]中的第j个元素。
在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
按列优先存储
地址如何计算?
在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,
可以把它看作一维数组
B 1[3] = { D[0][3][4],D[1][3][4],D[2][3][4] }
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[0][3][4]
i=0
D[1][3][4]
i=1
D[2][3][4]
i=2