【数据结构】数组的顺序存储(1、2、3、n维数组的元素地址计算）|保姆级详解+图解
数组是一种特殊的的数据结构，在存储结构是顺序存储（一个连着一个），所有只要给定数组的维度，和各维度的长度，数组中元素个数就是确定的。且给出首元素的地址，例如根据A[i][j][k]，的i、j、k就可以计算出该元素的地址（或与首元素的地址之差）在计算机中，内存储器的结构是一维的。对于一维数组，可以直接按照顺序直接存储对于常见的二维数组，通常采用两种方式实现物理结构上的一维顺序存储行优先：一行一行的存
文章共5,023字 · 阅读需要大约17分钟
👩🎓一、前言
数组是一种特殊的的数据结构，在存储结构是顺序存储（一个连着一个），所有只要给定数组的维度，和各维度的长度，数组中元素个数就是确定的。且给出首元素的地址，例如根据A[i][j][k]，的i、j、k就可以计算出该元素的地址（或与首元素的地址之差）
在计算机中，内存储器的结构是一维的。
- 对于一维数组，可以直接按照顺序直接存储
- 对于常见的二维数组，通常采用两种方式实现物理结构上的一维顺序存储
- 行优先：一行一行的存储，存完一行，再在这一行尾元素后面接着存储下一行
- 列优先、
- 三维数组：三维数组元素的下标号由三个数字组成：即行、列、纵 3个方向
下面的图片是以行为主序的方法存放
🥕总之，知道了多维数组的维度、每维度的上下限，就可以把多维数组的元素按照一维的顺序存储，存储在计算机中。
同样，根据数组的下标，可以计算出其在计算机中的位置（地址），这是重点和难点。
下面我将分别从
- 一维数组的地址计算
- 二维数组的地址计算
- 三维数组的地址计算
3个方面来详细讲解
🍊二、一维数组的地址计算
一维数组的本质其实就是线性表，它的存储非常简单
假设一维数组的元素为：(我们假设A数组下标从1开始）
A = a 1 , a 2 , a 3 , a 4... a i A = a1,a2,a3,a4 ... ai A=a1,a2,a3,a4...ai
假设每个元素占用size个字节（存储单元），那么ai的存储地址为：首元素地址 + （该元素和首元素相差元素个数）× size
图形结合来理解（黄色的箭头就是地址（指针
🥕 ai的存储地址计算公式
L o c ( A [ i ] ) = L o c ( A [ 1 ] ) + ( i − 1 ) × s i z e Loc(A[i]) = Loc(A[1]) + (i-1)×size Loc(A[i])=Loc(A[1])+(i−1)×size
🍊三、二维数组的地址计算
二维数组分行优先和列优先，原理都是一样的。这里我们按照行优先，A数组下标从（1，1）开始
假设每个元素占用size个字节（存储单元），那么A[i][j]的存储地址为：首元素地址 + （该元素和首元素相差元素个数）× size
这个
i-1和j-1的减去这个1，代表的起使分别是起使元素下标A[1][1]中的两个1
i - 1表示相差的行数，× 一行元素个数，表示i这一行之前所差的所有元素个数j-1表示的是只考虑i这一行，A[i][j]所相差元素个数理解了这个，当A数组首元素下标从（0，0）开始，可以很轻松的写出相应的公式了！
🥕 A[i][j]的存储地址计算公式（行优先）
L o c ( A [ i ] [ j ] ) = L o c ( A [ 1 ] [ 1 ] ) + ( n ( i − 1 ) + j − 1 ) × s i z e Loc(A[i][j]) = Loc(A[1][1]) + (n(i-1) + j -1)×size Loc(A[i][j])=Loc(A[1][1])+(n(i−1)+j−1)×size
🍊四、三维数组的地址计算
关于三维数组的理解方式，我是这样理解的：
- 看成二维数组，行还是表示二维数组的行，列还是表示二维数组的列
- 但是原来二维数组中的一个元素，这里是一纵元素
- 按行优先存储，依旧还是存完一行的元素，再存储下一行。但是注意，由于这个特殊的二维数组，它的元素是一个一维数组，所以在每一行依次存储每一个元素时，比如必须从前往后把这个元素（即一维数组遍历完！)存好，再存储下一个！
所以对于三维数组：
A
[
1..
r
]
[
1..
m
]
[
1..
n
]
A[1..r][1..m][1..n]
A[1..r][1..m][1..n]
假定每个元素占size个存储单位，并且按照行优先（就是我假设的那个把三维数组看成一个二维数组的那个行，体现在三维数组中，起使就是m*n的平面，每次r+1其实就跳过了m*n这个平面中这么多元素！）
🥕理解&推导（行优先）
首元素的地址为Loc(A[1][1][1])
- 对于
A[i][1][1]的地址，因为该元素前面有i-1个m*n的平面的元素，所以
L o c ( A [ i ] [ 1 ] [ 1 ] ) = L o c ( A [ 1 ] [ 1 ] [ 1 ] ) + ( ( i − 1 ) × m × n ) × s i z e Loc(A[i][1][1]) = Loc(A[1][1][1]) + ( (i-1)×m×n)×size Loc(A[i][1][1])=Loc(A[1][1][1])+((i−1)×m×n)×size - 对于
A[i][j][1]的地址,则在上面元素个数（(i-1)×m×n）基础上，再加j-1个“元素”，上面我说道，三维数组看作二维数组，一个元素，可以看作是长度为纵维度长度，即n的一个一维数组；所以需要加上(j-1)×n - 所以
A[i][j][k]就在上面两个答案累加的基础上加上该元素所在纵维度的没有算的k-1个元素即可
🥕 A[i][j][k]的存储地址计算公式（行优先）
L o c ( A [ i ] [ j ] [ k ] ) = L o c ( A [ 1 ] [ 1 ] [ 1 ] ) + ( ( i − 1 ) × m × n + ( j − 1 ) × n + k − 1 ) × s i z e Loc(A[i][j][k]) = Loc(A[1][1][1]) + ( (i-1)×m×n+(j-1)×n + k-1)×size Loc(A[i][j][k])=Loc(A[1][1][1])+((i−1)×m×n+(j−1)×n+k−1)×size
🍊五、n维数组的地址计算
对于n维度数组
A [ c 1.. d 1 , c 2.. d 2 , c 3.. d 3 , . . . , c n . . d n ] A[c1..d1,c2..d2,c3..d3,...,cn..dn] A[c1..d1,c2..d2,c3..d3,...,cn..dn]
🥕 A[j1][j2]...[jn]的存储地址计算公式（行优先）
L o c ( A [ j 1 ] [ j 2 ] . . . [ j n ] ) = L o c ( A [ c 1 ] [ c 2 ] . . . [ c n ] ) + ∑ i = 1 n a i × ( j i − c i ) Loc(A[j1][j2]...[jn]) = Loc(A[c1][c2]...[cn]) +\sum\limits_{i=1}^{n}ai×(ji-ci) Loc(A[j1][j2]...[jn])=Loc(A[c1][c2]...[cn])+i=1∑nai×(ji−ci)
其中：
a
i
=
s
i
z
e
×
∏
k
=
i
+
1
n
(
d
k
−
c
k
+
1
)
,
1
<
=
i
<
=
n
ai = size×\prod\limits_{k=i+1}^{n}(dk-ck+1),1<=i<=n
ai=size×k=i+1∏n(dk−ck+1),1<=i<=n
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
44
0- 0
已为社区贡献4条内容
所有评论(0)