内容提要广义表的概念广义表的存储结构广义表的课件

1、2022/7/246. 1 广义表的概念 定义：广义表是n(n=0)个元素a1,a2,an的有限序列，其中ai或者是原子或者是一个广义表。 GList = a1,a2,an | aiAtomSet或aiGList 原子结点 子表结点 2022/7/24例如: A = ( ) B = (a, b, c) C = (a, (b, c, d), e) D = (a, b), c, (d, (e, f), g) ) E = (a, ( ), ( ), ( ), b) L=(a, (a, b), (a, (a, b), c), ( ) 注意：（ ）、 （）是不同的。 线性表是广义表的特殊情况。 2022

2、/7/24 递归表：允许递归的表。 表的长度: 表中直接元素的个数. 表的深度： 表中嵌套的最大层次数。 表头: 第一个元素. 表尾: 除表头外剩下部分组成的广义表例如:A表的表头是( )，表尾是( )；B表的表头是a，表尾是(b, c)；C表的表头是a，表尾是( (b, c, d), e)；D表的表头是(a b)，表尾是(c, (d, (e, f), g) )；E表的表头是a，表尾是( ( ), ( ), ( ), b)。2022/7/24 例: X = ( e ) Y = (a, (b, c, d) Z = (X, Y) R = (a, R) S = ( ( ) ) 请指出它们的深度、表头

3、、表尾。 2022/7/24广义表的基本操作 构造一个广义表 释放广义表空间 遍历广义表 复制广义表 求广义表的长度 求广义表的深度 求广义表的表头 求广义表的表尾2022/7/246.2 广义表的存储结构1. 基本思想： 使用链式存储结构（顺序难以表达数据元素的层次关系） 结点结构typeData/sublistnext2022/7/242. 类型定义:enum GListNodeType ATOM, LIST ;template struct GListNode GListNodeType type; union T data; GListNode *sublist; ; GListNod

4、e * next; ;2022/7/24举例: 约定广义表结构有“头结点” 头结点的type域值取LIST 2022/7/242022/7/24template class GList GListNode *head;public: GList(); GList(GList head, GList tail); / 利用表头、表尾构造对象 GList(GList &gl); GList( ); void Traverse( ); / 遍历算法 int Length( ); / 计算表的长度 int Depth( ); / 计算表的深度 ; 2022/7/24 6.3 广义表的基本操作算法 1.

5、 构造函数 2022/7/24template GList:GList(GList head, GList tail) head=new GListNode; / 创建表头结点 head-type=LIST; head-next=NULL; / 将表头的头结点作为第一个数据结点 head-sublist= head.head; / 将表尾第一个数据结点作为第二个数据结点 head.head-next = tail.head-sublist; delete tail.head; / 释放表尾的头结点 head.head=tail.head=NULL; 2022/7/242. 遍历广义表(递归)t

6、emplate void GList:Traverse(GListNode *p) cout sublist; p; p=p-next) if (p-type=ATOM) cout data ; else Traverse(p); cout ); template void GList:Traverse( ) Traverse(head ); 2022/7/243复制广义表 (递归)template GListNode *GList:Copy(GListNode* p) head=new GListNode; / 创建头结点 head-type=LIST; head-next=head-sub

7、list=NULL; / 复制原子结点、子表结点及其子表 for (p=p-sublist; p; p=p-next) newp=new GListNode; newp-type = p-type; if (p-type=ATOM) newp-data =p-data; else newp-sublist=Copy(p); / 复制子表结点及其子表 if (head-sublist=NULL) head-sublist=tail=newp; else tail-next=newp; tail=newp; 2022/7/24 tail-next=NULL; return head;templat

8、e GList:GList(GList &gl) head = Copy(gl.head); 2022/7/244求广义表的长度template int GList:Length() n=0; for (p=head-sublist; p; p=p-next) n+; return n;2022/7/245. 求广义表的深度算法(递归)depth(p)的递归定义为:1）递归终止条件： 当*p为原子时，depth(p)=0, 2）递归规律： depth(p) =1+ Max depth(ai)2022/7/24 template int GList:Depth(GListNode *p) if

9、(p-type=ATOM) return 0; maxdepth=0; for (q=p-sublist; q; q=q-next) depth=Depth(q); if (depthmaxdepth) maxdepth=depth; return maxdepth+1;2022/7/24template int GList:Depth() return Depth(head); 2022/7/246. 广义表的析构算法 (递归) template void GList:Free(GListNode *p) if (p=NULL) return; q=p; / q指向待释放结点 p=p-sublist; / p指向第一个结点 delete q; 2022/7/24while( p ) q=p; / q指向待释放结点 p=p-next; / p指向下一个结点 if (q-type=ATOM) de