数据结构用孩子兄弟表示法创建广义表代码实现
时间: 2024-03-13 20:19:00 浏览: 34
孩子兄弟表示法是一种常用的树的存储结构,可以用于创建广义表。广义表是一种可以包含原子和子表的数据结构。
下面是使用孩子兄弟表示法创建广义表的代码实现:
```C++
#include <iostream>
using namespace std;
// 定义广义表节点结构体
struct GNode {
char data; // 数据域
GNode *firstChild; // 指向第一个子节点的指针
GNode *nextSibling; // 指向下一个兄弟节点的指针
};
// 创建广义表函数,返回根节点指针
GNode* createGList() {
char c;
cin >> c;
if (c == '#') { // 空表
return NULL;
} else if (c == '(') { // 子表
GNode *p = new GNode;
p->firstChild = createGList(); // 递归创建子表
p->nextSibling = createGList(); // 递归创建兄弟节点
return p;
} else { // 原子
GNode *p = new GNode;
p->data = c;
p->firstChild = NULL;
p->nextSibling = createGList(); // 递归创建兄弟节点
return p;
}
}
// 遍历广义表函数
void traverseGList(GNode *p) {
if (p == NULL) {
cout << "#";
} else if (p->firstChild == NULL) { // 原子
cout << p->data;
traverseGList(p->nextSibling);
} else { // 子表
cout << "(";
traverseGList(p->firstChild);
cout << ")";
traverseGList(p->nextSibling);
}
}
int main() {
GNode *root = createGList(); // 创建广义表
traverseGList(root); // 遍历广义表
return 0;
}
```
在上面的代码中,我们定义了 `GNode` 结构体作为广义表节点,其中包含数据域 `data`、指向第一个子节点的指针 `firstChild` 和指向下一个兄弟节点的指针 `nextSibling`。然后我们使用递归的方式创建广义表,并且使用递归的方式遍历广义表。
例如,我们可以输入 `(a(b(c)d)e)#` 来创建广义表,并且输出 `((a((b(c)#)d)#)e)#)` 来遍历广义表。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![cpp](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)
![](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)
![](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)