前言
在学习广义表的时候，我先是翻阅了严蔚敏老师的《数据结构》第二版教材，然后翻阅了我们上课的教材，周桂红老师的《数据结构》第一版，两本书中，广义表都在"串、数组、广义表"这个章节，大概是第四章。问题来了，严老师的教材对于广义表的代码实现没有提及，周老师的教材对于广义表的代码实现只是给了纯代码，加上代码中寥寥无几的注释，特别是在建立广义表的代码实现上面，逻辑复杂难懂，没有阐述实现的基本思想。
后来，我先是取到了 BliBli 视频网站上面去搜索有关广义表的学习视频，第一个找到的是青岛大学老师的教学视频，但是此视频只讲原理不讲代码如何实现，接下来我先后在 CSDN，C 语言中文网，C 语言网查找资料，发现有的标题写的 C 语言实现广义表，但是代码却是使用的 C++写的，有的文章写的好，但只写了如何创建，没有一篇是代码和实现思想均有详细清晰阐述的文章。于是我决定自己不看教材，试着自己写一个代码实现，其中包含一些基本运算函数。
广义表的存储结构
本例子基于实现此图,实现广义表 (a,(b,c,d))
typedef struct Node
{
int tag; //标志域
union
{
char atom; //原子结点的值域
struct
{
struct Node *hp, *tp;
} ptr; //子表结点的指针域，hp指向表头；tp指向表尾
} un;
} GList;
广义表创建的基本思想
由于广义表的每一个节点，可能是原子节点，也可能是表节点，那么我们将创建表节点和原子节点分开，分别编写函数
创建原子节点
- 设置原子节点的标识域
- 开辟原子域空间
- 设置原子域的标志域
- 设置原子域的原子值
- 为原子节点尾指针开辟空间
- 返回原子节点的尾指针
创建表节点
- 设置表节点的标识域
- 设置表节点的尾指针
- 创建子节点并开辟空间
- 返回子节点的头指针
广义表的取头尾操作
较为简单，直接看代码示例。
GList *Get_Head(GList *L)
{
GList *head = L->un.ptr.hp;
return head;
}
GList *Get_Tail(GList *L)
{
GList *tail = L->un.ptr.tp;
return tail;
}
广义表遍历的基本思想
如果发现标识域等于 0，那么就是原子节点，直接打印，否则就分别递归头指针和为尾指针。
int GListTraverse(GList *L)
{
if (L == NULL)
{
return 0;
}
// 如果该节点为原子节点，打印
if (L->tag == 0)
{
printf("%c", L->un.atom);
}
// 如果该节点为表节点，递归函数
else if (L->tag == 1)
{
GListTraverse(L->un.ptr.hp);
GListTraverse(L->un.ptr.tp);
}
}
广义表求深度基本思想
和遍历类似，如果是表节点那么深度depth就自增。
int GList_Depth(GList *L)
{
int depth = 1;
if (L == NULL)
{
return depth;
}
// 如果该节点为表节点，递归函数
if (L->tag == 1)
{
depth++;
GList_Depth(L->un.ptr.tp);
}
return depth;
}
本文完整代码
