串、数组和广义表.ppt

进阶任务（每任务200经验值） 什么叫广义表？它和线性表有和相同和不同之处？ 什么是广义表的表头、表尾、表长、表深？ P91~92选择题，综合应用题(1)(3)(4)(5)。 广义表LS = ( ?1, ?2, ???, ?n )是递归定义的线性结构， 其中：?i 或为原子 或为广义表。而在线性表中?i只能为原子。 当广义表LS = ( ?1, ?2, ???, ?n )非空，第一个元素?1称为表头，剩余元素(?2, ???, ?n )组成的子表称为表尾。 长度为最外层包含元素个数。深度为所含括弧的重数。 * 本节所讨论的数组与高级语言中的数组区别： 　高级语言中的数组是顺序结构； 　而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。 4.2 数组 * 数组的抽象数据类型 数据对象: 数据关系: ADT Array { * 基本操作: (1) InitArray (A,n,bound1, ?boundn) //构造数组A (2) DestroyArray (A) // 销毁数组A (3) Value(A,e,index1,…,indexn) //取数组元素值 (4) Assign (A,e,index1,…,indexn) //给数组元素赋值 }ADT Array * 一维数组 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 l l l l l l l l l l LOC(i) = LOC(i-1)+l = a+i*l LOC(i) = LOC(i-1)+l = a+i*l, i 0 a, i = 0 a+i*l a * 二维数组 * 以行序为主序 C, PASCAL 数组的顺序存储 * 以列序为主序 FORTRAN *  a[n][m] 设数组开始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k 二维数组的行序优先表示 * 设有二维数组A[10,20]，其每个元素占两个字节， A[0][0]存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为 ，按列优先顺序存储，元素A[6,6]的存储地址为 。 课堂任务（经验值200） 352 232 (6*20+6)*2+100=352 (6*10+6)*2+100=232 * 设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 设数组元素A[i][j]存放在起始地址为Loc ( i, j ) 的存储单元中 ∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = ( 676 - 2 - 644 ) / 2 = 15 ∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692. 课堂任务（经验值200） * 1. 什么是压缩存储？ 若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。 2. 什么样的矩阵能够压缩？ 一些值相同的元素或零元素在矩阵中分布有规律的特殊矩阵，如：对称矩阵，对角矩阵