第 四 章 数组和广义表
4, 1 数组的顺序存储结构
4.1.1 数组的定义
几乎在所有的高级算法语言中,都有数组类型数据的定义,
数组是线性表的推广,本节仅以二维数组为例,给出数组的定义
?
?
?
?
?
?
?
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
A
??
?????
??
??
21
22211
11211 左式是大家所熟悉的矩阵,即 二维数组
一个二维数组的逻辑结构可形式地表为,
),(_2 RDA r r ay ?,其中,
? ?0222111 ;,,1,;,,1,DadccjdcciaD ijij ?????? ??
? ?colro wR,?
? ?01,22111,,,1,,Daadjcdicaar o w jiijjiij ????????? ??
? ?0,12211,1,,,1,Daadjcdicaac ol jiijjiij ????????? ??
为某个数据对象,均为整数,
0D 2121,,,ddcc
由上述定义可见,
1)二维数组含有 )1()1(
2211 ????? cdcd
个数据元素 ;
2)每个数据元素
ija
均受两个关系 row(行 关系 )col(列 关系 )的
约束 ;
3)
1,?jia
是
ija
在 行 关系中的直接后继元素,
jia,1?
是
ija
在 列 关系中的直接后继元素 ;
4)数组中所有数据元素必须同属一种数据类型 ;
5)数组中每个数据元素对应于一组下标 ),( ji,且 ),(
11 dc和
),( 22 dc 分别是下标 i 和 j 的一对界偶 (即下确界和
上确界 ).
二维数组可看成是线性表的推广,从这一意义出发,也可如
下定义二维数组,
把二维数组看成是它的每个数据元素是一个线性表的线性
表,
对于 可看成一个线性表,即
nmA ?
)(),,,( 21 normpA p ?? ??? ?
其中每个数据元素
j?
是一个列向量的线性表
njaaa mjjjj ??? 1),,,( 21 ??
即
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mn
n
n
mj
j
j
m
nm
a
a
a
a
a
a
a
a
a
A
?
?
?
?
?
2
1
2
1
1
21
11 或者
i?
是一个行向量
的线性表
miaaa iniii ??? 1),,,( 21 ??
即
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
),,,(
),,,(
),,,(
21
21
11211
mnmm
inii
n
nm
aaa
aaa
aaa
A
?
?
?
?
?
4.1.2 数组的顺序存储结构
数组的一个特点是,其结构中的 数据元素个数和元素
之间的关系一旦建立就不再变动,因此 数组一般不作插入
和删除操作, 适宜于用顺序存储结构表示数组,
对于计算机来说,不管是外存储器还是内存储器,其
存储单元是一维结构,而数组是个多维结构, 因此用一组
地址连续的存储单元存放数组的 数据元素就有个次序约定
问题, 一个二维 数组,既可看成是列向量的一维数组,也
可看成是行向量的一维数组,与此相对应,对 二维 数组来
说,可有两种顺序存储方式,
(1) 以行序为主序 (按行优先 )的存储方式,其存储的物理
状态可见教材 P.75图 4.1(b),假设 二维 数组中每个 数据元
素占用 L个 存储单元,第 1c 行第 2c 列元素所占 L个 存储单元
的第一个 单元的地址叫基地址,用 ],[ 21 ccLO C 表示,
则,二维数组中任一数据元素所占 L个 存储单元 的第一个 单
元的地址可用下式计算,
? ? ? ? ? ? LcjcicdccL O CjiL O C ???????? )())(1(,,212221
(2) 以列序为主序 (按列优先 )的存储方式,其存储的物理
状态可见教材 P.75图 4.1(c),假设 二维 数组中每个 数据元
素占用 L个 存储单元,第 1c 行第 2c 列元素所占 L个 存储单元
的第一个 单元的地址叫基地址,用 ],[ 21 ccLO C 表示,则,二维
数组中任一数据元素所占 L个 存储单元 的第一个 单元的地址
可用下式计算,
? ? ? ? ? ? LcicjcdccL O CjiL O C ???????? )())(1(,,121121
4, 1 数组的顺序存储结构
4.1.1 数组的定义
几乎在所有的高级算法语言中,都有数组类型数据的定义,
数组是线性表的推广,本节仅以二维数组为例,给出数组的定义
?
?
?
?
?
?
?
?
?
?
?
?
?
mnmm
n
n
aaa
aaa
aaa
A
??
?????
??
??
21
22211
11211 左式是大家所熟悉的矩阵,即 二维数组
一个二维数组的逻辑结构可形式地表为,
),(_2 RDA r r ay ?,其中,
? ?0222111 ;,,1,;,,1,DadccjdcciaD ijij ?????? ??
? ?colro wR,?
? ?01,22111,,,1,,Daadjcdicaar o w jiijjiij ????????? ??
? ?0,12211,1,,,1,Daadjcdicaac ol jiijjiij ????????? ??
为某个数据对象,均为整数,
0D 2121,,,ddcc
由上述定义可见,
1)二维数组含有 )1()1(
2211 ????? cdcd
个数据元素 ;
2)每个数据元素
ija
均受两个关系 row(行 关系 )col(列 关系 )的
约束 ;
3)
1,?jia
是
ija
在 行 关系中的直接后继元素,
jia,1?
是
ija
在 列 关系中的直接后继元素 ;
4)数组中所有数据元素必须同属一种数据类型 ;
5)数组中每个数据元素对应于一组下标 ),( ji,且 ),(
11 dc和
),( 22 dc 分别是下标 i 和 j 的一对界偶 (即下确界和
上确界 ).
二维数组可看成是线性表的推广,从这一意义出发,也可如
下定义二维数组,
把二维数组看成是它的每个数据元素是一个线性表的线性
表,
对于 可看成一个线性表,即
nmA ?
)(),,,( 21 normpA p ?? ??? ?
其中每个数据元素
j?
是一个列向量的线性表
njaaa mjjjj ??? 1),,,( 21 ??
即
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mn
n
n
mj
j
j
m
nm
a
a
a
a
a
a
a
a
a
A
?
?
?
?
?
2
1
2
1
1
21
11 或者
i?
是一个行向量
的线性表
miaaa iniii ??? 1),,,( 21 ??
即
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
),,,(
),,,(
),,,(
21
21
11211
mnmm
inii
n
nm
aaa
aaa
aaa
A
?
?
?
?
?
4.1.2 数组的顺序存储结构
数组的一个特点是,其结构中的 数据元素个数和元素
之间的关系一旦建立就不再变动,因此 数组一般不作插入
和删除操作, 适宜于用顺序存储结构表示数组,
对于计算机来说,不管是外存储器还是内存储器,其
存储单元是一维结构,而数组是个多维结构, 因此用一组
地址连续的存储单元存放数组的 数据元素就有个次序约定
问题, 一个二维 数组,既可看成是列向量的一维数组,也
可看成是行向量的一维数组,与此相对应,对 二维 数组来
说,可有两种顺序存储方式,
(1) 以行序为主序 (按行优先 )的存储方式,其存储的物理
状态可见教材 P.75图 4.1(b),假设 二维 数组中每个 数据元
素占用 L个 存储单元,第 1c 行第 2c 列元素所占 L个 存储单元
的第一个 单元的地址叫基地址,用 ],[ 21 ccLO C 表示,
则,二维数组中任一数据元素所占 L个 存储单元 的第一个 单
元的地址可用下式计算,
? ? ? ? ? ? LcjcicdccL O CjiL O C ???????? )())(1(,,212221
(2) 以列序为主序 (按列优先 )的存储方式,其存储的物理
状态可见教材 P.75图 4.1(c),假设 二维 数组中每个 数据元
素占用 L个 存储单元,第 1c 行第 2c 列元素所占 L个 存储单元
的第一个 单元的地址叫基地址,用 ],[ 21 ccLO C 表示,则,二维
数组中任一数据元素所占 L个 存储单元 的第一个 单元的地址
可用下式计算,
? ? ? ? ? ? LcicjcdccL O CjiL O C ???????? )())(1(,,121121
