VC++2012编程演练数据结构《16》广义表

大灰狼

广义表是一种非线性的数据结构，顾名思义，它也是线性表的一种推广。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。
线性表被定义为一个有限的序列（a1，a2，a3，…，an）其中ai被限定为是单个数据元素。广义表也是n个数据元素d1，d2，d3，…，dn的有限序列，但不同的是，广义表中的di 则既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的。因为在定义广义表时，又使用了广义表的概念。
　　l D=（） 空表；其长度为零。
　　l A=（a，（b，c）） 表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。
　　l B=（A，A，D） 长度为3的广义表，其前两个元素为表A，第三个元素为空表D。
　　l C=（a，C） 长度为2递归定义的广义表，C相当于无穷表C=（a，（a，（a，（…））））。
　　其中，A，B，C，D是广义表的名字。下面以广义表A为例，说明求表头、表尾的操作如下：
　　head（A）=a； 表A的表头是：a
　　tail（A）=（（b，c））； 表A的表尾是（（b，c））。广义表的表尾一定是一个表。
　（1） 广义表的元素可以是子表，而子表还可以是子表…，由此，广义表是一个多层的结构。
　　（2） 广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。  周游广义表（3） 广义表具有递归性，如广义表C。

　　由于广义表GL=（d1，d2，d3，…，dn）中的数据元素既可以是单个元素，也可以是子表，因此对于广义表，我们难以用顺序存储结构来表示它，通常我们用链式存储结构来表示。表中的每个元素可用一个结点来表示。广义表中有两类结点，一类是单个元素结点，一类是子表结点。从上节得知，任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域。而元素结点置需要两个域：标志域和值域。

打开IDE

我们创建一个工程

类的声明如下

[cpp] view plaincopy

• #if !defined(AFX_GUANGYI_H__B04529B0_92E5_49C0_954F_629AA89C2F0A__INCLUDED_)  
• #define AFX_GUANGYI_H__B04529B0_92E5_49C0_954F_629AA89C2F0A__INCLUDED_  
•   
• #if _MSC_VER > 1000  
• #pragma once  
• #endif // _MSC_VER > 1000  
•   
• //广义表的类定义  
• #include<string.h>  
• #include<stdio.h>  
• #include<math.h>  
• typedef enum{INTGR,CH,LST}ElemTag;  
• class GList  
• {public:  
• ElemTag utype;  
• GList *first;  
• union  
• { int intinfo;  
• char charinfo;  
• GList *hlink;  
• };  
• //构造函数  
• GList(){}  
• //返回由elem指示的表元素的值  
• GList &Info(GList *&elem);  
• //返回表元素elem的元素值的数据类型  
• int nodetype(GList *elem) {return elem->utype;}  
• //将由elem指示的表元素的值修改为x  
• GList &setInfo(GList *&elem,GList &x);  
• //判断广义表是否相等的重载函数  
• int operator ==(GList &m);  
• //判断广义表是否相等  
• int equal(GList *s,GList *t);  
• //返回由ls指示的广义表的第一个元素的值  
• GList &Head(GList *&ls);  
• //返回广义表除第一个元素以外其它元素组成的表  
• GList *Tail();  
• //返回广义表的第一个元素  
• GList *First();  
• //返回由elem指示的表元素的直接后继元素  
• GList *Next(GList *elem);  
• //返回一个以x为头,由ls指示的广义表为尾的新表  
• GList *Addon(GList *ls,GList &x);  
• //由ls指示的广义表的复制  
• GList *Copy(GList *ls);   
• //求由ls指示的非递归表的深度  
• int depth(GList *&ls);  
• //判断广义表是否为空  
• bool GlistEmpty() {return first==NULL;}  
• //将广义表的头元素重置为x  
• void setHead(GList *&ls,GList &x);  
• //将elem2插到表中元素elem1后  
• void setNext(GList *elem1,GList *elem2);  
• //将x定义为由ls指示的广义表的尾  
• void setTail(GList *&ls,GList &x);  
• //插入元素x作为由ls指示的广义表的第一元素  
• GList *InsertGL(GList *&ls,GList &x);  
• //删除广义表中含数x或结点x的操作  
• GList *delvalue(GList *&ls,int x);  
• //删除广义表中含数x或结点x的操作  
• GList *delvalue(GList *&ls,char x);  
• //S是广义表的书写形式串,由S创建广义表GL  
• GList *CreateGList(char *&s);  
• //建立广义表时调用的过程  
• int sever(char *&str1,char *&hstr1);  
• //广义表的输出  
• void prtGlist(GList *h);  
• };  
•   
•   
• #endif // !defined(AFX_GUANGYI_H__B04529B0_92E5_49C0_954F_629AA89C2F0A__INCLUDED_)  
  

