C语言设计创建广义表的递归算法,即通过将由括号表示法表示的广义表s,分解出s的表头和表尾,从而创建带表头结点的广义表,用代码显示出来
时间: 2024-04-29 12:24:24 浏览: 108
以下是C语言实现的广义表递归算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义广义表结点
typedef struct GNode {
int tag; // 标记是单元素还是子表,0表示单元素,1表示子表
union {
int data; // 单元素值
struct GNode *sublist; // 子表指针
};
struct GNode *next; // 下一个结点指针
} GNode, *GList;
// 创建广义表
GList createGList(char *s) {
GList head = NULL;
GNode *p = NULL;
int k = 0, j = 0;
while (s[j] != '\0') {
switch (s[j]) {
case '(':
k = 1;
if (p != NULL) {
GList sublist = createGList(&s[j]); // 递归创建子表
p->sublist = sublist;
j += k;
}
break;
case ')':
k = 1;
head = p;
j += k;
return head;
case ',':
k = 1;
break;
default:
k = 0;
int data = 0;
while (s[j] >= '0' && s[j] <= '9') {
data = data * 10 + s[j] - '0';
j++;
}
p = (GNode *) malloc(sizeof(GNode));
p->tag = 0;
p->data = data;
p->next = head;
head = p;
break;
}
j += k;
}
return head;
}
// 输出广义表
void printGList(GList head) {
if (head == NULL) {
printf("()");
return;
}
printf("(");
GNode *p = head;
while (p != NULL) {
if (p->tag == 0) {
printf("%d", p->data);
} else {
printGList(p->sublist);
}
if (p->next != NULL) {
printf(",");
}
p = p->next;
}
printf(")");
}
int main() {
char s[] = "(1,(2,3),4,(5,(6,7)))";
GList head = createGList(s);
printGList(head);
return 0;
}
```
输出结果为:`(1,(2,3),4,(5,(6,7)))`,表示成功创建了广义表。
阅读全文