算法与数据结构之广义表

#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!='\0')
{
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(" *************欢迎使用广义表的运算系统****************\n");
printf("请输入一个广义表:(例如(b,(b,a,(#),d),((a,b),c,((#)))))\n");
gets(a);
g=creategl(p);
printf("广义表已建好\n");
while(1)
{
printf("请选择:");
printf(" 1求广义表的长度\n");
printf(" 2求广义表的深度\n");
printf(" 3输出广义表\n");
printf(" 4求广义表中的最大原子\n");
printf(" 5退出\n");
scanf("%d",&m);
switch(m)
{
case 1:printf("广义表的长度为:%d\n",gllength(g));break;
case 2:printf("广义表的深度为:%d\n",gldepth(g));break;
case 3:printf("广义表为:");dispgl(g);printf("\n");break;
case 4:printf("广义表中的最大原子为:%c\n",maxatom(g));break;
case 5:exit(0);
default:printf("输入错误\n");
}
}
}