二维数组

二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。

数组的顺序存储方式

由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。

数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。

(1) 行优先顺序
将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。
例: 二维数组Amn的按行优先存储的线性序列为：
a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn

注意：
PASCAL和C语言中，数组按行优先顺序存储。

行优先顺序推广到多维数组，可规定为先排最右的下标。

(2) 列优先顺序

将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。

例: 二维数组Amn的按列优先存储的线性序列为：
a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn

注意：
FORTRAN语言中，数组按列优先顺序存储。
列优先顺序推广到多维数组，可规定为先排最左的下标。

数组元素的地址计算公式

(1) 按行优先顺序存储的二维数组Amn地址计算公式
LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d

其中：
LOC(a11)是开始结点的存放地址（即基地址）
d为每个元素所占的存储单元数 由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。

(2) 按列优先顺序存储的二维数组Amn地址计算公式
LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d

(3) 按行优先顺序存储的三维数组Amnp地址计算公式
LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d

(4) 下界不为1的二维数组的地址计算公式
二维数组A[c1..d1,c2..d2]的地址计算公式:
LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d
下界为0的二维数组的地址计算公式(C语言中使用):
LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d

数组读取

for (j=0;j<N;j++)

  for (i=0;i<M;i++)

    A[i][j] = B[i][j] + C[i][j]

可优化为

for (i=0;i<M;i++)

  for (j=0;j<N;j++)

    A[i][j] = B[i][j] + C[i][j]

数组按行存储。前者按列读取，后者按行读取。后者可make use of the CPU cache.

对称矩阵 (symmetric array)

对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。

三角矩阵

以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。

上三角矩阵

下三角(不包括主角线)中的元素均为常数c。

下三角矩阵

与上三角矩阵相反，它的主对角线上方均为常数c。

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个。

稀疏矩阵 (sparse array)

设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即s << m x n)，则称A为稀疏矩阵。

为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
其中每一个非零元素所在的行号、列号和值组成一个三元组(i,j,aij)，并由此三元组惟一确定。

稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。