文档介绍：数组的基本概念
稀疏矩阵的三元组存储
稀疏矩阵的十字链表存储
广义表
迷宫问题
第5章数组和广义表
返回主目录
第5章数组和广义表
数组的基本概念
数组的概念
数组是相同类型的数据有序的组合, 数组中的每一个数据通常称为数组元素, 数组元素用下标识别, 下标的个数取决于数组的维数。例如, 一个形式如式()的m*n阶矩阵是个二维数组, 其中的每个元素都可用下标变量aij来表示, i为元素的行下标, j为元素的列下标:
Am×n=
a11 a12 … a1n
a21 a22 … a2n
…………
am1 am2 … amn (1≤i≤m, 1≤j≤n)
类似于线性表, 一个二维数组的逻辑结构可定义为
2-Array=(D, R) ()
其中D={aij|i=c1, c1 +1, …, d1, j= c2, c2 +1, …d2, aij ∈D0}
R={ROW, COL}
ROW={<aij, ai, j+1>| c1 ≤i≤ d1, c2≤j≤ d2 -1, aij , ai, j+1∈D}
COL={<aij,ai+1, j>|c1≤i≤d1-1, c2≤j≤d2, aij, ai+1, j∈D} D0为某个数椐对象, c1, c2, d1, d2均为整数。
二维数组中含有(d1 - c1 +1)*(d2 - c2 +1)个数据元素, 每一个数据元素aij都受 ROW(行关系)和COL(列关系)的约束。ai, j+1是aij在行关系中的直接后继元素; 而ai+1, j是aij在列关系中的直接后继元素。
若将上述定义推广为n维数组, 可写出n 维数组的逻辑结构的定义如下:
n-Array=(D, R)
其中
D= a j1 j2 …jn ji =ci, c i+1, …, di, i=1, 2, …, n (n>0)
aj1j2…jn∈D0, 且ci和di均为整数
R={R1, R2, …, Rn}
Ri=<a j1 j2 ji … jn, a j1j2…(ji+1)…jn>ck≤jk≤dk, 1≤k≤n 且 k≠i
ci≤ji≤di-1
a j1 j2 ji … jn, a j1j2…(ji+1)…jn∈D
每个关系中,数据元素aj1j2 ji jn(ci≤ji≤d i-1)都有一个直接后继元素。因此,这n个关系中的任一关系, 就其单个关系而言, 仍是线性关系。如线性表一样,所有的数据元素都必须属于同一数据类型。
数组中的每个数据元素都对应于一组下标(j1, j2,…, jn), 每个下标的取值范围是c1 ≤ ji ≤di ,其中di-ci+1 称为第 i 维的长度(i=1,2,…,n)。
显然, 当n=1时, n 维数组就退化为定长的线性表。反之, n 维数组也可以看成是线性表的推广。由此可见, n维数组含有∏ni=1 (di-ci+1)个数据元素,每个数据元素都受着n个关系的约束,也可以从另一个角度来定义n维数组。
我们可以把二维数组看成是一个定长线性表, 该线性表的每一个元素也是一个定长线性表。例如, 图式()所示是一个二维数组, 以m 行n 列的矩阵形式表示。它可以看成一个线性表达式:
A=(a1, a2, …, ap ) (p = m或n)
其中每个数据元素 aj是一个列向量形式的线性表达式(参见式()):
aj=(a1j, a2j, …, amj) 1≤j≤n
或者每个数据元素ai 是一个行向量形式的线性表达式(参见式()):
ai=(ai1, ai2, …, ain) 1≤i≤m
a11 a12 a13… a1n
a21 a22 a23 … a2n
a31 a32 a11 … a3n
……………
am1 am2 am3… amn
Am×n=
在C语言中, 一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型, 也就是说
typedef ElemType Array2[m][n];
等价于
typedef ElemType Array1[n];
typedef Array1 Array2[m];
同理, 一个n 维数组类型可以定义为其数据元素为n-1 维数组类型的一维数组类型。
对数组一般讨论两种算法:
(1) 给定一组有定义的下标, 存取相应的数据元素;
(2) 给定一组有定义的下标, 修改相应数据元素中的某个或几个