两个广义表是否相等的递归算法用c实现,采用链式存储结构存完整代码
时间: 2024-05-16 16:18:16 浏览: 15
以下是用链式存储结构实现两个广义表相等判断的递归算法的C代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef enum {
ATOM,
LIST
} ElemTag;
typedef char AtomType;
struct GLNode;
typedef struct {
ElemTag tag;
union {
AtomType atom;
struct GLNode *sublist;
};
} ElemType;
typedef struct GLNode {
ElemType data;
struct GLNode *next;
} GLNode, *GList;
int equal(GList L1, GList L2);
int main() {
// 两个广义表分别为 (a, b, (c, d)) 和 ((a, b), c, d)
GLNode *L1 = (GLNode*)malloc(sizeof(GLNode));
L1->data.tag = LIST;
L1->data.sublist = (GLNode*)malloc(sizeof(GLNode));
L1->data.sublist->data.tag = ATOM;
L1->data.sublist->data.atom = 'a';
L1->next = (GLNode*)malloc(sizeof(GLNode));
L1->next->data.tag = LIST;
L1->next->data.sublist = (GLNode*)malloc(sizeof(GLNode));
L1->next->data.sublist->data.tag = ATOM;
L1->next->data.sublist->data.atom = 'b';
L1->next->next = (GLNode*)malloc(sizeof(GLNode));
L1->next->next->data.tag = LIST;
L1->next->next->data.sublist = (GLNode*)malloc(sizeof(GLNode));
L1->next->next->data.sublist->data.tag = LIST;
L1->next->next->data.sublist->data.sublist = (GLNode*)malloc(sizeof(GLNode));
L1->next->next->data.sublist->data.sublist->data.tag = ATOM;
L1->next->next->data.sublist->data.sublist->data.atom = 'c';
L1->next->next->data.sublist->data.sublist->next = (GLNode*)malloc(sizeof(GLNode));
L1->next->next->data.sublist->data.sublist->next->data.tag = ATOM;
L1->next->next->data.sublist->data.sublist->next->data.atom = 'd';
L1->next->next->data.sublist->next = NULL;
GLNode *L2 = (GLNode*)malloc(sizeof(GLNode));
L2->data.tag = LIST;
L2->data.sublist = (GLNode*)malloc(sizeof(GLNode));
L2->data.sublist->data.tag = LIST;
L2->data.sublist->data.sublist = (GLNode*)malloc(sizeof(GLNode));
L2->data.sublist->data.sublist->data.tag = ATOM;
L2->data.sublist->data.sublist->data.atom = 'a';
L2->data.sublist->next = (GLNode*)malloc(sizeof(GLNode));
L2->data.sublist->next->data.tag = LIST;
L2->data.sublist->next->data.sublist = (GLNode*)malloc(sizeof(GLNode));
L2->data.sublist->next->data.sublist->data.tag = ATOM;
L2->data.sublist->next->data.sublist->data.atom = 'b';
L2->next = (GLNode*)malloc(sizeof(GLNode));
L2->next->data.tag = ATOM;
L2->next->data.atom = 'c';
L2->next->next = (GLNode*)malloc(sizeof(GLNode));
L2->next->next->data.tag = ATOM;
L2->next->next->data.atom = 'd';
L2->next->next->next = NULL;
printf("%d\n", equal(L1, L2)); // 输出 1
return 0;
}
int equal(GList L1, GList L2) {
if (L1 == NULL && L2 == NULL) {
return 1;
} else if (L1 == NULL || L2 == NULL) {
return 0;
}
if (L1->data.tag == ATOM && L2->data.tag == ATOM) {
return L1->data.atom == L2->data.atom;
} else if (L1->data.tag == LIST && L2->data.tag == LIST) {
GList p1 = L1->data.sublist;
GList p2 = L2->data.sublist;
while (p1 != NULL && p2 != NULL) {
if (!equal(p1, p2)) {
return 0;
}
p1 = p1->next;
p2 = p2->next;
}
return p1 == NULL && p2 == NULL;
} else {
return 0;
}
}
```
注:以上广义表的存储方式为单链表,头结点不存储数据。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)