数据结构第5章3.pptVIP

十字链表 矩阵A的十字链表: 0 0 1 2 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 6 0 0 1 6 -2 3 4 -8 4 2 3 4 6 7 5 3 9 5 1 -12 0 0 广义表（Lists，又称列表）是线性表的推广。 广义表是n(n=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。 通常记作LS=（a1,a2,a3,…,an)。 LS是广义表的名字，n为长度。若ai是广义表，则称它为LS的子表。 与线形表的区别： 线性表的元素仅限于原子项 广义表的元素除可以是原子项，还可以是表结构 5.4 广义表的定义 广义表的抽象数据类型 ADT GList{ 数据对象：D={ei∣i=1,2,…,n; n≥0; ei∈AtomSet或ei∈GList,AtomSet为某个数据对象} 数据关系：R={ei-1,ei∣ei-1,ei∈D,2≤i≤n} 基本操作： InitGList(L); CreateGList(L,S); GListLength(L); GListDepth(L) GetHead(L) GetTail(L) InsertGL(L,e); DeleteGL(L,e); }ADT GList 例如: A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a, ??? , ) ) ) 广义表是一个多层次的线性结构 例如： D=(E, F) 其中: E=(a, (b, c)) F=(d, (e)) D E F a ( ) d ( ) b c e 广义表 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) 任何一个非空广义表 LS = ( ?1, ?2, …, ?n) 均可分解为 表头 Head(LS) = ?1 和 表尾 Tail(LS) = ( ?2, …, ?n) 两部分。 例如: 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 ) ) = ( ) 1. GetTail【(b, k, p, h)】＝ ; 2. GetHead【( (a,b), (c,d) )】＝ ; 3. GetTail【( (a,b), (c,d) )】＝ ; 4. GetTail【 GetHead【((a,b),(c,d))】】＝ ; 例：求下列广义表操作的结果 (k, p, h) （b） (a,b) 5. GetTail【（e）】＝ ; 6. GetHead 【 ( ( ) )】＝ . 7. GetTail【 ( ( ) ) 】＝ . ( ) (a,b) ( ) ( ) ((c,d)) 5.5 广义表的存储结构 顺序存储结构：不能； 链式存储结构: 关键是结点的定义 表结点: tag=1 hp