#include<stdio.h>  
#include<malloc.h>  
#include<windows.h>  
typedef char elemtype;  
typedef struct lnode //广义表的定义  
{  
int tag;  
union  
{  
elemtype data;  
struct lnode *sublist;  
}val;  
struct lnode *link;  
}glnode;  
  
glnode *creategl(char *&s) //建立广义表的链式存储结构  
{  
glnode *g;  
char ch=*s++;  
if(ch!="")  
{  
g=(glnode *)malloc(sizeof(glnode));  
if(ch=="(")  
{  
g->tag=1;  
g->val.sublist=creategl(s);  
}  
else if(ch==")")  
g=NULL;  
else if(ch=="#")  
g=NULL;  
else  
{  
g->tag=0;  
g->val.data=ch;  
}  
}  
else  
g=NULL;  
ch=*s++;  
if(g!=NULL)  
if(ch==",")  
g->link=creategl(s);  
else  
g->link=NULL;  
return g;  
}  
  
int gllength(glnode *g) //求广义表的长度  
{  
int n=0;  
glnode *g1;  
g1=g->val.sublist;  
while(g1!=NULL)  
{  
n++;  
g1=g1->link;  
}  
return n;  
}  
  
int gldepth(glnode *g) //求广义表的深度  
{  
glnode *g1;  
int max=0,dep;  
if(g->tag==0)  
return 0;  
g1=g->val.sublist;  
if(g1==NULL)  
return 1;  
while(g1-NULL)  
{  
if(g1->tag==1)  
{  
dep=gldepth(g1);  
if(dep>max)  
max=dep;  
}  
g1=g1->link;  
}  
return(max+1);  
}  
  
elemtype maxatom(glnode *g) //求广义表中的最大原子  
{  
elemtype max1,max2;  
if(g!=NULL)  
{  
if(g->tag==0)  
{  
max1=maxatom(g->link);  
return(g->val.data>max1?g->val.data:max1);  
}  
else  
{  
max1=maxatom(g->val.sublist);  
max2=maxatom(g->link);  
return(max1>max2?max1:max2);  
}  
}  
else  
return 0;  
}  
void dispgl(glnode *g) //输出广义表  
{  
if(g!=NULL)  
{  
if(g->tag==0)  
printf("%c",g->val.data);  
else  
{  
printf("(");  
if(g->val.sublist==NULL)  
printf("#");  
else  
dispgl(g->val.sublist);  
printf(")");  
}  
if(g->link!=NULL)  
{  
printf(",");  
dispgl(g->link);  
}  
}  
}  
  
void main()  
{  
glnode *g;  
char a[100],*p=a;  
int m;  
printf(" *************欢迎使用广义表的运算系统****************
");  
printf("请输入一个广义表:(例如(b,(b,a,(#),d),((a,b),c,((#)))))
");  
gets(a);  
g=creategl(p);  
printf("广义表已建好
");  
while(1)  
{  
printf("请选择:");  
printf(" 1求广义表的长度
");  
printf(" 2求广义表的深度
");  
printf(" 3输出广义表
");  
printf(" 4求广义表中的最大原子
");  
printf(" 5退出
");  
scanf("%d",&m);  
switch(m)  
{  
case 1:printf("广义表的长度为:%d
",gllength(g));break;  
case 2:printf("广义表的深度为:%d
",gldepth(g));break;  
case 3:printf("广义表为:");dispgl(g);printf("
");break;  
case 4:printf("广义表中的最大原子为:%c
",maxatom(g));break;  
case 5:exit(0);  
default:printf("输入错误
");  
}  
}  
}