文档介绍：第5章数组和广义表
数组是一种人们非常熟悉的数据结构,几乎所有的程序设计语言都支持这种数据结构或将这种数据结构设定为语言的固有类型。数组这种数据结构可以看成是线性表的推广。
科学计算中涉及到大量的矩阵问题,在程序设计语言中一般都采用数组来存储,被描述成一个二维数组。但当矩阵规模很大且具有特殊结构(对角矩阵、三角矩阵、对称矩阵、稀疏矩阵等),为减少程序的时间和空间需求,采用自定义的描述方式。
广义表是另一种推广形式的线性表,是一种灵活的数据结构,在许多方面有广泛的应用。
数组的定义
数组是一组偶对(下标值,数据元素值)的集合。在数组中,对于一组有意义的下标,都存在一个与其对应的值。一维数组对应着一个下标值,二维数组对应着两个下标值,如此类推。
数组是由n(n>1)个具有相同数据类型的数据元素a1,a2,…,an组成的有序序列,且该序列必须存储在一块地址连续的存储单元中。
◆数组中的数据元素具有相同数据类型。
◆数组是一种随机存取结构,给定一组下标,就可以访问与其对应的数据元素。
◆数组中的数据元素个数是固定的。
数组的抽象数据类型定义
1 抽象数据类型定义
ADT Array{
数据对象:ji= 0,1,…,bi-1 , 1,2, …,n ;
D = { aj1j2…jn | n>0称为数组的维数,bi是数组第i维的长度,ji是数组元素第i维的下标,aj1j2…jn∈ElemSet }
数据关系:R = {R1, R2, …, Rn}
Ri={<aj1j2 …ji…jn , aj1j2 …ji+1…jn>|0≦jk≦bk-1 , 1≦k≦n且k≠i,0≦ji≦bi-2, aj1j2 …ji+1…jn∈D }
基本操作: ……
} ADT Array
由上述定义知,n维数组中有b1b2 … bn个数据元素,每个数据元素都受到n维关系的约束。
2 直观的n维数组
以二维数组为例讨论。将二维数组看成是一个定长的线性表,其每个元素又是一个定长的线性表。
设二维数组A=(aij)mn,则
A=(α1,α2,…,αp) (p=m或n)
其中每个数据元素αj是一个列向量(线性表) :
αj =(a1j ,a2j ,…,amj) 1≦j≦n
或是一个行向量:
αi =(ai1 ,ai2 ,…,ain) 1≦i≦m
如图5-1所示。
a11 a12 … a1n
a21 a22 … a2n
……………
am1 am2 … amn
A=
……………
A=
a11 a12 … a1n
a21 a22 … a2n
am1 am2 … amn
a11
a21
┆
am1
a12
a22
┆
am2
a1n
a2n
┆
amn
┆
┆
┆
A=
图5-1 二维数组图例形式
(a) 矩阵表示形式
(b) 列向量的一维数组形式
(c) 行向量的一维数组形式
数组的顺序表示和实现
数组一般不做插入和删除操作,也就是说,数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化。因此,一般都是采用顺序存储的方法来表示数组。
问题:计算机的内存结构是一维(线性)地址结构,对于多维数组,将其存放(映射)到内存一维结构时,有个次序约定问题。即必须按某种次序将数组元素排成一列序列,然后将这个线性序列存放到内存中。
二维数组是最简单的多维数组,以此为例说明多维数组存放(映射)到内存一维结构时的次序约定问题。
通常有两种顺序存储方式
⑴行优先顺序(Row Major Order) :将数组元素按行排列,第i+1个行向量紧接在第i个行向量后面。对二维数组,按行优先顺序存储的线性序列为:
a11,a12,…,a1n, a21,a22,…a2n ,……, am1,am2,…,amn
PASCAL、C是按行优先顺序存储的,如图5-2(b)示。
⑵列优先顺序(Column Major Order) :将数组元素按列向量排列,第j+1个列向量紧接在第j个列向量之后,对二维数组,按列优先顺序存储的线性序列为:
a11,a21,…,am1, a12,a22,…am2, ……, an1,an2,…,anm
FORTRAN是按列优先顺序存储的,如图5-2(c)。
图5-2 二维数组及其顺序存储图例形式
a11 a12 … a1n
a21 a22 … a2n
……………
am1 am2 … amn
A=
(a) 二维数组的表示形式
(b) 行优先顺序存储
(c) 列优先顺序存储
a11
a12
…
a1n
第
1
行
a21
a22
…
a2n
第
2
行
am1
am2
…
Amn
第
m
行
┆
┆
…