类的实现如下

[cpp] view plaincopy

• #include "stdafx.h"  
• #include "guangyi.h"  
•   
• //广义表的类实现  
• //返回由elem指示的表元素的值  
• GList &GList::Info(GList *&elem)  
• {static GList *pitem=new GList;  
• pitem->utype=elem->utype;  
• if(elem->utype==LST)  
•   pitem->hlink=elem->hlink;  
• if(elem->utype==INTGR)  
•   pitem->intinfo=elem->intinfo;  
• if(elem->utype==CH&&elem->charinfo!=')')  
•   pitem->charinfo=elem->charinfo;  
• pitem->first=elem->first;  
• return *pitem;  
• }  
• //将由elem指示的表元素的值修改为x  
• GList &GList::setInfo(GList *&elem,GList &x)  
• {elem->utype=x.utype;  
• if(x.utype==INTGR)  
•   elem->intinfo=elem->intinfo;  
• if(x.utype==CH&&x.charinfo!=')')  
•   elem->charinfo=x.charinfo;  
• return *elem;  
• }  
• //返回由ls指示的广义表的第一个元素的值  
• GList &GList::Head(GList *&ls)  
• {static GList *temp;  
• if(ls==NULL)  
•   {cout<<"Illegal head operation.\n";exit(1);}  
• else {  
•   temp=new GList;  
•   ls=ls->first;  
•   temp=ls;  
•   if(ls->utype==INTGR)  
•     temp->intinfo=ls->intinfo;  
•   if(ls->utype==CH)  
•     temp->charinfo=ls->charinfo;}  
• temp->first=ls;  
• return *temp;  
• }  
• //返回广义表除第一个元素以外其它元素组成的表  
• GList *GList::Tail()  
• {if(first==NULL)  
•   {cout<<"Illegal head operation.\n";exit(1);}  
• return first->first;  
• }  
• //返回广义表的第一个元素  
• GList *GList::First()  
• {if(hlink==NULL) return NULL;  
• else return hlink;  
• }  
• //返回由elem指示的表元素的直接后继元素  
• GList *GList::Next(GList *elem)  
• {if(elem->first==NULL) return NULL;  
• else return elem->first;  
• }  
• //插入元素x作为由ls指示的广义表的第一元素  
• GList *GList::InsertGL(GList *&ls,GList &x)  
• {if(ls->hlink==NULL) ls->hlink=&x;  
• else {  
•    static GList *temp=new GList;  
•    temp->utype=x.utype;  
•    temp->first=ls->first;  
•    temp->intinfo=x.intinfo;  
•    ls->hlink=temp;  
•    ls->first=temp;}  
• return ls;   
• }  
• //返回一个以x为头,由ls指示的广义表为尾的新表  
• GList *GList::Addon(GList *ls,GList &x)  
• {static GList *p=new GList;  
• p->utype=x.utype;  
• if(x.utype==INTGR) p->intinfo=x.intinfo;  
• if(x.utype==CH) p->charinfo=x.charinfo;  
• p->first=Copy(ls);  
• ls=p;  
• return ls;  
• }  
• //将广义表的头元素重置为x  
• void GList::setHead(GList *&ls,GList &x)  
• {static GList *temp=new GList;  
• temp->utype=x.utype;  
• if(x.utype==INTGR) temp->intinfo=x.intinfo;  
• if(x.utype==CH&&x.charinfo!=')') temp->charinfo=x.charinfo;  
• temp->first=ls->first->first;  
• ls->first=temp;  
• ls->hlink=temp;  
• }  
• //将elem2插到表中元素elem1后  
• void GList::setNext(GList *elem1,GList *elem2)  
• {GList *temp;  
• while(elem1->first!=NULL)  
• {temp=elem1->first;  
•   elem2->first=temp->first;  
•   delete temp;}  
• elem1->first=elem2;  
• }  
• //将x定义为由ls指示的广义表的尾  
• void GList::setTail(GList *&ls,GList &x)  
• {static GList *r,*q,*p,*temp=new GList;  
• temp->utype=x.utype;  
• if(x.utype==INTGR) temp->intinfo=x.intinfo;  
• if(x.utype==CH&&x.charinfo!=')') temp->charinfo=x.charinfo;  
• r=ls;  
• while(!(r->charinfo!=')'&&r->first->first->first==NULL))  
•   {p=r->first;r=r->first;}  
• q=p->first;  
• p->first=temp;  
• temp->first=q;  
• }  
• //由ls指示的广义表的复制  
• GList *GList::Copy(GList *ls)  
• {static GList *gh,*q,*p=new GList;  
• q=p;  
• if(ls)  
•   do {  
•    gh=new GList;  
•    p->utype=ls->utype;  
•    switch(ls->utype)  
•    {case INTGR:p->intinfo=ls->intinfo;break;  
•     case CH:p->charinfo=ls->charinfo;break;  
•     case LST:p->hlink=ls->hlink;break;  
•    }  
•    p->first=ls->first;  
•    ls=ls->first;  
•    p=gh;  
•   }while(ls->first!=NULL);  
• p->first=NULL;   
• return q;  
• }  
• //求由ls指示的非递归表的深度  
• int GList::depth(GList *&ls)  
• {GList *temp=ls;  
• int m=0;  
• if(temp->first==NULL) return 0;  
• do  
• {if(temp->utype==LST) m++;  
•    temp=temp->first;  
• }while(temp!=NULL);  
• return m;  
• }  
• //判断广义表是否相等的重载函数  
• int GList::operator ==(GList &m)  
• {int k=equal(first,m.first);  
• return k;  
• }  
• //判断广义表是否相等  
• int GList::equal(GList *s,GList *t)  
• {int x;  
• if(s->first==NULL&&t->first==NULL) return 1;  
• if(s->first==NULL&&t->first==NULL&&  
•   s->first->utype==t->first->utype)  
• {if(s->first->utype==INTGR)  
•    if(s->first->intinfo==t->first->intinfo) x=1;  
•    else x=0;  
•   else if(s->first->utype==CH)  
•    if(s->first->charinfo==t->first->charinfo) x=1;  
•    else x=0;  
•   else x=equal(s->first->first,t->first->first);  
•   if(x) return equal(s->first,t->first);  
• }  
• return 0;  
• }  
• //删除广义表中含数x或结点x的操作  
• GList *GList::delvalue(GList *&ls,int x)  
• {static GList *r,*p,*q=ls;  
• p=ls;  
• while(ls!=NULL)  
• {p=ls->first;  
•   while(p!=NULL&&p->utype==INTGR&&p->intinfo==x)  
•    {r=p->first;  
•     delete p;  
•     p=r;break;}  
•   if(p==r){ls->first=r;break;}  
•   ls=ls->first;  
• }  
• return q;  
• }  
• //删除广义表中含数x或结点x的操作  
• GList *GList::delvalue(GList *&ls,char x)  
• {static GList *r,*p,*q=ls;  
• p=ls;  
• while(ls!=NULL)  
• {p=ls->first;  
•   while(p!=NULL&&p->utype==CH&&p->charinfo==x)  
•    {r=p->first;  
•     delete p;  
•     p=r;break;}  
•   if(p==r){ls->first=r;break;}  
•   ls=ls->first;  
• }  
• return q;  
• }  
• //S是广义表的书写形式串,由S创建广义表GL  
• GList *GList::CreateGList(char *&s)  
• {GList *r,*q,*p;  
• p=q=new GList;  
• p->first=NULL;  
• char *sub=new char[30];  
• char *hsub=new char[30];  
• for(int i=0;i<30;i++) hsub=sub='\0';  
• strncpy(sub,s,strlen(s));  
• sub[strlen(s)]='\0';  
• cout<<"欲创建的广义表="<<s<<endl;  
• cout<<"广义表的长度="<<strlen(s)<<endl;  
• if(strlen(sub)==0||!strcmp(sub,"()")) p->first=NULL;  
• else  
• {do  
•   {sever(sub,hsub);  
•    if(strlen(hsub)==1)  
•     {if(48<=hsub[0]&&hsub[0]<=57)  
•       {r=new GList;r->first=NULL;  
•        p->utype=INTGR;p->intinfo=atoi(hsub);  
•        p->first=r;p=r;}  
•      else  
•      {if((65<=hsub[0]&&hsub[0]<91)||(hsub[0]>=97&&hsub[0]<123)||hsub[0]==')')  
•        {r=new GList;r->first=NULL;  
•         p->utype=CH;p->charinfo=hsub[0];  
•         p->first=r;p=r;}  
•       else  
•       {if(hsub[0]=='(')  
•         {r=new GList;r->first=NULL;  
•          p->utype=LST;p->hlink=r;  
•          p->first=r;p=r;  
•    }}}}  
•   }while(*sub!='\0');  
•   p->first=NULL;  
• }  
• return q;  
• }  
• //建立广义表时调用的过程  
• int GList::sever(char *&str1,char *&hstr1)  
• {char ch;int i=0,k=0,j=0;  
• int n=strlen(str1);  
• static int m=1;  
• if(m==1)  
•   while(j<n||k!=0)  
•   {ch=str1[j];j++;m++;  
•    if(ch=='\0') break;  
•    if(ch=='(') k++;  
•    else if(ch==')') k--;}  
• if(k!=0) return 0;  
• for(i=0;i<n;++i)  
• {ch=str1;  
•   if(ch=='\0') break;  
•   if(ch==',')  
•    {for(int i0=i;i0<n;i0++)  
•      str1[i0]=str1[i0+1];  
•     break;}}  
• if(n>1) {  
•   strncpy(hstr1,str1,1);  
•   strncpy(str1,str1+1,n-1);str1[n-1]='\0';  
•   return 1;}  
• else if(n==1)  
•    {strncpy(hstr1,str1,1);  
•     str1[0]='\0';return 1;}  
• else return 0;   
• }  
• //广义表的输出  
• void GList::prtGlist(GList *h)  
• {GList *q,*p=h;  
• if(h)  
•   do  
•   {if(p->utype==INTGR)  
•     {q=p->first;  
•      if(q->charinfo==')'||q->first==NULL)  
•       cout<<p->intinfo;  
•      else cout<<p->intinfo<<',';  
•      p=p->first;}  
•    else  
•     {if(p->utype==CH)  
•       {q=p->first;  
•        if(q->charinfo==')'||q->first==NULL)  
•         cout<<p->charinfo;  
•        else cout<<p->charinfo<<',';  
•        p=p->first;}  
•      else  
•       if(p->utype==LST)  
•        {cout<<'(';p=p->first;}  
•     }  
• }while(p->first!=NULL);  
• }  
  

