2014/47 s5.3广义表(Lists) s5.3广义表(Lists) 2存储结构 ·图示 因为广义表数据元素可具有不同结构，故难以用顺序方 E=NIL 式存储。一般用链接方式存储，称之为广义链表。 )广义表的头尾链表表示方法。 ·表结点吧→表 →aomhpp 。原子结点： tag-0 stom 1表结点，使用p和p 菊二服 邮一0原子结点，使用am 使用Uo0说明 存储结构见书上说明 §5.3广义表(Lists) s5.3广义表(Lists) ②单链表示法 ·特点 模仿战性表的单链表结构，当所有元素为原子时，等价于单链表 ①除空表的表头指针为空外，头指针均指向表结点。 ·结点结构： ②任一表结点的p均指向表头部（原子结点或表结点】 tom dats/slink limk-一→闸层后继（当无系鞋时为） 任一表结点的p均指向表尾部（当表尾部为空表时， 0本结点为子表《业指向子表的第一个结点) 【本结点为原子(4山) tp=NL,否则必指向表结点) ,图示：E=NL ③易分清表中原子和子表所在层次， C=(A,B)=((x,(a,b)),((x,(a,b)),y)) 如x、L在第一层，a、b在第二层。 =(A(x,L(a,b)),B(A(x,L(a,b)),y)) ④最高层的表结点数即为广义表的长度。 DHAD四 ⑤浪费空间，易求表长和表深度。 00□ O□N B G立□a四 g立□-b闪 §5.3广义表(Lists) s5.3广义表(Lists) ·存储结构说明 。缺点： typedef struct GLNode{ ①若要在某一表中开始处插入或删除一个结点，则要找 int atom:亦可定义为枚举类型，标志域 出所有指向该结点的指针，逐一加以修改。 struct GLNode*slink,指向同层后继 例如，上图中，删除A表中的x,修改A的头指针 union 外，须修改来自于B、C表的指针，引用来源点不易 知道。 struct GLNode*slink:指向子表的第一个结点 删除一个表可能导致错误 DataType data;I原子结点数据域 例如，删除A表时，A的所有结点释放后，会引起 optval;I候选值 B、C表的错误。 )*GList; 62014/4/7 6 §5.3 广义表（Lists） 2. 存储结构 因为广义表数据元素可具有不同结构，故难以用顺序方 式存储。一般用链接方式存储，称之为广义链表。 (1) 广义表的头尾链表表示方法。  表结点： 31  原子结点： 存储结构见书上说明 §5.3 广义表（Lists）  图示 E=NIL 32 §5.3 广义表（Lists）  特点 ① 除空表的表头指针为空外，头指针均指向表结点。 ② 任一表结点的hp均指向表头部（原子结点或表结点） 任一表结点的tp均指向表尾部（当表尾部为空表时， tp=NIL，否则必指向表结点） ③ 易分清表中原子和子表所在层次。 33 如x、L在第一层，a、b在第二层。 ④ 最高层的表结点数即为广义表的长度。 ⑤ 浪费空间，易求表长和表深度。 §5.3 广义表（Lists） (2) 单链表示法 模仿线性表的单链表结构，当所有元素为原子时，等价于单链表。  结点结构：  图示：E=NIL C (A B) (( ( b)) (( ( b)) )) 34 C=(A, B)=((x, (a, b)), ((x, (a, b)), y)) =(A(x, L(a, b)), B(A(x, L(a, b)), y)) §5.3 广义表（Lists）  存储结构说明 typedef struct GLNode{ int atom; //亦可定义为枚举类型，标志域 struct GLNode *slink; //指向同层后继 union { struct GLNode *slink; //指向子表的第一个结点 35 struct GLNode slink; //指向子表的第一个结点 DataType data； //原子结点数据域 }optval; //候选值 } *GList; §5.3 广义表（Lists）  缺点： ① 若要在某一表中开始处插入或删除一个结点，则要找 出所有指向该结点的指针，逐一加以修改。 例如，上图中，删除A表中的x，修改A的头指针 外，须修改来自于B、C表的指针，引用来源点不易 知道。 36 ② 删除一个表可能导致错误。 例如，删除A表时，A的所有结点释放后，会引起 B、C表的错误