本课课题： 广义表
教学目的： 掌握广义表的定义，它的链接存储结构，以及求广义表长度、深度的方法和递归算法 教学重点： 广义表的操作及意义 教学难点： 广义表存储结构 教学过程： 一、广义表的定义
广义表是线性表的推广，其表中的元素可以是另一个广义表,或其自身。
对于一个非空的广义表来说，它的第一个元素称为该广义表的表头，除第一个元素外的所有元素构成的表称为该广义表的表尾。
一个表的尝试是指该表中括号嵌套的最大次数。 广义表的定义: ADT GList{
数据对象:D={i=1,2,...,n>=0;ei(-AtomSet或ei(-GList, AtomSet为某个数据对象}
数据关系:R1={ 操作结果:创建空的广义表L CreateGList(&L,S); 初始条件:S是广义表的书写形式串 操作结果:由S创建广义表L DestroyGlist(&L); 初始条件:广义表L存在 操作结果:销毁广义表L CopyGlist(&T,L); 初始条件:广义表L存在 操作结果:由广义表L复制得到广义表T GListLength(L); 初始条件:广义表L存在 操作结果:求广义表L的长度,即元素个数 GListDepth(L); 《数据结构》教案21 初始条件:广义表L存在 操作结果:求广义表L的深度 GlistEmpty(L); 初始条件:广义表L存在 操作结果:判断广义表L是否为空 GetHead(L); 初始条件:广义表L存在 操作结果:取广义表L的头 GetTail(L); 初始条件:广义表L存在 操作结果:取广义表L的尾 InsertFirst_GL(&L,e); 初始条件:广义表L存在 操作结果:插入元素e作为广义表L的第一元素 DeleteFirst_GL(&L,&e); 初始条件:广义表L存在 操作结果:删除广义表L的第一元素,并用e返回其值 Traverse_GL(L,Visit()); 初始条件:广义表L存在 操作结果:遍历广义表L,用函数Visit处理每个元素 }ADT GList 广义表一般记作:LS=(a1,a2,...,an) 其中LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为原子和子表,当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾. 二、广义表的图形表示 ——用圆圈和方框分别表示表（表元素）和单元素，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来，则可得到一个广义表的图形表示。 [例]画出下列广义表的图形表示 A＝（） B＝（e） C＝（a,（b,c,d）） 《数据结构》教案22 D＝（A,B,C）＝（（），（e），（a,（b,c,d））） E＝（（a,（a,b）,((a,b）,c））) 解： 《数据结构》教案23 e a b c d e a b c d a a b c a b 一个表的深度是指该表中括号嵌套的最在次数。所以A和B的深度为1，C、D、E的深度分别为2，3，4。 三、广义表的存储结构——广义表是一种递归的数据结构，因此很难为广义表分配固定大小的存储空间，所以其存储结构只好采用动态链接结构。 广义表的头尾链表存储表示 typedef emnu{ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union{ AtomType atom; struct{struct GLNode *hp,*tp;}ptr; } } 四、广义表的运算 ——包括求广义表的长度和深度，向广义表插入元素和从广义表中查找或删除元素，建立广义表的存储结构，打印广义表等。 总结： 1、广义表是线性表的嵌套结构，即每个元素仍可是一个表。广义表所含元素的个数称为广义表的长度，嵌套的最大层数称为广义表的深度。 2、广义表的存储结构采用动态链接结构，单元素结点和表元素结点，虽然具有相同的结点类型，但具有不同的结点结构，一个含有存储元素值的数据域data，另一个含有存储表元素起始位置的指针域sublist。 《数据结构》教案24