请写出判断两个广义表是否相等的递归算法,如果两个广义表相等,则输出1,否则输出0。如A=((a)),B=((a)),则A=B,输出1。要求输入的广义表采用链式存储结构存储,并基于链式存储结构编写递归函数。
时间: 2023-11-24 13:07:36 浏览: 51
算法如下:
1. 如果两个广义表都为空,则它们相等,返回1。
2. 如果两个广义表中一个为空,另一个不为空,则它们不相等,返回0。
3. 如果两个广义表的表头元素不相等,则它们不相等,返回0。
4. 如果两个广义表的表头元素相等,则继续递归比较它们的子表,如果所有子表都相等,则它们相等,返回1,否则返回0。
以下是基于链式存储结构的递归函数实现:
```
typedef struct GLNode {
int tag; // 标志域,0表示原子,1表示子表
union {
char data; // 原子结点的值域
struct GLNode *sublist; // 指向子表的指针
} atom_sublist;
struct GLNode *next; // 指向后继结点的指针
} GLNode, *GList;
int equal(GList A, GList B) {
if (A == NULL && B == NULL) {
return 1;
} else if (A == NULL || B == NULL) {
return 0;
} else if (A->tag != B->tag) {
return 0;
} else if (A->tag == 0 && B->tag == 0) {
return A->atom_sublist.data == B->atom_sublist.data;
} else {
GList p = A->atom_sublist.sublist;
GList q = B->atom_sublist.sublist;
while (p != NULL && q != NULL) {
if (!equal(p, q)) {
return 0;
}
p = p->next;
q = q->next;
}
return p == NULL && q == NULL;
}
}
```
其中,tag表示广义表的类型,0表示原子,1表示子表。如果tag为0,data表示原子结点的值域;如果tag为1,sublist表示指向子表的指针。next表示指向后继结点的指针。函数equal递归地比较两个广义表是否相等。