广义表是一种递归数据结构，其递归运算为求表头和求表尾运算，下面通过几个例子介绍利用这些递归运算进行广义表递归算法设计的方法。
【例4-3】设计一个算法，求广义表g中所有原子的个数。
解：本例的递归模型如下。
0 当g=NULL时
f(g)= 1 当g为原子时
f(head(g))+f(tail(g)) 其他情况
对应的递归算法如下：
int AtomCount(GLNode *g)
{
if(g->val.sublist==NULL) /*为空表时返回0*/
return(0);
else if(g->tag==0) /*为原子时返回1*/
return(1);
else /*其他情况*/
return(AtomCount(head(g))+AtomCount(tail(g)));
}
【例4-4】设计一个算法，将广义表g中所有值为x的原子改为y。
解：本例的递归模型如下。
NULL 当g=NULL时
f(g)= g->val.data=y 当g为原子节点且值为x
Append(f(head(g),x,y),f(tail(g),x,y)) 当g为非空子表时
对应的递归算法如下：
GLNode *Change(GLNode *g,char x,char y)
{
GLNode *h,*t,*g1;
if(g==NULL)
return NULL;
if(g->tag==0 && g->val.data==x) /*为原子且原子值为x*/
g->val.data=y;
if(g->tag==1 && g->val.sublist!=NULL) /*为非空子表*/
{
h=head(g);
t=tail(g);
g1=Append(Change(h,x,y),Change(t,x,y));
return(g1);
}
}
【例4-5】设计一个算法，求出从广义表g中提取出原子x的所有求表头表尾的操作步骤。
解：设计一个SqList类型的顺序表用于存放操作串。Findop()算法用于在广义表g中寻找值为x的原子，其递归模型如下：
不做任何事情返回0 当g=NULL时
f(g,x,s,op)=: 将s复制到op，返回1 当g为原子节点且值为x
在head(g)中查找x，未找到时再到tail(g)中查找 当g为非空子表时
Dispop()算法用于调用Findop()算法并输出操作过程。对应的算法如下：
typedef struct snode
{
char data[MaxSize]; /*存放操作串，h表示取表头，t表示取表尾*/
int len; /*存放操作串的实际长度*/
} SqList;
int Findop(GLNode *g,char x,SqList s,SqList &op)
{
int i,p;
GLNode *h,*t;
if(g==NULL)
return(0);
if(g->tag==0)
if (g->val.data==x) /*为原子且原子值为x*/
{
for (i=0;i<s.len;i++)
op.data[i]=s.data[i];
op.len=s.len;
return(1);
}
else return (0);
if(g->tag==1 && g->val.sublist!=NULL) /*为非空子表*/
{
h=head(g);
s.data[s.len]='h';s.len++; /*将当前取表头操作添加到s中*/
p=Findop(h,x,s,op);
s.len--; /*回溯*/
if(p==0) /*在表头中未找到时再到表尾中查找*/
{
s.data[s.len]='t';s.len++; /*将当前取表尾操作添加到s中*/
t=tail(g);
p=Findop(t,x,s,op);
s.len--; /*回溯*/
return(p);
}
}
else return NULL;
}
void Dispop(GLNode *g,char x) /*输出操作过程*/
{
int i;
SqList s,op;
s.len=0;
if(Findop(g,x,s,op)==1) /*找到x时输出*/
{
printf("操作过程:");
for (i=op.len-1;i>=0;i--) /*反向输出操作过程*/
if (op.data[i]=='h')
printf("head[");
else if(op.data[i]='t')
printf("tail[");
printf("g");
for(i=0;i<op.len;i++) /*输出对应的]括号*/
printf("]");
printf("=%c\n",x);
}
else printf("在广义表中未找到%c\n",x);
}
设计一个主函数：
void main()
{
GLNode *g;
char *str="(a,(b,c,d),((e,f),g))";
g=CreatGL(str);
printf("广义表g:");DispGL(g);printf("\n");
Dispop(g,'f');
}
本程序执行结果如下：
广义表g:(a,(b,c,d),((e,f),g))
操作过程:head[tail[head[head[tail[tail[g]=f