请写出判断两个广义表是否相等的递归算法,如果两个广义表相等,则输出1,否则输出0。如A=((a)),B=((a)),则A=B,输出1。要求输入的广义表采用链式存储结构存储,并基于链式存储结构编写递归函数。用c语言实现
时间: 2023-11-24 07:08:22 浏览: 72
判别两个广义表是否相等的递归算法
4星 · 用户满意度95%
假设广义表的链式存储结构如下:
```c
struct node {
char data;
struct node *sublist;
struct node *next;
};
typedef struct node *GList;
```
其中,data表示当前节点的元素,sublist指向当前节点的子表,next指向下一个元素或子表。
判断两个广义表是否相等的递归算法如下:
```c
int isEqual(GList A, GList B) {
if (A == NULL && B == NULL) { // 当A、B都为空时,两个广义表相等
return 1;
}
else if (A == NULL || B == NULL) { // 当A、B其中一个为空时,两个广义表不相等
return 0;
}
else if (A->data != B->data) { // 当A、B当前节点的元素不等时,两个广义表不相等
return 0;
}
else if (A->sublist == NULL && B->sublist == NULL) { // 当A、B当前节点均没有子表时,比较下一节点
return isEqual(A->next, B->next);
}
else if (A->sublist == NULL || B->sublist == NULL) { // 当A、B其中一个节点有子表,另一个没有时,两个广义表不相等
return 0;
}
else { // 当A、B当前节点均有子表时,递归比较子表
return isEqual(A->sublist, B->sublist) && isEqual(A->next, B->next);
}
}
```
其中,第1个判断是当两个广义表均为空时,它们相等;第2个判断是其中一个广义表为空时,两个广义表不相等;第3个判断是当前节点的元素不相等时,两个广义表不相等;第4个判断是当前节点均没有子表时,比较下一个节点;第5个判断是其中一个节点有子表,另一个节点没有子表时,两个广义表不相等;最后一个判断是当前节点均有子表时,递归比较子表,且比较下一个节点。
阅读全文