类的调用如下

[cpp] view plaincopy

• #include "stdafx.h"  
• #include "guangyi.h"  
• static GList *GL,*GL1,*GL2,*GL3;  
• static GList GU,GU1,GU2,GU3,GU4;  
• void main()  
• {cout<<"运行结果:\n";  
• char *a="(A,(B),(3,5,7),(a,b),((C)),D)";  
• char *b="(A,(B),(3,5),(a,b),7)";  
• char *c="(9,(B),(3,5),(a,b))";  
• GU3.utype=INTGR;GU3.intinfo=9;  
• GU3.first=GL2;  
• GL=GU.CreateGList(a);  
• cout<<"返回的指针值GL="<<GL<<endl;  
• cout<<"创建后的广义表=";  
• GU.prtGlist(GL);  
• cout<<"\n广义表GL的深度="<<GU.depth(GL);  
• GL=GU.delvalue(GL,5);  
• cout<<"\n删除5后的广义表GL=";GU.prtGlist(GL);  
• GL=GU.delvalue(GL,'a');  
• cout<<"\n删除a后的广义表GL=";GU.prtGlist(GL);  
• cout<<"\n将GU3定义为由ls指示的广义表的尾:";  
• GU.setTail(GL,GU3);GU.prtGlist(GL);  
• cout<<"\n重置广义表的头元素后的广义表:";  
• GU.setHead(GL,GU3);GU.prtGlist(GL);  
• GL1=GU.Copy(GL);  
• cout<<"\n复制后的广义表GL1=";  
• GU.prtGlist(GL1);  
• cout<<"\n广义表GU的第一个元素的值:\n";  
• GU2=GU.Head(GL1);  
• cout<<"GU2.utype="<<GU2.utype;  
• if(GU2.utype==INTGR)  
• cout<<",GU2.intinfo="<<GU2.intinfo<<endl;  
• if(GU2.utype==CH)  
• cout<<",GU2.charinfo="<<GU2.charinfo<<endl;  
• GU=GU.Info(GL1);  
• cout<<"广义表GU的第一个元素的值:\n";  
• cout<<"GU.utype="<<GU.utype;  
• if(GL1->utype==INTGR)  
• cout<<",GU.intinfo="<<GU.intinfo<<endl;  
• if(GL1->utype==CH)  
• cout<<",GU.charinfo="<<GU.charinfo<<endl;  
• GL2=GU1.CreateGList(b);  
• if(GU.operator ==(GU1)) cout<<"广义表GU与GU1相等!\n";  
• else cout<<"广义表GU与GU1不等!\n";  
• cout<<"修改广义表GU1的表头后的广义表:";  
• GL2=GU1.InsertGL(GL2,GU3);  
• GU1.prtGlist(GL2);  
• GU1=*GL2;  
• cout<<"\n广义表GU1除第一个元素以外其它元素组成的表:";  
• GL2=GU1.Tail();cout<<'(';  
• GU1.prtGlist(GL2);cout<<endl;  
• GL3=GU4.CreateGList(c);  
• cout<<"创建后的广义表=";  
• GU4.prtGlist(GL3);  
• cout<<"\n以GU3为头,由GL3指示的广义表为尾的新表:";  
• GU3.utype=CH;GU3.charinfo='F';  
• GU3.first=NULL;  
• GL3=GU4.Addon(GL3,GU3);cout<<'(';  
• GU4.prtGlist(GL3);cout<<')';  
• getch();  
• }  
  

效果如下