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

1、2022-8-1 2022-8-12022-8-12022-8-12022-8-1 广义表的基本操作广义表的基本操作 2022-8-11.基本思想：基本思想：使用链式存储结构使用链式存储结构（顺序难以表达数据元素的层次关系）（顺序难以表达数据元素的层次关系）结点结构结点结构typeData/sublistnext2022-8-12.2.类型定义类型定义:enum GListNodeType ATOM,LIST;template struct GListNode GListNodeType type;union T data;GListNode*sublist;GListNode*next;20

2、22-8-1举例举例:约定广义表结构有约定广义表结构有“头结点头结点”头结点的头结点的type域值取域值取LIST 2022-8-12022-8-1template class GList GListNode*head;public:GList();GList(GList head,GList tail);/利用表头、表尾构造对象利用表头、表尾构造对象 GList(GList&gl);GList();void Traverse();/遍历算法遍历算法 int Length();/计算表的长度计算表的长度 int Depth();/计算表的深度计算表的深度 ;2022-8-1 1.构造函数构造函

3、数 2022-8-1vtemplate vGList: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.

4、head=tail.head=NULL;v2022-8-12.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);2022-8-13复制广义表复制广义表(递归递归)vtemplate vGListNode*GList:Copy(GListNode*p)v head=

5、new GListNode;/创建头结点创建头结点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=ne

6、wp;v else tail-next=newp;tail=newp;v 2022-8-1v tail-next=NULL;v return head;vvtemplate vGList:GList(GList&gl)v head=Copy(gl.head);2022-8-14求广义表的长度求广义表的长度vtemplate vint GList:Length()v n=0;v for(p=head-sublist;p;p=p-next)v n+;v return n;v2022-8-1vdepth(p)的递归定义为的递归定义为:1）递归终止条件：）递归终止条件：当当*p为原子时，为原子时，de

7、pth(p)=0,2）递归规律：）递归规律：depth(p)=1+Max depth(ai)2022-8-1v 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;v2022-8-1vtemplate vint GList:Depth()v return Depth(head);2022-8-

8、1 template void GList:Free(GListNode*p)if(p=NULL)return;q=p;/q指向待释放结点指向待释放结点 p=p-sublist;/p指向第一个结点指向第一个结点 delete q;2022-8-1vwhile(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);2022-8-1本本 章章 小小 结结v（1）掌握广义表的定义。）掌握广义表的定义。v（2）重点掌握广义表的存储结构。）重点掌握广义表的存储结构。v（3）掌握广义表的基本运算，）掌握广义表的基本运算，包括创建广义表、释放广义表、遍历广义表、包括创建广义表、释放广义表、遍历广义表、求广义表的长度和深度。求广义表的长度和深度。