//创建广义表
//算法思路: 从字符序列中分离出左部,右部,依次为左部和右部建立存储
char s[61]; //设字符序列长度不超过60
//eg:
// (a,b),(c),d,((e,f),g)
// | | |
// a i b
int sever(int a,int b)
{//从Sa->Sb中分离出左部,函数值为左部后面一个字符的下标
int i,k;
if(a>b) return 0; //a,b的大小弄错了
k=0;
i=a; //i是遍历的指针
do
{
switch(s[i])
{
case '(': k++;break; //k=1
case ')': k--; //K=0 .这个时候while可以结束
}
i++;
} while (!((k==0)&&(s[i]==',')||(i>b)));
return i;
}
//eg:
// ((a,b),(c),d,((e,f),g))
// | |
// i j
void create(node* &p,int i,int j)
{//根据Si~Sj 创建链表,返回表头指针p
int k;
node *q;
if(i>j)
{
return NULL;//如果i,j的大小的不对.
}
else
{//生成一个新的节点
p=new node();
if(i==j)
{//如果i,j指向一个原子节点,生成的节点存放原子值
p->tag=0;
p->atom=s[i];
}
else
{//新生成的节点作表头节点
p->tag=1;
p->next=NULL;
//去掉左右括号
i++;
j--;
//分离出左部和右部
k=sever(i,j); //k 左部的下一个字符
//递归处理左部
create(p->head,i,k-1); //p->head为返回的左部建立的链表的头指针
//递归处理右部
q=p->head; //q为左部的指针
while(q!=NULL)
{
i=k+1;
k=sever(q->next,i,k-1);
q=q->next;
}
}
}
}
//判断两个广义表是否相等
//算法思路:使用递归的方法,设Si是广义表S的第i个元素,Ti是广义表T的第i个元素
int equal(node* s,node* t)
{//s t是两个广义表的表头指针
int r=0;
if((s==NULL)&&(t==NULL))
{//如果两个广义表都是空的,就相等
r=1;
}
else
{
if((s!=NULL)&&(t!=NULL))
{//如果两个广义表都不是空的
if(s->tag == t->tag)
{
switch(s->tag)
{
case 0: //如果都是原始节点,并且值相等,next相等,就是相等的
r=((s->atom==t->atom)&&(equal(s->next,t->next)==1));
break;
case 1: //如果是子表,就判断head(它的下一级节点),next(它的同级别节点)是否相同.
r=(equal(s->head,t->head)==1)&&(equal(s->next,t->next)==1);
}
}
}
}
return r;
}