genlist.cpp

数据结构中广义表的C++源码

#include<iostream.h>
#include<string.h>
#include<cstdlib>

class GenList;

class GenListNode{
	friend class GenList;
private:
	int utype; //0,1,2,3
	union{
		int		intinfo;
		char	charinfo;
		GenListNode* hlink;
	}value;
	GenListNode* tlink;
public:
	GenListNode(){}
};


class GenList{
private:
	GenListNode *first;
	int Sever( char* &hstr,char * &s );
	void strncpy1( char* &hstr,char* &s,int comma );
	GenListNode* CreatList( char* s );
	void show( GenListNode* ls );
public:
	void Creat( char* s );
	void Display( void );
};

int GenList::Sever( char* &hstr,char* &s ){
	char ch=s[0];
	int n=strlen( s );
	
	int i=0,k=0,comma=-1;
	while( i<n && (ch!=',' || k!=0) ){
		if( ch=='(' )	k++;
		else 
			if( ch==')' )	k--;
		i++;
		ch=s[i];
		if( k==1 && comma==-1 && ch==',' )
			comma=i;		
	}
	if( k!=0 ){
		cout<<"括号不配对!    退出程序!"<<endl;
		exit(1);
	}

	if( comma==-1 )	comma=n;
	strncpy1( hstr,s,comma );

	if( strlen(hstr)>3 )
		return 3;
	else{
		if( hstr[0]<='9' && hstr[0]>='0' )
			return 1;
		if( hstr[0]<='z' && hstr[0]>='a' )
			return 2;
	}
	return 1;
}

void GenList::strncpy1( char* &hstr,char* &s,int comma ){
	int n=strlen(s);
	hstr=new char[n];
	for( int t=0,i=1;i<comma;i++ )
		hstr[t++]=s[i];
	hstr[t]='\0';
	for( t=1,i=comma+1;i<n;t++,i++ )
		s[t]=s[i];
	s[t]='\0';
}

void GenList::Creat( char* s ){
	first=CreatList( s );
}

GenListNode* GenList::CreatList( char* s ){
	GenListNode *ls,*head;
	head=ls=new GenListNode();
	ls->utype=0;
	if( strlen(s)<=2 )
		ls->tlink=NULL;
	else{
		char* sub;
		while( strlen(s)>2 ){
			ls=ls->tlink=new GenListNode();			
			ls->utype=Sever(sub,s);
			switch( ls->utype ){
			case 1:ls->value.intinfo=atoi(sub);break;
			case 2:ls->value.charinfo=sub[0];break;
			case 3:ls->value.hlink=CreatList( sub );
			}
		}
		ls->tlink=NULL;
	}
	return head;
}

void GenList::Display( void ){
	show( first );
}

void GenList::show( GenListNode* ls ){
	while( ls!=NULL ){
		switch( ls->utype ){
			case 0:cout<<"(  ";	break;
			case 1:cout<<ls->value.intinfo;cout<<" , ";		break;
			case 2:cout<<ls->value.charinfo;cout<<" , ";	break;
			case 3:show( ls->value.hlink );		break;
		}
		ls=ls->tlink;
	}
	cout<<" ) ";
}