第四、五章 串 数组与广义表.pptVIP

第四章 串 4.2.1 定长顺序存储表示 4.2 串的表示和实现 4.2 串的表示和实现 4.2 串的表示和实现 练习 第5章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.2 数组的顺序表示和实现 注意： 2.以“列优先顺序”存储 二维数组中任一元素aij的(首)地址是： LOC[aij]=LOC[a11]+[(i-1)?m+(j-1)]?l (5-1) i=1,2, …,n j=1,2, …,m 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.1 特殊矩阵 5.3.1 特殊矩阵 5.3.1 特殊矩阵 5.3.1 特殊矩阵 5.3.1 特殊矩阵 5.3.1 特殊矩阵 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.3.2 稀疏矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.4 广义表的定义 5.4 广义表的定义 练习 5.5 广义表的存储结构 5.5 广义表的存储结构 第5章 小结 第5章 数组和广义表 练习 作业 作业 1、定义 广义表是线性表的推广，也称为列表（lists）。 记为：LS=（a1，a2，……，an） 广义表名 n是表长 在广义表中约定： ① ai可以是单个元素，也可以是广义表，分别称为原子和子表; ② 用小写字母表示元素，用大写字母表示列表名称； ③ 当LS非空时，称第一个元素为表头(Head)，其余元素组成的表 (a2，…，an)为表尾(Tail)。 任何一个非空表，表头可能是原子，也可能是列表，但 表尾一定是列表。 例如: A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a, ??? , ) ) ) 5.4 广义表的定义 广义表是一个多层次的线性结构 例如： D=(E, F) 其中: E=(a, (b, c)) F=(d, (e)) D E F a ( ) d ( ) b c e 5.4 广义表的定义 广义表 LS = ( ?1, ?2, …, ?n )的结构特点: 1) 广义表中的数据元素有相对次序； 2) 广义表的长度定义为最外层包含元素个数； 3) 广义表的深度定义为所含括弧的重数； 例如，A=(b,c)的深度为1， B=(A,d)的深度为2， C=(f,B,h)的深度为3。 注意：“原子”的深度为 0 　“空表”的深度为 1 4) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。 如：E=(a,E) 5.4 广义表的定义 例：求下列广义表的长度。 (1) A=( ) (2) B=(e) (3) C=(a，(b，c，d)) (4) D=（A ，B，C） (5) E=(a，E) n=0，因为A是空表 n=1，表中元素e是原子 n=2，a 为原子，(b,c,d)为子表 D=(A,B,C)=(( ),(e),(a,(b,c,d)))，共享表 E=(a,E)=(a,(a,E))= (a,(a,(a,…….)))，E为递归表 n=3，3个元素都是子表 n=2，a 为原子，E为子表 表中元素个数 例如: D = ( E, F ) = ((a, (b, c))，F ) Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) ) Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) 5.4 广义表的定义 5) 任何一个非空广义表 LS = ( ?1, ?2, …, ?n) 均可分解为表头 GetHead(LS) = ?1 和表尾 GetTail(LS) = ( ?2, …, ?n)两部分。 广义表两种特殊的基本操作： GetHead 【 L 】－－－取表头（可能是原子或列表） GetTail 【 L 】 －－－取表尾（一定是列表） （1）GetTail【 (b，k，p，h ) 】 = （2）GetHead 【((a,b)，(c,d)) 】= （3）GetTail 【((a,b