第7章 图和广义表.ppt

* * * 一、广义表的类型定义 广义表的定义： 广义表是n（n≥0）个元素?1, ?2, ???, ?n的有限集，通常记作 LS = ( ?1, ?2, ???, ?n )。 广义表是递归定义的线性结构, 其中: ?i 或为原子 或为广义表（子表） 。 * 北京亚洲足球邀请赛 （日本, 韩国,中国, 朝鲜） （日本, 韩国, （申花, 实德, 现代）,（）） 在现实中，不乏广义表的例子： * 一般广义表的例子: A = ( ) 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) 广义表的深度定义为所含括弧的重数； 注意：“原子”的深度为 0 　“空表”的深度为 1 4) 广义表可以共享； 5) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。 * 6) 任何一个非空广义表 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 ) ) = ( ) * 结构的创建和销毁 InitGList(L); DestroyGList(L); CreateGList(L, S); CopyGList(T, L); 状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作 InsertFirst_GL(L, e); DeleteFirst_GL(L, e); 遍历 Traverse_GL(L, Visit()); 广义表的操作： * 二、广义表的存储结构 通常采用头、尾指针的链表结构 表结点: 原子结点： tag=1 hp tp tag=0 data * 1) 表头、表尾分析法： 构造存储结构的两种分析方法: 若表头为原子，则为 空表 ls=NIL 非空表 ls tag=1 指向表头的指针 指向表尾的指针 tag=0 data 否则，依次类推。 * 例如: L=(a, (x, y), ((x)) ) a ((x, y), ((x)) ) (x, y) ( ((x)) ) x (y) ((x)) ( ) y ( ) (x) ( ) x ( ) * L = ( a, ( x, y ), ( ( x ) ) ) a ( x, y ) ( ) 1 L L = ( ) 0 a 1 1 1 1 1 0 x ? ? ( ) x ? …… * 2) 子表分析法： 若子表为原子，则为 空表 ls=NIL 非空表 1 指向子