请写出判断两个广义表是否相等的递归算法,如果两个广义表相等,则输出1,否则输出0。如A=((a)),B=((a)),则A=B,输出1。要求输入的广义表采用链式存储结构存储,并基于链式存储结构编写递归函数。
时间: 2023-11-24 13:08:23 浏览: 98
我们可以采用递归的方式来判断两个广义表是否相等,具体算法如下:
1. 如果两个广义表都为空,则它们相等,返回1。
2. 如果两个广义表的类型不同,则它们不相等,返回0。
3. 如果两个广义表的类型相同并且都为原子,则比较它们的值是否相等,如果相等返回1,否则返回0。
4. 如果两个广义表的类型相同并且都为子表,则递归比较它们的子表是否相等,如果子表都相等,则返回1,否则返回0。
根据上述算法,可以编写如下的递归函数:
```
int equal(GLNode *A, GLNode *B) {
if (A == nullptr && B == nullptr) {
return 1;
} else if (A == nullptr || B == nullptr) {
return 0;
} else if (A->tag != B->tag) {
return 0;
} else if (A->tag == ATOM && B->tag == ATOM) {
return strcmp(A->atom, B->atom) == 0;
} else {
GLNode *p = A->hp, *q = B->hp;
while (p != nullptr && q != nullptr) {
if (!equal(p, q)) {
return 0;
}
p = p->tp;
q = q->tp;
}
return p == nullptr && q == nullptr;
}
}
```
其中,GLNode是广义表节点的结构体,它包含一个tag字段表示节点的类型(ATOM表示原子,LIST表示子表),以及一个union结构体用于存储原子值或子表的头指针和尾指针。hp表示子表的头指针,tp表示子表的尾指针。
上述递归函数的参数为两个广义表节点的指针A和B,返回值为1或0,表示它们是否相等。在函数中,首先判断A和B是否都为空,如果是则返回1;然后判断A和B的类型是否相同,如果不同则返回0;接着判断A和B是否都为原子,如果是则比较它们的值是否相等;最后,如果A和B都为子表,则依次比较它们的子表是否相等。
阅读全文