==> 学习汇总（持续更新） ==> 从零搭建后端基础设施系列（一）-- 背景介绍
所谓的广义表就是单链表的扩展，就是节点可以是一个元素也可以是一个链表。官方的说法是，原子节点和子表节点。广义表用递归的方法来创建是最简单易懂的，也符合广义表的思想。
C代码实现下载 C++代码实现下载 (备用下载地址 )
1.广义表的各种形态
（1）、A = (); 空表 （2）、B = (()); 长度为1，深度为2，原子个数为0，这个实质上就是广义表中有一个元素，它是子表，该子表为空。 （3）、C = (a); 长度为1，深度为0，原子个数为1 （4）、D = (a,A,b);长度为3，深度为2，原子个数为2，其中A是一个空表。 （5）、E = (A,B,C,D)；长度为4，深度为3，原子个数为3，其中ABCD都是表。 （6）、F = （a,F）; 无限递归下去。
2.广义表C语言实现思路
先来看结构体定义
enum NodeType { ATOM, LIST }; typedef struct _GList { NodeType nodeType; //节点类型 union { char c; //原子 _GList* subList; //子表 }; _GList* next; //指向后继节点 }GList, *PGList;（1）创建表 给定一个串，该串必须遵守相关规则，例如，层次分隔符用‘（）’，元素分隔符用‘，’。
伪代码描述如下：
Create(PGList* gl,char* s) { 如果s="()",则(*gl)=NULL 如果s='(',则递归创建子表，Create(&(*gl)->subList,s); 否则创建原子节点 如果s=',',则递归创建后继节点（该节点可能是ATOM或LIST）Create(&(*gl)->next,s); 如果s=')',则置(*gl)->next为NULL，表示该子表已经结束 如果s='\0'，则置(*gl)->next为NULL，表示该广义表已经创建完成 }重点！！！ ：为什么这里要传进去二级指针？刚开始我传进一级指针的时候，我发现创建完成后，gl = NULL，为什么？因为没有一个变量记录gl第一个节点的地址啊，所以最后找不到它了。这时候就需要一个二级指针，指向该头节点的地址。如图：
（2）计算广义表长度 这个就比较简单了，就和单链表一样，依次遍历第一层节点即可。 需要注意的是，因为创建广义表的时候，一开始就创建了一个子表节点，所以该节点才是广义表的头节点。
（3）计算广义表深度 递归遍历子表，取子表深度最大值。例如：（A,(B,C),(D,E,(F,G)),H） 此时最大深度在（F,G）这个子表处得到。
（4）添加原子到广义表前面或后面 这个操作和单链表的操作是一样的，广义表如果要实现更深层次的插入和添加会比较麻烦。
（5）打印广义表 一样的递归遍历，若是原子节点，则直接输出，所示子表节点，则递归进去。
2.广义表C++实现思路
广义表的节点类如下：
enum NodeType { ATOM, LIST }; //节点类型 private: class Node //广义表结点类 { public: Node(NodeType nodeType, T atom) :nodeType(nodeType), atom(atom) {} private: NodeType nodeType; //节点类型 union { T atom; //原子 Node* subList; //子表 }; Node* next; //指向下一个元素 friend class GList; };和C语言类似。
只不过C++我用模板实现，这样就能存储字符、整形、浮点型了。 基本思路和C语言类似，所以，我一般都是用C语言实现了简单的功能，然后用C++封装成一个完善的类。这里省略对C++的描述，具体看代码，里面有注释。
_acme_ 认证博客专家 JAVA