generalizedlist.c

数据结构学习中的广义表

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define OK     1;
#define ERORR  0;

typedef enum{ ATOM, GLIST }ETag;

struct _GLNode;

typedef union _UNode {
	char value;
	struct _GLNode *SubGL;
}UNode;

typedef struct _GLNode {
	ETag Tag;
	UNode Data;
	struct _GLNode *next;
}GLNode;

GLNode *CreatGList( char *str, int *idx );
GLNode *PrintGList(GLNode *GL);
int Length(GLNode *GL );
int FreeGList( GLNode *GL );
GLNode *CopyGList(GLNode *GL);
int Depth( GLNode *GL );
void main()
{
	int i = 0;
	char str[] = "()";
	GLNode GL;
    GLNode *GL1;

	GL =  *CreatGList( str, &i );
    PrintGList( &GL );
	GL1 = CopyGList(&GL);
	PrintGList( GL1 );
	printf("%d\n", Length( &GL) );
	printf("%d\n", Depth( &GL ) );
	FreeGList( &GL );
	GL.Data.SubGL = NULL;

}

GLNode *CreatGList( char *str, int *idx ){ //(a,b(c,d),e)
	GLNode *GL, *pt, *pt1;
	int i = *idx;
	if( str[i] == 0 )return NULL;
	GL = ( GLNode* )calloc( 1, sizeof(GLNode) );
	if( str[i] != '(' ){ GL->Tag = ATOM; GL->Data.value = str[i];  }
	else{
		GL->Tag = GLIST;
		i++;
		pt = NULL;
		while( str[i] != ')' ){
			pt1 = CreatGList( str, &i );
			if(pt == NULL)GL->Data.SubGL = pt1;
			else pt->next = pt1;
			pt = pt1;
			if(str[i] == ',')i++;
		}
		i++;
	}
	*idx = i + 1;
	return GL;
}

GLNode *PrintGList(GLNode *GL){
	GLNode *pt;
	
	if( GL == NULL )return 0;
	
	if( GL->Tag == ATOM )printf( "%c", GL->Data );	
	else{
		printf("(");
		for( pt = GL->Data.SubGL; pt != NULL; pt = pt->next ){
			if( pt->Tag == GLIST )PrintGList( pt );
			else printf( "%c", pt->Data );
            if( pt->next != NULL )printf(",");		
		}
		printf(")");
	}

	return GL;
}

int Length(GLNode *GL ){   
	GLNode *pt;
    int Num = 0;
    
	if (GL->Tag == GLIST)pt = GL->Data.SubGL;
	
	while( pt != NULL ){
	    if( pt->Tag == GLIST )Num = Num - 1 + Length( pt );
        
		pt =pt->next;
		Num++;
	}
    return Num;
}

int Depth( GLNode *GL ){
	int Num = 0, Temp = 0;
	GLNode *pt;
	pt = GL;
	//if( pt->Tag == ATOM )return 0;
	do{
		if(pt->Tag == GLIST ){
			Temp = Depth( pt->Data.SubGL );
			Num = ( Temp > Num ? Temp : Num ) ;
		}
		pt = pt->next;
	}while( pt != NULL );
	
	return (Num+1);
}

int FreeGList( GLNode *GL ){
	GLNode *pt, *pt1;
	if( GL == NULL )return OK;
	if( GL->Tag  == GLIST )   pt = GL->Data.SubGL; 
	
	while( pt != NULL ){
		pt1 = pt;
		pt = pt->next;
		if( pt1->Tag == GLIST )FreeGList( pt1 );
		free(pt1);
	}
	return OK;
}

GLNode *CopyGList(GLNode *GL)      
{
	GLNode *NewGL, *Tail, *pt, *pt1;
	if (GL == NULL) return NULL;
    NewGL = (GLNode *) calloc(1, sizeof(GLNode));
    NewGL->Tag = GL->Tag;    
	NewGL->Data = GL->Data;
    if (GL->Tag == ATOM) return NewGL;
    Tail = NULL;
    for (pt = GL->Data.SubGL; pt != NULL; pt = pt->next) {
		if (pt->Tag == GLIST) pt1 = CopyGList(pt);
	    else {
	        pt1 = (GLNode *) calloc(1, sizeof(GLNode));
	        pt1->Tag = pt->Tag; 
			pt1->Data = pt->Data;
		}
		if (Tail == NULL) NewGL->Data.SubGL = pt1;
        else Tail->next = pt1;
        Tail = pt1;
	}
    return NewGL;
}