guangyim.txt

一本数据结构的经典书籍-数据结构算法程序集里

//广义表的类定义guangyi.h
#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);
};
//广义表的类实现guangyi.cpp
//返回由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->intinfo==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=new GList;
 q=p;p->first=NULL;
 char *sub=new char[30];
 char *hsub=new char[30];
 for(int i=0;i<30;i++) hsub[i]=sub[i]='\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[i];
  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);
}
//广义表的相关操作的测试guangyiM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<conio.h>
#include "guangyi.h"
#include "guangyi.cpp"
static GList *GL,*GL1,*GL2,*GL3;
static GList GU,GU1,GU2,GU3,GU4;
void main()
{cout<<"guangyiM.cpp运行结果:\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();}
guangyiM.cpp运行结果:
欲创建的广义表=(A,(B),(3,5,7),(a,b),((C)),D)
广义表的长度=29
返回的指针值GL=12603376
创建后的广义表=(A,(B),(3,5,7),(a,b),((C)),D)
广义表GL的深度=6
删除5后的广义表GL=(A,(B),(3,7),(a,b),((C)),D)
删除a后的广义表GL=(A,(B),(3,7),(b),((C)),D)
将GU3定义为由ls指示的广义表的尾:(A,(B),(3,7),(b),((C)),D,9)
重置广义表的头元素后的广义表:(9,(B),(3,7),(b),((C)),D,9)
复制后的广义表GL1=(9,(B),(3,7),(b),((C)),D,9)
广义表GU的第一个元素的值:
GU2.utype=0,GU2.intinfo=9
广义表GU的第一个元素的值:
GU.utype=0,GU.intinfo=9
欲创建的广义表=(A,(B),(3,5),(a,b),7)
广义表的长度=21
广义表GU与GU1不等!
修改广义表GU1的表头后的广义表:(9,A,(B),(3,5),(a,b),7)
广义表GU1除第一个元素以外其它元素组成的表:(A,(B),(3,5),(a,b),7)
欲创建的广义表=(9,(B),(3,5),(a,b))
广义表的长度=19
创建后的广义表=(9,(B),(3,5),(a,b))
以GU3为头,由GL3指示的广义表为尾的新表:(F,(9,(B),(3,5),(a,b)))