广义表是线性表的推广，也被称为列表（lists),广义表一般记作：
LS=（a₁，a₂，a₃，…，a_n）
其中，LS是表的名称，n是表的长度。在线性表的定义中，a_i (1<=i<=n）只能限于单个元素，但是在广义表中a_i可以是 单个元素，也可以是广义表，分别称为广义表LS的原子和子表。 当广义表非空时，第一个元素（a₁）被称为表头，其余元素（a₂，a₃，…，a _n）被称为子表。

广义表常用表示

• **E=()：**E是一个空表，其长度为0。
  • 广义表()和(())不同
    • 前者是长度为0的空表
    • 后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)
• **L=(a，b) ：**L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
• **A=(x，L)=(x，(a，b))：**A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
• **B=(A，y)=((x，(a，b))，y)：**B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
• **C=(A，B)=((x，(a，b))，((x，(a，b))，y))：**C的长度为2，两个元素都是子表。
• **D=(a，D)=(a，(a，(a，(…))))：**D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。

2️⃣ 两层广义表

3️⃣ 三层广义表

4️⃣ 四层广义表

广义表的深度

一个表的"深度"是指表展开后所含括号的层数。

• E=()：深度为1
• L=(a，b) ：深度为1
• A=(x，L)=(x，(a，b))：深度为2
• B=(A，y)=((x，(a，b))，y)：深度为3
• C=(A，B)=((x，(a，b))，((x，(a，b))，y))：深度为4
• D=(a，D)=(a，(a，(a，(…))))：深度为∞

广义表实现

• 创建广义表
• 遍历广义表
• 求广义表深度
• 删除广义表

---

📦 封装广义表节点

typedef struct GeneralizedList {
	bool flag;     // true：表节点， false：原子节点
	union {
		DataType data;    // 原节点，储存数据
		struct GeneralizedList* glist;    // 表节点，储存表
	};
	struct GeneralizedList* next;
}GList;

---

📑 创建广义表

• 空表定义：#
• 递归思路：
  • 返回值：void，参数：当前节点指针；
  • 递归结束条件：顺序执行完即可；
  • 单层递归逻辑：以(x,(a,b))为例
    • 从左到右，遍历，如果是#，说明是空表，直接赋值为null即可，如果是(，则需要创建表然后递归指向表节点，如果是x，即是原子节点，则创建原子节点，递归指向下一个节点；
    • 后面一种情况是，,、）这两个，如果是,，则说明递归去创建下一个节点，如果是)，则说明这一层表已经到头了，next指向NULL。

/*
	空表:#
	例子：
	(x,(a,b))
	((x,(a,b)),y,(z,f))
*/
void create_glist(GList** list)
{
	assert(list);

	char key;
	scanf_s("%c", &key, 1);
	// 从做到有开始读，首先有三种情况，#，(， 数据
	if (key == '#') {
		*list = NULL;
	}
	else if (key == '(') {
		*list = (GList*)calloc(1, sizeof(GList));
		assert(*list);
		(*list)->flag = true;
		create_glist(&((*list)->glist));
	}
	else {    // 读取数据
		*list = (GList*)calloc(1, sizeof(GList));
		assert(*list);
		(*list)->flag = false;
		(*list)->data = key;   // 读取数据
	}

	// 其他情况：','  ')'
	scanf_s("%c", &key, 1);

	if (*list == NULL) {  // 空表后面不进行任何操作，GList为NULL
		return;
	}
	else if (key == ',') {
		create_glist(&((*list)->next));
	}
	else if (key == ')' || key == '\n') {   // '\n' 是因为出入数据中有换行，这个时候就是的一个广义表创建完成
		(*list)->next = NULL;
	}
}

---

🏠 递归遍历

• 存储结构：以节点形式存储，

