~~~
#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");
}
}
}
~~~