数据结构中 编写判断两个广义表的递归算法

有空给你编。

#include<stdio.h>
#include<malloc.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->val.data=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;
}

bool same(GLNode *h1,GLNode *h2)
{
bool mark;
if(h1==h2)
return true;
else if(h1->tag==h2->tag)
{
if(h1->tag==0)
{
if(h1->val.data==h2->val.data)
mark=true;
else
mark=false;
}
if(h1->tag==1)
mark=same(h1->val.sublist,h2->val.sublist);
if(mark)
{
if(!(h1->link==NULL && h2->link==NULL))
{
if(h1->link!=NULL && h2->link!=NULL)
mark=same(h1->link,h2->link);
else
return false;
}
}
if(mark==false)
return false;
else if(mark)
return true;
}
return false;
}

void main()
{
char *s1="( )",*s2="(a,(b,c))";
GLNode *g1,*g2;
g1=CreateGL(s1);
g2=CreateGL(s2);
printf("判断两个广义表是否相等:%s\n",same(g1,g2)?"两个广义表相等":"两个广义表不相等");
}