• 递归思路：

  • 返回值：void，参数：节点指针
  • 结束条件：从上到下顺序即可
  • 单层递归逻辑：
    • 如果是表节点，打印(，看这个表节点是否存储了节点，list->glist == NULL(没有，则打印#)，否则，就递归遍历表节点指向的这个表，后打印)
    • 如果不是表节点，则是原子节点，则打印数据即可
    • 打印，打印完数据或者）后，如果下一个next指向不为NULL，则打印,

// 遍历,脑子有广义表图形
void print_glist(GList* list)
{
	if (list->flag == true) {
		printf("(");
		if (list->glist == NULL)
			printf("#");
		else
			print_glist(list->glist);
		// 递归完成，这个时候就是一个表打印完成
		printf(")");
	}
	else {
		printf("%c", list->data);
	}

	if (list->next != NULL) {
		printf(",");
		print_glist(list->next);
	}
}

---

📘 求深度

递归思路：

• 返回值：最大层数，参数：节点
• 递归结束条件：节点为空，或者这个节点为原子节点
• 单层递归逻辑：
  • 一层一层，从左到右边
  • 下图是回溯过程：

// 场景：不为空、且是表节点，则递归
// 画图思路：先以一层为例返回
int depth_glist(GList* list)
{
	int max_depth = 0;
	if (list == NULL) {
		return 0;
	}

	if (list->flag == false) {
		return 0;
	}

	GList* t = list;
	while (t) {
		int res = depth_glist(list->glist);
		max_depth = max_depth > res ? max_depth : res;
		t = t->next;
	}
	return max_depth + 1;
}

---

❌ 删除节点

递归逻辑：

• 返回值：void，参数：节点指针
• 结束条件：从上到下顺序即可
• 单层递归逻辑：
  • 如果这个节点数据是要删除的数据，则按照链表删除方式即可，接着递归。
  • 如果不是，则判断：如果是表节点，则递归表，如果是原子节点，则递归下一个节点。

// 要修改指针的指向
// 递归条件：不相等、为表节点
void erase(GList** list, char k)
{
	if (*list == NULL) {
		return;
	}

	if ((*list)->data == k) {
		GList* t = *list;
		*list = (*list)->next;
		free(t);
		t = NULL;
		erase(list, k);
	}
	else {
		if ((*list)->flag == true) {
			erase(&(*list)->glist, k);
		}
		else {
			erase(&(*list)->next, k);
		}
	}
}

---

⏰ 总代码

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int DataType;

typedef struct GeneralizedList {
	bool flag;     // true：表节点， false：原子节点
	union {
		DataType data;    // 原节点，储存数据
		struct GeneralizedList* glist;    // 表节点，储存表
	};
	struct GeneralizedList* next;
}GList;


/*
	(x,(a,b))
	空表:#
	((x,(a,b)),y,(z,f))
*/
void create_glist(GList** list)
{
	assert(list);

	char key;
	scanf_s("%c", &key, 1);
	// 从做到有开始读，首先有三种情况，#，(， 数据
	if (key == '#') {
		*list = NULL;
	}
	else if (key == '(') {
		*list = (GList*)calloc(1, sizeof(GList));
		assert(*list);
		(*list)->flag = true;
		create_glist(&((*list)->glist));
	}
	else {    // 读取数据
		*list = (GList*)calloc(1, sizeof(GList));
		assert(*list);
		(*list)->flag = false;
		(*list)->data = key;   // 读取数据
	}

	// 其他情况：','  ')'
	scanf_s("%c", &key, 1);

	if (*list == NULL) {  // 空表后面不进行任何操作，GList为NULL
		return;
	}
	else if (key == ',') {
		create_glist(&((*list)->next));
	}
	else if (key == ')' || key == '\n') {   // '\n' 是因为出入数据中有换行，这个时候就是的一个广义表创建完成
		(*list)->next = NULL;
	}
}

// 遍历,脑子有广义表图形
void print_glist(GList* list)
{
	if (list->flag == true) {
		printf("(");
		if (list->glist == NULL)
			printf("#");
		else
			print_glist(list->glist);
		// 递归完成，这个时候就是一个表打印完成
		printf(")");
	}
	else {
		printf("%c", list->data);
	}

	if (list->next != NULL) {
		printf(",");
		print_glist(list->next);
	}
}

// 场景：不为空、且是表节点，则递归
// 画图思路：先以一层为例返回
int depth_glist(GList* list)
{
	int max_depth = 0;
	if (list == NULL) {
		return 0;
	}

	if (list->flag == false) {
		return 0;
	}

	GList* t = list;
	while (t) {
		int res = depth_glist(list->glist);
		max_depth = max_depth > res ? max_depth : res;
		t = t->next;
	}
	return max_depth + 1;
}

// 要修改指针的指向
// 递归条件：不相等、为表节点
void erase(GList** list, char k)
{
	if (*list == NULL) {
		return;
	}

	if ((*list)->data == k) {
		GList* t = *list;
		*list = (*list)->next;
		free(t);
		t = NULL;
		erase(list, k);
	}
	else {
		if ((*list)->flag == true) {
			erase(&(*list)->glist, k);
		}
		else {
			erase(&(*list)->next, k);
		}
	}
}

int main()
{
	GList* list = NULL;

	create_glist(&list);

	print_glist(list);

	putchar('\n');

	printf("max_depth: %d\n", depth_glist(list));

	erase(&list, 'b');

	print_glist(list);


	return 0;
}