数据结构_数据结构5.ppt

第五章数组和广义表 数组的类型定义 稀疏矩阵的压缩存储 数组的顺序表示和实现 广义表的类型定义 广义表的表示方法 广义表操作的递归函数 数组的类型定义 ADT Array { 数据对象: D = {aj1,j2, ...,,ji, ...,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+1,j>| 0 ≤i≤ b1-2, 0 ≤j≤ b2-1} COL = {<ai,j,ai,j+1>| 0 ≤i≤ b1-1, 0 ≤ j≤ b2-2} 基本操作: 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 。 数组的顺序表示和实现类型特点: 1) 只有引用型操作,没有加工型操作; 2) 数组是多维的结构,而存储空间是一个一维的结构。有两种顺序映象的方式:1)以行序为主序(低下标优先); 2)以列序为主序(高下标优先)。