4-4（1）数组

数组：按一定格式排列起来的具有相同类型的数据元素的集合

• 一维数组：若线性表中的数据元素为非结构的简单元素，则称为一维数组

  一维数组的逻辑结构：线性结构，定长的线性表

  声明格式：数据类型 变量名称[长度]

  int num[5] = {0, 1, 2, 3, 4};
  

• 二维数组：若一维数组中的数据元素又是一维数组，则称为二维数组

  

  二维数组的逻辑结构：

  1. 非线性结构：每一个数据元素既在一个行表中，又在一个列表中
  2. 线性结构：该线性表的每个数据元素也是一个定长的线性表

  声明格式：数据类型 变量名称[行数][列数];

  int num[5][8]; //声明一个5行8列的二维数组
  

• n维数组：若n-1维数组中元素又是一个一维数组结构，则称为n维数组

结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展

数组特点：结构固定—定义后，维数和维界不再改变

数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素的操作

4-4（2）数组的抽象数据类型定义

n维数组的抽象数据类型

ADT Array {
	数据对象：ji=0,...,bi-1, i=1,2,...,n
					 D={aj1,j2,...,jn|aj1j2jn∈ElemSet}
	数据关系：R1={<aj1,...,ji,...,jn, aj1,...,ji+1,...,jn>|0<=jk<=bk-1, 1<=1<=n, 且k!=i, 0<=ji<=bi-2, aj1...ji...jn, i=2,...,n}
	基本操作：
		(1)InitArray(&A, n, bound1,...,boundn) //构造数组A
		(2)DestroyArray(&A) //销毁数组A
		(3)Value(A, &e, index1,...,indexn) //取数组元素值
		(4)Assign(A, &e, index1,...,indexn) //给数组元素赋值
}ADT Array

例：二维数组的数据关系

n=2（维数为2，二维数组）

$b_1：第一维长度（行数） b_2：第二维长度（列数）$

$a_{{j_1}{j_2}}：第一维下标为j_1，第二维下标为j_2$

4-4（3）数组的顺序存储

数组的特点：结构固定—维数和维界不变

数组的基本操作：一般不做插入和删除操作（用赋值操作）

所以： 一般都是采用顺序存储结构来表示数组

注意：数组可以是多维的，但存储数据元素的内存单元地址是一维的。因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题

例：有数组定义int a[5]

每个元素占用四个字节，假设a[0]存储在2000单元，a[3]地址是多少？

答：$a[3]=3\times4+2000=2012$

LOC(i)=

1. LOC(0)=a i=0
2. LOC(i-1)+L=a+i*L i>0

二维数组：

两种顺序存储方式：

1. 以行序为主序（C、Java、BASIC）
2. 以列序为主序（FORTAN）

以行序为主序：设数组开始存储位置LOC(0,0)，存储每个元素需要L个存储单元。

数组元素a[i][j]的存储位置是：$LOC(i,j)=LOC(0,0)+(i*n+j)*L$