guangyibiao.txt

1、 基本操作包括： 创建、输出、求表深、求表长 2、 要求用户能够键入所要创建的广义表的形式

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

typedef struct lnode 

{ 

int tag; 
union 
{ 
char data; 
struct lnode *sublist; 
}val; 
struct lnode *link; 
}GLNode; 

//2、算法实现
//创建广义表
GLNode *GreatGL(char *s) 
{ 
GLNode *h;char ch; 
ch=*s; 
s++; 
if(ch!='\0') 
{ 
    h=(GLNode *)malloc(sizeof(GLNode)); 
       if(ch=='(') 
{ 
     h->tag=1; 
      h->val.sublist=GreatGL(s); 
} 
    else if(ch==')') 
    h->link=GreatGL(s); 
     else 
{ 
     h->tag=0; 
     h->val.data=ch; 
} 
} 
else h=NULL; 
ch=*s; 
s++; 
if(h!=NULL) 
if(ch==',') 
h->link=GreatGL(s); 
else  
h->link=NULL; 
return h; 
} 

//输出广义表
void DispGL(GLNode *g) 
{ 
if(g!=NULL) 
{ 
if(g->tag==1) 
{ 
printf("("); 
if(g->val.sublist==NULL) 
printf(" "); 
else 
DispGL(g->val.sublist); 
} 
else  
printf("%c",g->val.data); 
if(g->tag==1) 
printf(")"); 
if(g->link!=NULL) 
{ 
printf(","); 
DispGL(g->link); 
} 
} 
} 

//求表深
int GLDepth(GLNode *g) 
{ 
int max=0,dep; 
if(g->tag==0) 
return 0; 
g=g->val.sublist; 
if(g==NULL) 
return 1; 
while(g!=NULL) 
{ 
if(g->tag==1) 
{ 
dep=GLDepth(g); 
if(dep>max)  max=dep; 
} 
    g=g->link; 
} 
return max+1; 
} 

//求表长
int GLLength(GLNode *g) 
{ 
int n=0; 
g=g->val.sublist; 
while(g!=NULL) 
{ 
n++; 
g=g->link; 
} 
return n; 
} 


void main() 
{ GLNode *GL;
	int i;
char s[100]; 
char ch;
char *gl0; 
 
printf("please input a GL:"); 
i=0;
while((ch=getchar())!='\n')
{s[i]=ch;
i++;
}
	
gl0=s;
GL=GreatGL(gl0); 
DispGL(GL);
printf("\nThe depth of the GL is:%d",GLDepth(GL));
printf("\nThe length of the GL is:%d",GLLength(GL));
}