设计算法,对以字符串形式表示的广义表,构造出其相应的链表存储结构
时间: 2024-05-14 15:14:15 浏览: 12
1. 定义节点结构体
```
struct Node {
char data;
Node *next;
Node *sublist;
};
```
2. 定义栈结构体
```
struct Stack {
Node *top;
};
```
3. 定义函数`createList`,利用栈来构造链表结构
```
Node* createList(string s) {
Stack stack;
stack.top = NULL;
Node *head, *p;
head = p = NULL;
for (int i = 0; i < s.length(); i++) {
char ch = s[i];
if (ch == '(') {
Node *node = new Node;
node->data = ch;
node->sublist = NULL;
node->next = NULL;
if (p == NULL) {
head = p = node;
} else {
p->sublist = node;
p = node;
}
stack.top = node;
} else if (ch == ')') {
stack.top = stack.top->next;
p = p->next;
} else if (ch == ',') {
continue;
} else {
Node *node = new Node;
node->data = ch;
node->sublist = NULL;
node->next = NULL;
if (p == NULL) {
head = p = node;
} else {
p->next = node;
p = node;
}
if (stack.top->sublist == NULL) {
stack.top->sublist = node;
} else {
Node *q = stack.top->sublist;
while (q->next != NULL) {
q = q->next;
}
q->next = node;
}
}
}
return head;
}
```
4. 示例
```
string s = "(A,B,(C,D,(E,F)))";
Node *head = createList(s);
```
5. 链表结构
```
head -> A -> B -> C -> D -> E -> F
|
V
NULL
```