第二讲数组

第二讲数组

数组已广泛应用于各种高级语言中，是我们比较熟悉的一种数据结构。从结构上看，它是线性表的推广。这一讲主要介绍数组的逻辑结构定义及存储方式，着重介绍特殊形式的数组--稀疏矩阵的存储结构及相应的运算。

1 数据的定义和运算

一维数组

A=[a₁,a₂,...,a_n]

二维数组

一般形式二维数组

数组结构具有三条性质：

数据元素数目固定，即一旦说明了一个数组结构，其元素数目不再有增减变化；
数据元素具有相同的类型；
数据元素的下标关系具有上下界的约束并且下标有序。

对于数组，通常只有以下两种运算：

给定一组下标，存取相应的数据元素；
给定一组下标，修改相应数据元素中的某个数据项的值。

2 数组的顺序存储结构

由于计算机的存储单元是一维结构，而数组是多维结构，要用一维的连续单元存放数组的元素，就有一个存放次序的约定问题。根据不同的存放形式可以分为：

（1）按行优先顺序存放

按行优先顺序存放就是按行切分，如上述二维数组A₂₃，按行切分可得

假设每个元素仅占一个存储单元，则元素a_ij的存储地址可以通过下面的关系式计算

Loc(a_ij)=Loc(a₁₁)+(i-1)´n+(j-1) (1 £ i £ m, 1 £ j £ n)

对应二维数组按行优先顺序存放，在三维数组中是以左下标为主序的存储方式。例对A_lmn，(设l=2, m=3, n=4)

元素a_ijk的存储地址可以通过下面的关系式计算

Loc(a_ijk)=Loc(a₁₁₁)+(i-1)´m´n+(j-1)´n+(k-1) (1 £ i £ l，1 £ j £ m, 1 £ k £ n)

在C、BASIC、COBOL和PASCAL等语言中，数组的实现采用按行优先的存储方式。利用存储地址、指针，可以提高数据访问的效率。

例，C语言中,一维数组时，
char str[80], *p1；
p1=str； /* 或 p1=&str[0] */
// 要访问第5个元素，则
str[4] 或
*(p1+4)

二维数组时，
int x[][2]={1, 1, 2, 4, 3, 9}
int *p1；
p1=&x[0][0]；
// 要访问a₃₂=9，则
x[2][1] 或
*(p1+5)

（2）按列优先顺序存放

如果数组按列切分，就得到按列优先顺序存放方式，仍以上述二维数组A₂₃为例，按列切分可得

假设每个元素仅占一个存储单元，则元素a_ij的存储地址可以通过下面的关系式计算

Loc(a_ij)=Loc(a₁₁)+(j-1)´m+(i-1) (1 £ i £ m, 1 £ j £ n)

对应二维数组按列优先顺序存放，在三维数组中是以右下标为主序的存储方式。例对A_lmn，(设l=2, m=3, n=4)

元素a_ijk的存储地址可以通过下面的关系式计算

Loc(a_ijk)=Loc(a₁₁₁)+(k-1)´l´m+(j-1)´l+(i-1) (1 £ i £ l，1 £ j £ m, 1 £ k £ n)

在FORTRAN语言中，数组采用按列优先的存储方式。

3 特殊矩阵的存储方式

上述两种数组的顺序存储方式，对于绝大部分元素值不为零的数组是合适的。但是，如果数组中有很多元素的值为零时，上述存储方式会造成大量存储单元的浪费。

（1）下三角阵的存储方式

设下三角阵数组A_nn为：

若将其中非零元素按行优先顺序存放为：

{a₁₁,a₂₁,a₂₂,a₃₁,a₃₂,...,a_n1,a_n2,...,a_nn}

从第1行至第i-1行的非零元素个数为：

求取其中非零元素aij地址的关系式为：

（2）三对角阵的存储方式

设A_nn为三对角阵：

若将其中非零元素按行优先顺序存放为：

{a₁₁,a₁₂,a₂₁,a₂₂,a₂₃,a₃₂,a₃₃,a₃₄,...,a_n,n-1,a_nn}

求取其中非零元素aij地址的关系式为：

Loc(a_ij)=Loc(a₁₁)+2(i-1)+(j-1) (i=1, j=1,2或i=n,j=n-1,n或1<i<n,j=i-1,i,i+1)

（3）对称矩阵的存储方式

类似三角阵的存储

4 稀疏矩阵

矩阵在科学计算中应用十分广泛，而且随着计算机应用的发展，大量出现处理高阶矩阵问题，有的甚至达到几十万阶、几千亿个元素，这就远远超过计算机的内存容量。然而，在大量的高阶问题中，绝大部分元素是零值。当非零元素所占比例£25% ～30%时，我们称这种含有大量零元素的矩阵为稀疏矩阵。压缩这种零元素占据的空间，不但能节省内存空间，而且能够避免大量零元素进行的无意义运算，大大提高运算效率。

4.1 顺序存储结构

(1)三元组表

线性表中的每个结点由三个字段组成，分别是该非零元素的行下标、列下标和值，按行优先顺序排列。为便于与教材比较，以下讨论矩阵下标均从0开始。

C语言下数据类型：

#define smax 16  ； /* 最大非零元素个数的常数 */
typedef int datatype；
typedef struct
{ int i, j；   /* 行号，列号 */
datatype v； /* 元素值 */
}node；
typedef struct
{ int m, n, t；     /* 行数，列数，非零元素个数 */
node data[smax]； /* 三元组表 */
} spmatrix；        /* 稀疏矩阵类型 */

例如稀疏矩阵A为　