数据结构第五章-数组和广义表要点.ppt

3、广义表 F=((((a),b)),((( ),(d)),(e,f))) 画出其图形表示及存储结构。 4、广义表 G=(((a,b,( )),( ),(a,(b))),( )) 画出其图形表示及存储结构。 思考题： 5、假设有二维数组elemtype a[6][8] ; 每个数 据元素占6个字节,存储器按字节编址。a的基地址 为1000,则： (1) 数组a的体积； (2)数组a的最后一个元素的第一个字节的地址； (3)按行存储时，a[2,4]的第一个字节的地址； (4)按列存储时，a[2,4]的第一个字节的地址； 思考题： 1 1 1 1 1 1 0 f 0 e 0 b 0 a 1 1 1 1 0 d 1 1 1 3、F 1 1 1 1 1 1 1 1 0 a 0 a 0 b 1 1 1 0 b 4、 第五章内容到此结束… 数组的类型定义 ADT Array { 数据对象： D＝{aj1,j2, ...,,jn| ji =0,...,bi -1, i=1,2,..,n } 数据关系： 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,j+1| 0≤i≤b1-1, 0≤ j≤b2-2} COL = {ai,j,ai+1,j | 0≤i≤b1-2, 0≤j≤b2-1} 基本操作： InitArray(A, n, bound1, ..., boundn) DestroyArray(A) Value(A, e, index1, ..., indexn) Assign(A, e, index1, ..., indexn) InitArray(A, n, bound1, ..., boundn) 操作结果：若维数 n 和各维长度合法， 则构造相应的数组A，并 返回OK。 DestroyArray(A) 操作结果：销毁数组A。 Value(A, e, index1, ..., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。 Assign(A, e, index1, ..., indexn) 初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。 与线性表一样，数组的数据对象是同一数据类型的数据元素的集合。 每个数据元素都对应于一组下标（j1,j2, ...,,jn），下标的个数n即表示数组的维数（即n维数组。如n=1时为一维数组（实际上就是一个定长的线性表），n=2时为二维数组等等），每个下标有一个取值范围： 0 = ji =bi -1, bi称为第i维的长度。 n维数组中的数据元素个数：b1Xb2X…Xbn 数据关系：R＝{R1, R2, ...,