[C++知识库]广义表（C++）

核心思想：
1.节点类中用一个标志域区别是表还是元素
2.节点类中使用联合体
3.广义表类中存放一个起始指针

1.创建

1.两个函数的形式，详见代码注释
2.两次接受输入，方便递归，见注释
3.通过递归时传参传tlink ,hlink指针，后面函数直接用他们创造结点，巧妙避开结点连接问题
4.输入格式：空表用#表示，每个之间加逗号，用分号表示结束
例如：a,(#),b,c,(d,(e));
（如果觉得对输入要求过高，可以使用一个字符串保存输入，然后加一个处理函数，把其他格式的输入转化为此输入，函数中读输入时从该字符串中读即可）

#include<bits/stdc++.h>
using namespace std;
class node
{
	int flag;//用来区别是原子还是表
	union
	{
		char data;//为原子时存放数据
		node* hlink;//为表时存放下一个表的指针
	};//联合体，其中的元素只能存在一个
	node* tlink;
public:
	friend class glist;
};
class glist
{
	node* first;
public:
	glist()
	{
		first = NULL;
	}

//创建广义表

	void creat_glist()
	{
		creat_glist(first);
	}//设置两个函数是因为主函数中不一定有first指针，第二个函数带指针参数是为了递归
	void creat_glist(node*& gs)
	{
		char a;
		cin >> a;
		if (a == '#')
		{
			gs = NULL;
		}//如果不加表示空表的符号话，当空表时，读入'）'的时候会进入else分支
		else if(a=='(')
		{
			gs = new node;
			gs->flag = 1;
			creat_glist(gs->hlink);
		}
		else
		{
			gs = new node;
			gs->flag = 0;
			gs->data = a;
		}
		cin >> a;//再加一个输入是为了递归回来后能进行后续的读入
		if (gs == NULL);
		else if (a == ',')
		{
			creat_glist(gs->tlink);
		}
		else if ((a == ')') || (a == ';'))
		{
			gs->tlink = NULL;
		}

	}
};
int main()
{
	glist a;
	a.creat_glist();
}