第5章数组合广义表Part1.ppt

第五章 数组和广义表 主讲：戚玉涛 第5章 数组和广义表 5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.4 广义表 数组的ADT定义 二维数组的定义 数组是n(n＞1)个相同类型数据元素a0,a1,…,an-1构成的有限序列。 数组的定义类似于线性表，是线性表在维数上的扩张，也就是线性表中的元素又是一个线性表。一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组。 n维数组，bi是第i维的长度，则n维数组共有 个数据元素，每个元素受n个关系的制约，就单个关系而言，这n个关系仍然是线性的。 练习： 将一个A[1..100, 1..100]的三对角矩阵，按行优先存入一维数组B[1..298]，A中元素a66,65在B数组中的位置k=?。 在主对角线左下方，65*3-1+1 = 195。 作业： 5.2 5.25 * * ADT Array { 数据对象： D＝{aj1,j2, ..., ji, ...,jn| ji =0,...,bi -1, i=1,2,..,n } n：数组维数 bi：数组第i维的长度 数据关系： R＝{R1, R2, ..., Rn} Ri＝{aj1,... ji,... jn , aj1, ...ji +1, ...jn | 0 ? jk ? bk -1, 1 ? k ? n 且k ? i, 0 ? ji ? bi -2, i=2,...,n } 基本操作： } ADT Array 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } ROW = {ai,j,ai+1,j| 0≤i≤b1-2, 0≤j≤b2-1} COL = {ai,j,ai,j+1| 0≤i≤b1-1, 0≤ j≤b2-2} 可以把二维数组看成是一个定长的线性表：它的每一个数据元素也是一个定长的线性表 数组举例： 数组的定义和运算 数组具有以下性质： (1)数组中的数据元素数目固定。一旦定义了一个 数组,其数据元素数目不再有增减变化。 (2)数组中的数据元素具有相同的数据类型。 (3)数组中的每个数据元素都和一组唯一的下标值对 应。 (4)数组是一种随机存储结构。可随机存取数组中的 任意数据元素。 数组的基本操作 (1) InitArray(A, n, bound1, ..., boundn) (2) DestroyArray(A) (3) 取值 Value( A, e, index1,..., indexn) (4) 赋值Assign( A, e, index1,…, indexn) 数组一旦被确定，其维数和每一维的维界就不能再改变，因此数组除了初始化和销毁操作之外，只有“存取”和“修改”操作。数组一般不进行插入和删除操作。因此使用顺序存储结构表示数组成为自然的选择。 数组的顺序表示和实现 类型特点: 1) 只有引用型操作，没有加工型操作； 2) 数组是多维的结构，而存储空间是一个一维的结构。 有两种顺序映象的方式: 1) 以行序为主序(低下标优先)； 2) 以列序为主序(高下标优先)。 如何使用一维的结构表示多维的结构？ 数组的存储结构 一维数组中, LOC(a0)确定, 每个数据元素占用L个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出： LOC(ai)=LOC(a0)+i*L (0≤i≤n-1) 二维数组,由于计算机的存储结构是线性的,如何用线性的存储结构存放二维数组元素就有一个行／列次序排放问题。 以行序为主序 以列序为主序 两种顺序映象的方式 二维数组通常可以描述为两种形式 : 以行序为主序: PASCAL、C 可以看成 A = ( α0，α1， ，αm-1 ) . . . 其中αi 是一个行向量形式的线性表，0≤i≤m-1 αi = ( ai0，ai1， ，ai n-1 ) . . . a00 a01 a02 a0,n-1 a10 a11 a12 a1,n-1 am-1,0 am-1,1 am-1,2 am-1,n-1 . . . . . . . . . . . . . . . . . . . . .