递归广义表（创建，打印，求深度，删除指定结点）.cpp

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
//*************************
#define HEAD 0
#define INTER 1
#define CH 2
#define LST 3
//----------------------------
class GenList;

class GenListNode{
friend class GenList;
private:
	int utype;
	GenListNode *tlink;
	union
	{
		int ref;
		int intgrinfo;
		char charinfo;
		GenListNode *hlink;
	}      value;
public:

};
//----------------------------------------------------------------
class GenList{
	GenListNode *first;
	int GenList::Createlist( GenListNode *&ls, char *s);
	int depth(GenListNode *ls);
	int equal(GenListNode *s, GenListNode *t);
	void Remove(GenListNode *ls);
	void print(GenListNode *ls);
public:
	GenList();
	~GenList();
	int Createlist(char *s);
	int depth();
	int sever(char *str1, char *hstr1);
	void print();

};

//-------------------------------------------------------
GenList::GenList(){
	first = NULL;	
	first= new GenListNode;
	first->utype=0;
	first->value.ref=1;
	first->tlink=NULL;
	
	GenListNode *av=new GenListNode[100];
}
//-----------------------------------------------------------
int GenList::Createlist(char *s)
{
	return Createlist(first, s);
	
}
int GenList::Createlist( GenListNode *&ls, char *s){
	char sub[100], hsub[100];
	ls= new GenListNode();
	ls->utype=HEAD;
	ls->value.ref=1;
	if( strlen(s)==0||!strcmp(s,"()") )           //*
	{
		
		ls->tlink=NULL;
	}
	else
	{
		int length=strlen(s)-2;
		strncpy(sub, s+1, length);
		sub[length]=0;

		GenListNode *p = ls; 
		while(strlen(sub)!=0)
		{
			p =p->tlink=new GenListNode();
			//~
			if( sever(sub,hsub) )
			{
				if( hsub[0]!='('&&hsub[0]!='\'')
				{
					p->utype=INTER;
					p->value.intgrinfo=atoi( hsub );
				}
				else if( hsub[0]=='\'' )
				{
					p->utype=CH;
					p->value.charinfo=hsub[1];
				}
				else
				{
					p->utype=LST;
					Createlist( p->value.hlink, hsub );
				}
			}

			else return 0;
		}
		p->tlink=NULL;
	}
	return 1;
}
//----------------------------------------------------------
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);
		str1[n-i]=0;
		return 1;
	}
//#
	else if(k!=0)
		return 0;
	
	else
	{
		strcpy(hstr1, str1);
		str1[0]=0; 
		return 1;
	}
}
//------------------------------
GenList::~GenList(){
	Remove(first);
}

void GenList::Remove(GenListNode *ls){
	GenListNode *p;
	if (ls == NULL)	return;
	p = ls->tlink;
	while (p)
	{
		GenListNode *q = p->tlink;
		if (p->utype == LST)	Remove(p->value.hlink);
		delete p;
		p = q;
	}
	delete ls;

}

//----------------------------------------------------------------------------------------------------------求深度

int GenList::depth()
{
	return depth(first);
}

int GenList::depth(GenListNode *ls)
{
	if(ls->tlink==NULL)
		return 1;
	GenListNode *temp=ls->tlink;
	int m=0;
	while(temp!=NULL)
	{
		if(temp->utype==LST)
		{
			int n=depth( temp->value.hlink );
			if(m<n)
				m=n;
		}
		temp=temp->tlink;
	}
	return m+1;
}

//-----------------------------------------------------------------
void GenList::print()
{
 print(first) ;
 cout<<endl;
 cout<<"2"<<endl;
}

void GenList::print(GenListNode *ls){
 if(ls->tlink==NULL)
  cout << "()" << endl ;
 while(ls!=NULL)
 {
  switch( ls->utype )
  {
  case HEAD:
   {
    cout << "(" ;
    break ;
   }
  case INTER:
   {
    cout<<ls->value.intgrinfo;
    if(ls->tlink!=NULL)
     cout << "," ;
    break ;
   }
  case CH:
   {
    cout <<"\'" << ls->value.charinfo << "\'" ;
    if(ls->tlink!=NULL)
     cout << "," ;
    break ;
   }
  case LST:
   {
    print(ls->value.hlink);
    if( ls->tlink != NULL )
     cout << "," ;
    break ;
   }
  default:  break ;
  }
  ls = ls->tlink ;
 }
 cout << ")" ;
 
}
//***************************************
int main(int argc, char* argv[]){
	GenList glist;
	char str[]="(2,(\'d\'))";
	glist.Createlist(str);
	glist.print();
	return 0;
}