《内容提要广义表的概念广义表的存储结构广义表的课件》由会员分享，可在线阅读，更多相关《内容提要广义表的概念广义表的存储结构广义表的课件（22页珍藏版）》请在装配图网上搜索。
1、2023/9/116.1 广义表的概念广义表的概念 定义：定义：广义表是广义表是n(nn(n=0)=0)个元素个元素a a1 1,a,a2 2,a,an n的有限序列，其中的有限序列，其中a ai i或者是原子或者是一个广或者是原子或者是一个广义表。义表。GListGList=a a1,1,a a2,2,anan|ai ai AtomSetAtomSet或或或或aiai GListGList 原子结点原子结点原子结点原子结点 子表结点子表结点子表结点子表结点 2023/9/11例如例如:A=()B=(a,b,c)C=(a,(b,c,d),e)D=(a,b),c,(d,(e,f),g)E=(a,
2、(),(),(),b)L=(a,(a,b),(a,(a,b),c),()注意注意：（）、）、（）是不同的。（）是不同的。线性表是广义表的特殊情况。线性表是广义表的特殊情况。2023/9/11 递归表递归表递归表递归表：允许递归的表。：允许递归的表。：允许递归的表。：允许递归的表。表的长度表的长度表的长度表的长度:表中直接元素的个数表中直接元素的个数表中直接元素的个数表中直接元素的个数.表的深度表的深度表的深度表的深度：表中嵌套的最大层次数。表中嵌套的最大层次数。表中嵌套的最大层次数。表中嵌套的最大层次数。表头表头表头表头:第一个元素第一个元素第一个元素第一个元素.表尾表尾表尾表尾:除表头外剩下
3、部分组成的广义表除表头外剩下部分组成的广义表除表头外剩下部分组成的广义表除表头外剩下部分组成的广义表 例如例如例如例如:A A表的表头是表的表头是表的表头是表的表头是()()，表尾是，表尾是，表尾是，表尾是()()；B B表的表头是表的表头是表的表头是表的表头是a a，表尾是，表尾是，表尾是，表尾是(b b,c c)；C C表的表头是表的表头是表的表头是表的表头是a a，表尾是，表尾是，表尾是，表尾是(b b,c c,d d),),e e)；D D表的表头是表的表头是表的表头是表的表头是(a a b b)，表尾是，表尾是，表尾是，表尾是(c c,(,(d d,(,(e e,f f),),g g
4、)；E E表的表头是表的表头是表的表头是表的表头是a a，表尾是，表尾是，表尾是，表尾是(),(),(),(),(),(),b b)。2023/9/11 例例:X=(e)Y=(a,(b,c,d)Z=(X,Y)R=(a,R)S=()请指出它们的深度、表头、表尾。请指出它们的深度、表头、表尾。2023/9/11广义表的基本操作广义表的基本操作 构造一个广义表构造一个广义表 释放广义表空间释放广义表空间 遍历广义表遍历广义表 复制广义表复制广义表 求广义表的长度求广义表的长度 求广义表的深度求广义表的深度 求广义表的表头求广义表的表头 求广义表的表尾求广义表的表尾2023/9/116.2 6.2 广
5、义表的存储结构广义表的存储结构1.基本思想：基本思想：使用链式存储结构使用链式存储结构（顺序难以表达数据元素的层次关系）（顺序难以表达数据元素的层次关系）结点结构结点结构typeData/sublistnext2023/9/112.2.类型定义类型定义:enum GListNodeType ATOM,LIST;template struct GListNode GListNodeType type;union T data;GListNode*sublist;GListNode*next;2023/9/11举例举例:约定广义表结构有约定广义表结构有“头结点头结点”头结点的头结点的type域值取
6、域值取LIST 2023/9/112023/9/11template class GList GListNode*head;public:GList();GList(GList head,GList tail);/利用表头、表尾构造对象利用表头、表尾构造对象 GList(GList&gl);GList();void Traverse();/遍历算法遍历算法 int Length();/计算表的长度计算表的长度 int Depth();/计算表的深度计算表的深度 ;2023/9/11 6.3 广义表的基本操作算法广义表的基本操作算法 1.构造函数构造函数 2023/9/11vtemplate v
7、GList:GList(GList head,GList tail)v head=new GListNode;/创建表头结点创建表头结点v head-type=LIST;head-next=NULL;v /将表头的头结点作为第一个数据结点将表头的头结点作为第一个数据结点v head-sublist=head.head;v /将表尾第一个数据结点作为第二个数据结点将表尾第一个数据结点作为第二个数据结点v head.head-next=tail.head-sublist;v delete tail.head;/释放表尾的头结点释放表尾的头结点v head.head=tail.head=NULL;v
8、2023/9/112.2.遍历广义表遍历广义表(递归递归)vtemplate vvoid GList:Traverse(GListNode*p)v cout sublist;p;p=p-next)v if(p-type=ATOM)cout data ;v else Traverse(p);v cout );vvtemplate vvoid GList:Traverse()v Traverse(head);2023/9/113复制广义表复制广义表(递归递归)vtemplate vGListNode*GList:Copy(GListNode*p)v head=new GListNode;/创建头结
9、点创建头结点v head-type=LIST;head-next=head-sublist=NULL;v /复制原子结点、子表结点及其子表复制原子结点、子表结点及其子表v for(p=p-sublist;p;p=p-next)v newp=new GListNode;v newp-type=p-type;v if(p-type=ATOM)newp-data=p-data;v else newp-sublist=Copy(p);v /复制子表结点及其子表复制子表结点及其子表v if(head-sublist=NULL)head-sublist=tail=newp;v else tail-next
10、=newp;tail=newp;v 2023/9/11v tail-next=NULL;v return head;vvtemplate vGList:GList(GList&gl)v head=Copy(gl.head);2023/9/114求广义表的长度求广义表的长度vtemplate vint GList:Length()v n=0;v for(p=head-sublist;p;p=p-next)v n+;v return n;v2023/9/115.5.求广义表的求广义表的深度深度算法算法(递归递归)vdepth(p)的递归定义为的递归定义为:1）递归终止条件：）递归终止条件：当当*p
11、为原子时，为原子时，depth(p)=0,2）递归规律：）递归规律：depth(p)=1+Max depth(ai)2023/9/11v template vint GList:Depth(GListNode*p)v if(p-type=ATOM)return 0;v maxdepth=0;v for(q=p-sublist;q;q=q-next)v depth=Depth(q);v if(depthmaxdepth)maxdepth=depth;v v return maxdepth+1;v2023/9/11vtemplate vint GList:Depth()v return Depth
12、(head);2023/9/116.6.广义表的析构算法广义表的析构算法(递归递归)template void GList:Free(GListNode*p)if(p=NULL)return;q=p;/q指向待释放结点指向待释放结点 p=p-sublist;/p指向第一个结点指向第一个结点 delete q;2023/9/11vwhile(p)v q=p;/q指向待释放结点指向待释放结点v p=p-next;/p指向下一个结点指向下一个结点v if(q-type=ATOM)delete q;v else Free(q);v vvtemplate vGList:GList()v Free(head);2023/9/11本本 章章 小小 结结v（1）掌握广义表的定义。）掌握广义表的定义。v（2）重点掌握广义表的存储结构。）重点掌握广义表的存储结构。v（3）掌握广义表的基本运算，）掌握广义表的基本运算，包括创建广义表、释放广义表、遍历广义表、包括创建广义表、释放广义表、遍历广义表、求广义表的长度和深度。求广义表的长度和深度。
内容提要广义表的概念广义表的存储结构广义表的课件
