genlist.cpp

广义表的实现用vc

#include"Genlist.h"
#include"String.h"
#include"stdlib.h"
#include"iostream.h"
GenlistNode &GenlistNode::Info(GenlistNode * elem)
{
	GenlistNode *pitem=new GenlistNode;
	pitem->utype=elem->utype;
	pitem->value=elem->value;
	return * pitem;
}
void GenlistNode::setInfo(GenlistNode * elem,GenlistNode * x)
{     elem->utype=x->utype;
      elem->value=x->value;
}
Genlist::Genlist()
{
	GenlistNode *first=new GenlistNode;
	first->utype=0;
	first->value.ref=1;
	first->tlink=NULL;
}
Genlist::Genlist(char*s)
{ 
	
int a=Createlist(first,s);
  if(a==1)
	  cout<<"success"<<endl;
  else
	  cout<<"fail"<<endl;
}
Genlist::~Genlist()
{
	Remove(first);
}
void Genlist::Remove(GenlistNode *ls)
{
	ls->value.ref--;
	if(!ls->value.ref)
	{
		GenlistNode *y=ls->tlink,*z;
		delete ls;
		while(y!=NULL)
		{  z=y;
			y=y->tlink;
			delete z;
			if(y!=0)
			{	if(y->utype==LST)
				Remove(y->value.hlink);
			}
			else return;
		}
		//y->tlink=av;
		//av=ls;
	}
}


int Genlist::sever(char * &str1,char * & hstr1)
{      
	   char ch=str1[0];
       int n= strlen(str1);
       int i=0,k=0;
        while (i<n &&(ch!=','||k!=0))
			{
			if(ch=='(')k++;
			else if(ch==')')k--;
			i++;
			ch=str1[i];
			}
        if(i<n)
		{
			strncpy(hstr1,str1,i);
			hstr1[i]=0;
			strncpy(str1,str1+i+1,n-i-1);
			str1[n-i-1]=0;
			return 1;
		}
		else if(k!=0)
			return 0;
		else
		{
			strcpy(hstr1,str1);
			hstr1[n]=0;
		    str1[0]=0;
			return 1;
		}
}



int Genlist::Createlist(GenlistNode * &ls,char *s)
{    int b=strlen(s);
	char * sub=new char[b-1];
	sub[b-2]=0;
    char * hsub=new char[b];
	ls=new GenlistNode();
	ls->utype=HEAD;
	ls->value.ref=1;
	if(strlen(s)==0||!strcmp(s,"()"))ls->tlink=0;
	else 
	{
		strncpy(sub,s+1,strlen(s)-2);
	    GenlistNode * p=ls;
	    while( strlen(sub)!=0)
		{
		   p=p->tlink=new GenlistNode();
		   if(sever(sub,hsub))
		   {
		  	  if(hsub[0]!='('&&hsub[0]!='\'')
			  {
				p->utype=INTGR;
				p->value.intg=atoi(hsub);
			  }
		      else if(hsub[0]!='('&& hsub[0]=='\'')
			  {
				p->utype=CH;
				p->value.chari=hsub[1];
			  }
			 else
			 {
                   p->utype=LST;
				   Createlist(p->value.hlink,hsub);
			 }
		   }
		else return 0;
		}
	p->tlink=0;
	}
	
	delete[] sub;
	delete[] hsub;
return 1;
}


void Genlist::print()
{ Genlist::print(first);
}
void Genlist::print(GenlistNode *p)
{   cout<<"(";
int i=0;
while( p->tlink)
{  if(i!=0) cout<<",";
   p=p->tlink;	
  if(p->utype==LST)
	{	print(p->value.hlink);
	   
	}
	else if(p->utype==INTGR)
		cout<<p->value.intg;
	else 
		cout<<"'"<<p->value.chari<<"'";
        i=1;  
}
	cout<<")";
}