广义线性表.pptx

广义表广义表LS=(a1,a2,an)长度 n每个 ai 1in 或是一个元素（原子原子），或是一个子广义表。a1是表头head,a2,an 是表尾。用小写字母表示原子，大写字母表示广义表。广义表的例广义表的例A=()长度为0的空表。B=(e)只有一个元素的表，长为1。C=(a,(b,c,d)长度为2的广义表，第二个 元素是长度为3的子表。D=(A,B,C)长度为3的广义表，三个 元素都是长度为3的子表。D=(),(e),(a,(b,c,d)E=(a,E)递归定义的表。E=(a,(a,(a,).广义表的存储广义表的存储广义表的结点标志域标志域 表头指针表头指针 表尾指针表尾指针 tag=1 hp tp 表结点1标志域标志域 原子域原子域 表尾指针表尾指针 tag=0 atom tp 表结点2广义表结点类定义广义表结点类定义enum ElemTagATOM,LIST;templatestruct GLNode ElemTag tag;union T atom;GLNode *hp;GLNode *tp;tag=1 hp tp 表结点1tag=0 hp tp 表结点2广义表的链表表示广义表的链表表示1 A1B0 e C1 0 e10 a0 b0c D11 11E10 a1广义表结点类的补充定义广义表结点类的补充定义enum ElemTagATOM,LIST;templateclass GLNode ElemTag tag;union T atom;GLNode *hp;GLNode *tp;public:GLNode(const T&item,GLNode*t=NULL);GLNode(GLNode*h,GLNode*t);ElemTag GetType()return tag;T&GetValue();GLNode*Next();Void SetValue(GLNode&x);广义表结点类的实现广义表结点类的实现template GLNode:GLNode(const T&item,GLNode*t=NULL)tag=ATOM;atom=item;temp.tp=t;template GLNode:GLNode(GLNode*h,GLNode*t)tag=LIST;hp=h;tp=t;template T&GLNode:GetValue()if(tag=ATOM)return atom;else cout“no value”;return 0;template GLNode*GLNode:Next()return tp;template Void GLNode:SetValue(GLNode&x)tag=x.tag;tp=x.tp;if(tag=ATOM)atom=x.atom;else hp=x.hp;广义表类定义广义表类定义template class GList GLNode*first;GLNode*GetNode(const T&item,Node*t=NULL);GLNode*GetNode(Node*h=NULL,Node*t=NULL);void FreeGLNode(GLNode*p);void CopyList(const GList&list);void ClearGList();public:GList(void);Glist(GLNode*p);Glist(GLNode&x,Glist&list);Glist(GList&head,Glist&tail);GList(const GList&list);GList(void);GLNode*First();GLNode&Head();GLNode*Tail();void Push(GLNode&x);/add node x as head void SetHead(GLNode&x);/replace x to head void SetTail(Glist&L);templateGlist:GList(const GList&list)CopyList(list):template GLNode*Glist:GetNode(const T&item,Node*t=NULL)GLNode*p=new GLNode;p-tag=ATOM;p-atom=item;ptp=t;return p;template GLNode*Glist:GetNode(Node*h=NULL,Node*t=NULL)GLNode*p=new GLNode;p-tag=LIST;p-hp=h;p-tp=t;return p;template void Glist:FreeGLNode(GLNode*p)free p;template GLNode*GList:CopyList(const GList&list)GLNode*p,*q;q=this;if(list.first!=NULL)p=new GLNode;p-tag=list.first-tag;if(p.-tagATOM)p-atom=list.first-atom;elae p-hp=CopyList(list.first-hp);p-tp=CopyList(list.first-tp);this=p;q.ClearList();return p;templatevoid Glist:ClearGList()if(first-tag=LIST)ClearGList(first-hp);ClearList(first-tp);free(this);template Glist:GList(void)first=new GLNode;first-tag=LIST;first-hp=NULL;firsttp=NULL;template Glist:Glist(GLNode*p)first=p;template Glist:Glist(GLNode&x,Glist&list)first=new GLNode;first-tag=LIST;first-hp=new GLNode(x);first-tp=CopyList(list);templateGlist:Glist(GList&head,Glist&tail)first=new GLNode;first-tag=LIST;first-hp=CopyList(head);fisrt-tp=CopyList(tail);templateGlist:GList(void)ClearList();广义表的深度广义表的深度Depth(list)1 list 为空表Depth(list)=0 list 为原子 1+Max Depth(ai);O.W.广义表深度广义表深度Depth(list)的算法的算法int Depth(GLNode*p)if(p=NULL)return 1;if(p-tag=ATOM)return 0;GLNode*s;int dep;for(int max=0,s=p;s;s=s-tp)if(s-tag=LIST)dep=Depth(s-hp);if(depmax)max=dep;return max+1;int Depth(GList list)return Depth(list-first);