ch042--list development two---Array and G-List.ppt

Chapter 4-2 List development Two --- Array 数组(Array) ---多维定长线性表 是线性表的推广，表中的数据元素本身也是一个线性表。 举例：二维数组 --- 可看作由定长一维表组成的定长一维表。 n维数组：各维定长的n维表。 - bi（1=i =n)是数组第i维的长度。则数组元素的第i维下标ji的取值范围0~ bi -1。 ADT接口： InitArray( A, n, b1, b2, …, bn) --- 数组初始化 DestroyArray( A) ---- 撤销数组 Value( A, e, index1, …, indexn ) --- 取数组元素值 Assign( A, e, index1, …, indexn ) --- 数组元素赋值 数组的顺序存储方式： 1）一维数组 2）二维数组 列优先存放： 3）三维数组 各维元素个数为 b1, b2, b3 下标为 i1, i2, i3的数组元素的存储地址：（按页/行/列顺序存放） LOC ( i1, i2, i3 ) = a + ( i1* b2 * b3 + i2* b3 + i3 ) * l i1* b2 * b3_——前i1页总元素个数 i2* b3 ——第i1页的前i2行总元素个数 i3——第 i2 行前 i3 列元素个数 4）n维数组 各维元素个数为 b1, b2, b3, …, bn 下标为 j1, j2, j3, …, jn 的数组元素的存储地址： LOC ( j1, j2, …, jn ) = a + ( j1*b2*b3*…*bn + j2*b3*b4*…*bn+ + ……+ jn-1*bn + jn ) * l 数组的应用： 1）矩阵的压缩存储 特殊矩阵的存储——三角矩阵 只存储上三角元素或下三角元素?一维数组 元素的个数 Chapter 4-3 List development Three --- generalized List 广义表的定义：n ( ? 0 )个表元素组成的有限序列，记作 L = (a1, a2, …, an) L是表名，ai是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。 n为表的长度。n = 0 的广义表为空表。 n 0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。 广义表的ADT说明 GetHead( L ) ----- 取表头操作 GetTail( L ) ----- 取表尾操作 例子： A = ( ) 对空表不求表头、表尾 B = ( 6, 2 ) GetHead(B)=6, GetTail(b)=(2) C = ( ‘a’, ( 5, 3, ‘x’ ) ) GetHead(C)=‘a’, GetTail(C)=((5,3,’x’)) D = ( B, C, A ) GetHead(D)=B, GetTail(D)=(C,A) E = ( B, D ) GetHead(E)=B, GetTail(E)=(D) F = ( 4, F ) GetHead(F)=4, GetTail(F)=(F) 特性： 有次序性，有长度，可共享，可递归，有深度 广义表的应用 （1）求对应关系 () ((NIL)) (()) NIL ((())) (NIL) (() ()) (NIL (NIL)) (() (())) (NIL NIL) （2）L=（a, (b, ( c ), e))利用求表头和求表尾操作将原子e分离出来 (3) 整数序列中，是否存在一个子序列（不一定是连续的）其和等于给定的整数x （1 2 3 7 9 ） 12 ? True （1 2 3 7 9 ） -1 ? False 可以将整数序列看成是一个广义表： True ? x = 0 ? 表尾中存在一个子序列其和等于x - head(L) ? 表尾中存在一个子序列其和等于x False ? L为空表 Bool Sublist_sum(L, x){ If x = 0 return true; If !L return false; else{ if (! Sublist_sum(Tail(L), x-Head(L)) return Sublist