《数据结构》课程教学资源：第四章 数组和广义表

第四章数组和广义表 4.1数组的顺序存储结构 411数组的定义 几乎在所有的高级算法语言中,都有数组类型数据的定义 数组是线性表的推广,本节仅以二维数组为例,给出数组的定义 左式是大家所熟悉的矩阵,即二维数组 12 个二维数组的逻辑结构可形式地表为: A nan2_Aay=(D,R),其中 D={2=c+14…=c2c2+1…d;a∈D} ml am」R={om,co rO=a,a1m>≤i≤d1,c2≤j≤d2-1,an,a col=(an,an,1≤1≤d-1c2≤j≤d1,a,am∈D}

第 四 章 数组和广义表 4 . 1 数组的顺序存储结构 4.1.1 数组的定义 几乎在所有的高级算法语言中, 都有数组类型数据的定义. 数组是线性表的推广, 本节仅以二维数组为例, 给出数组的定义             = m m m n n n a a a a a a a a a A        1 2 1 1 2 2 2 1 1 1 2 1 左式是大家所熟悉的矩阵, 即二维数组 一个二维数组的逻辑结构可形式地表为: 2_ Array = (D,R) ,其中: D = ai j i = c1 ,c1 +1,  ,d1 ; j = c2 ,c2 +1,  ,d2 ;ai j D0  R = row,col row =  ai j ,ai, j+1  c1  i  d1 ,c2  j  d2 −1,ai j ,ai, j+1 D0  col =  ai j ,ai+1, j  c1  i  d1 −1,c2  j  d2 ,ai j ,ai+1, j D0 

D为某个数据对象,C,C2,41,d2均为整数 由上述定义可见 )二维数组含有(d1-c1+1)·(d2-c2+1)个数据元素; 2)每个数据元素均受两个关系row(行关系)co(列关系)的 约束; 3)a1+是a在行关系中的直接后继元素, 是在列关系中的直接后继元素 4)数组中所有数据元素必须同属一种数据类型; 5)数组中每个数据元素对应于一组下标(,j),且(C121) 和(C2,d2)分别是下标i和j的一对界偶(即下确界和 上确界). 二维数组可看成是线性表的推广,从这一意义出发,也可如 下定义二维数组: 把二维数组看成是它的每个数据元素是一个线性表的线性 表

为某个数据对象, 均为整数. D0 1 2 1 2 c ,c ,d ,d 由上述定义可见: 1)二维数组含有 ( 1) ( 1) d1 − c1 + • d2 − c2 + 个数据元素; 2)每个数据元素 aij 均受两个关系row(行关系)col(列关系)的 约束; 3) ai, j+1 是 aij 在行关系中的直接后继元素, ai+1, j 是 aij 在列关系中的直接后继元素; 4)数组中所有数据元素必须同属一种数据类型; 5)数组中每个数据元素对应于一组下标 (i, j) ,且 ( , ) c1 d1 和 ( , ) c2 d2 分别是下标 i 和 j 的一对界偶(即下确界和 上确界). 二维数组可看成是线性表的推广,从这一意义出发,也可如 下定义二维数组: 把二维数组看成是它的每个数据元素是一个线性表的线性 表

对于A,可看成一个线性表,即 A=(a, a,, ,a,)(p=m or n) 其中每个数据元素a是一个列向量的线性表 )1≤j≤n 或者a1是一个行向量 的线性表 C i1212 2 )1≤i≤m n×n C,,.C 115012nl nXn 123° m23 2 mn

对于 A mn 可看成一个线性表, 即 ( , , , ) ( ) 1 2 A p m or n =     p = 其中每个数据元素  j 是一个列向量的线性表 a a a j n  j = ( 1 j , 2 j ,  , mj) 1  即                                                      = m n n n mj j j m m n a a a a a a a a a A      2 1 2 1 1 2 1 1 1 或者  i 是一个行向量 的线性表 i = (ai1 ,ai2 ,  ,ai n ) 1 i  m 即                  = ( , , , ) ( , , , ) ( , , , ) 1 2 1 2 1 1 1 2 1 m m mn i i i n n m n a a a a a a a a a A     

412数组的顺序存储结构 数组的一个特点是,其结构中的数据元素个数和元素 之间的关系一旦建立就不再变动,因此数组一般不作插入 和删除操作.适宜于用顺序存储结构表示数组 对于计算机来说,不管是外存储器还是内存储器,其 存储单元是一维结构,而数组是个多维结构.因此用一组 地址连续的存储单元存放数组的数据元素就有个次序约定 问题.一个二维数组,既可看成是列向量的一维数组,也 可看成是行向量的一维数组,与此相对应,对二维数组来 说,可有两种顺序存储方式: (1)以行序为主序(按行优先)的存储方式,其存储的物理 状态可见教材P75图41(b假设二维数组中每个数据元 素占用L个存储单元,第G行第C2列元素所占L个存储单元 的第一个单元的地址叫基地址,用 LOLO12c2]表示

4.1.2 数组的顺序存储结构 数组的一个特点是, 其结构中的数据元素个数和元素 之间的关系一旦建立就不再变动, 因此数组一般不作插入 和删除操作. 适宜于用顺序存储结构表示数组. 对于计算机来说, 不管是外存储器还是内存储器, 其 存储单元是一维结构, 而数组是个多维结构. 因此用一组 地址连续的存储单元存放数组的数据元素就有个次序约定 问题. 一个二维数组, 既可看成是列向量的一维数组, 也 可看成是行向量的一维数组, 与此相对应, 对二维数组来 说, 可有两种顺序存储方式: (1) 以行序为主序(按行优先)的存储方式, 其存储的物理 状态可见教材P.75图4.1(b). 假设二维数组中每个数据元 素占用L个存储单元, 第 1 c 行第 2 c 列元素所占L个存储单元 的第一个单元的地址叫基地址, 用 [ , ] 1 2 LOC c c 表示

则,二维数组中任一数据元素所占L个存储单元的第一个单 元的地址可用下式计算 LOC[,小=LOC[c,c2]+[(d2-c2+1)i-c)+(-c2)×L (2)以列序为主序(按列优先)的存储方式,其存储的物理 状态可见教材P75图41(c).假设二维数组中每个数据元 素占用L个存储单元,第C行第C2列元素所占L个存储单元 的第一个单元的地址叫基地址,用 LOCO1,C2表示,则,二维 数组中任一数据元素所占L个存储单元的第一个单元的地址 可用下式计算: LOC[i,小=LOC[c;c]+(a-c+1j-c2)+(i-c1)×L

则,二维数组中任一数据元素所占L个存储单元的第一个单 元的地址可用下式计算: LOCi, j= LOCc1 ,c2 + (d2 − c2 +1)(i − c1 ) + ( j − c2 ) L (2) 以列序为主序(按列优先)的存储方式, 其存储的物理 状态可见教材P.75图4.1(c). 假设二维数组中每个数据元 素占用L个存储单元, 第 1 c 行第 2 c 列元素所占L个存储单元 的第一个单元的地址叫基地址, 用 [ , ] 1 2 LOC c c 表示,则,二维 数组中任一数据元素所占L个存储单元的第一个单元的地址 可用下式计算: LOCi, j= LOCc1 ,c2 + (d1 − c1 +1)( j − c2 ) + (i − c1 ) L