【数据结构】数组的顺序存储(1、2、3、n维数组的元素地址计算）|保姆级详解+图解

• 作者：努力学习的大一在校计算机专业学生，热爱学习和创作。目前在学习和分享：算法、数据结构、Java等相关知识。
• 博主主页： @是瑶瑶子啦
• 所属专栏: 【数据结构】：该专栏专注于数据结构知识，持续更新，每一篇内容优质，浅显易懂，不失深度！
• 近期目标：写好专栏的每一篇文章

目录

• 👩‍🎓一、前言
• 🍊二、一维数组的地址计算
• 🍊三、二维数组的地址计算
• 🍊四、三维数组的地址计算
• 🍊五、n维数组的地址计算

👩‍🎓一、前言

数组是一种特殊的的数据结构，在存储结构是顺序存储（一个连着一个），所有只要给定数组的维度，和各维度的长度，数组中元素个数就是确定的。且给出首元素的地址，例如根据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∑n​ai×(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

---

• Java岛冒险记【从小白到大佬之路】

• LeetCode每日一题–进击大厂
• 算法