# 数组

1. 定义

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作 “数据元素是一维数组” 的一维数组，三维数组可以看作 “数据元素是二维数组” 的一维数组，依此类推。

n 维数组可以看成是这样一个线性表，其中每个数据元素均是一个 n -1 维数组。

2. 特点

数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。

3. 储存方式

数组采用顺序存储结构，其主要操作是随机存取，即数据元素的定位，给定元素的下标，得到该元素在计算机中的存放位置。

给定数组下标求其数组元素在一维空间的位置
数组元素地址 = 基址 +(序号 - 1)*size

1) 行优先
定义：将数组元素按行向量排列，第 i+1 个行向量紧接在第 i 个行向量后面。
如：
a11 a12 … a1n , a21 a22 … a2n , … , am1 am2 … amn;
储存位置计算:
假设每个数据元素占 L 个存储单元，则按行序优先存储的数组 A 中任一元素 aij 的存储位置为：

LOC(aij)=LOC(a11)+[(i-1)*n+j-1 ]*L

LOC(aij)=LOC(a00)+[i*n+j]*L

//LOC (a11)、LOC (a00) 是开始结点的存放地址，即基地址；

2) 列优先
定义：将数组元素按列向量排列，第 i+1 个列向量紧接在第 i 个行向量后面。
如：
a11 a21 … am1 , a12 a22 … am2 , … ,a1n a2n … amn；
存储位置计算:
假设每个数据元素占 L 个存储单元，则按列序优先存储的数组 A 中任一元素 aij 的存储位置为：

LOC(aij)=LOC(a11)+[(j-1)*m+i-1 ]*L;

LOC(aij)=LOC(a00)+[j*m+i]*L;

// 其中，LOC (a11)、LOC (a00) 是开始结点的存放地址，即基地址。

3) 三维数组 Amnp 按行优先存储

LOC(aijk)=LOC(a000)+[i*n*p+j*p+k]*L

4) 四维数组 A [b1][b2][b3][b4] 按行优先存储

LOC(aijkm)=LOC(a0000)+[i*b2*b3*b4+j*b3*b4+k*b4+m]*L