1. 广义表的定义
每个元素可以为Atom，原子，也可以为线性表。
线性表的推广。线性表元素有唯一的前驱和后继，为线性表，而广义表是多层次的线性表
表头：第一个元素，可能是原子，可能是广义表
表尾：除了第一个元素，剩余的元素，所构成的广义表
举例：
A = (a,b,(c,d),e)
head(A) = a
tail(A) = (b,(c,d),e)
遍历操作：
取表头，取表尾 ，取表头..
长度：最外层的元素数，即最外层的','+1
深度：括号层数
2. 广义表的两种存储结构（子表法）
2.1链式存储结构 - 每个数据元素可以用一个节点表示
元素可以为原子或列表
原子节点：标志域、值域
列表节点：标志域、指示表头的指针域、指示表尾的指针域
空表：A = NULL
除了空表，表头指针指向一个表节点，表节点再分表头、表尾...
最高层表节点(可能原子、子表)的个数就是表长度? A = (a,b,(c,d),e) 最高层表头是先a,表尾是(b,(c,d),e)，表头是b,表尾((c,d),e)..就是第一层的表尾直到为空之前，有过的表尾指针+1
判断是否在同一层次？
是这样的： 最高层处于同一层，后继的tail指针指向的是同一层，否则，head指针，或者表头是Atom，都是下一层。
2.2扩展线性表存储结构
不是用表头表尾指针了，而是，每一个节点，不管是子表还是原子，都有一个指向本子表下一个元素的next指针
A = (a,b,(c,d))
A -> |1,HP,TP|
| |
a -> b -> (c,d)
|
c -> d下面，实现了广义表的两种定义，以及基于递归的一些操作。
#include<bits/stdc++.h>
#define AtomType int
typedef enum{ATOM,LIST}ElemTag; //ATOM = 0：原子；LIST = 1:子表
/*线性表存储之链式*/
typedef struct GLNode{
ElemTag tag; //枚举类型的标志域，只能取定义了的枚举值
union{ //union联合体，下面两部分只能取其一；要么取AtomType;要么取结构体ptr,ptr包括两个指针hp,tp
AtomType atom;
struct{
struct GLNode *hp,*tp;
}ptr;
};
}*GList; //定义广义表类型，GList为指针 /*线性表存储之扩展线性表 = 子表法*/
typedef struct GLNode2{
ElemTag tag;
union{
AtomType atom;
struct GLNode2 *hp; //对于原子，tp就是指向其相同层次的下一个元素
//对于列表，hp指向本列表内部第一个元素，而tp是指向本层次上的下一个元素
};
struct GLNode2 *tp;
} *GList2;
/*
* 讨论广义表的递归算法 ： 分治法进行递归算法设计
* 1. 问题可拆解成子问题，与原问题性质相同，规模变小
* 2. 有递归终止条件
*/ /*求广义表的深度 - 采用链式存储结构时
* 广义表的深度：（）的重数 空表() 深度为1.原子深度为0
*
*/
int GListDepth(GList L) {
if(!L) return ; //空表1
if(L->tag ==ATOM ) return ;
GList pp;
//遍历同一层，递归下一层，取表尾，取表头，第一步先去一个表头
int max;
for(max = , pp =L;pp!=NULL;pp = pp->ptr.tp){
int dep = GListDepth(pp->ptr.hp) ;
if(dep > max) max = dep; //这一步比较，是比较同一层的depth
}
return max+;
}
//练习
int depth_my(GList L) {
if(L == NULL){
return ;
}
if(L->tag == ATOM){
return ;
}
int max = ;
GList pp;
for(max = ,pp=L;pp!=NULL;pp = pp->ptr.tp){
int dep = depth_my(pp->ptr.hp);
if(dep >max) max = dep;
}
return max+;
} /*
求Depth2 == 子表法求dep
*/
int GListDepth_2(GList2 L){
if(L == NULL) return ;
if(L->tag == ATOM) return ;
int max = ;
GList2 pp;
for(max = ,pp=L->hp;pp!=NULL;pp = pp->tp){
int dep = GListDepth_2(pp);
if(dep >max) max = dep;
}
return max+;
}
/*********************分界*****************************/
/*
* 复制广义表：copy深复制 -- 链式存储
* 分别复制表头、表尾，然后合成即可==递归
*/
void CopyGList(GList &T,GList L) {
//头尾链表存储，将L赋值给T
if(!L) T = NULL; //空
else{
//创建一个节点 ，这个节点要么是ATOM，要么是广义表
T = (GList)malloc(sizeof(GLNode));
if(!T) exit();
T->tag = L->tag;
if(L->tag == ATOM) //是原子的话，复制原子
T->atom = L->atom;
//复制广义表
else{
//分别复制表头和表尾
CopyGList(T -> ptr.hp,L->ptr.hp);
CopyGList(T->ptr.tp,L->ptr.tp);
}
}
}
//练习
void copy_my(GList&T,GList L) {
if(L == NULL) T = NULL;
else{
T = (GList)malloc(sizeof(GLNode));
if(!T) exit();
T -> tag = L -> tag;
if(L->tag == ATOM){
T->atom = L->atom;
}else{
copy_my(T -> ptr.hp,L->ptr.hp);
copy_my(T ->ptr.tp,L->ptr.tp);
}
}
}
/**********************分割线*************************/
/*
* 创建一个广义表：必考内容
* 广义表的书写，看成一个字符串S
* 下面头尾链表法创建一个广义表
*/
using namespace std;
string emp = "()" ; void sever(string &str,string &hstr){
//将非空串str分割成两部分，hstr是表头
int n = str.size();
int i = -;
int k = ; //k记录尚未配对的“(” 数
char ch;
do{ //搜索最外层第一个(
++i;
ch = str[i];
if(ch == '(') ++k;
else if(ch == ')') --k;
}while(i<n&&(ch != ','||k!=));
if(i<n){
hstr =str.substr(,i);
//printf("in\n");
str = str.substr(i+,n-i-);
//printf("out\n");
}else{
hstr = str.substr(,str.size());
str.clear();
}
} void CreateGList(GList &L,string s){
//采用头尾链表存储结构，创建L
if(s.compare(emp) == ) L = NULL;
else{
L = (GList)malloc(sizeof(GLNode));
if(!L) exit();
if(s.size() == ){ //单个元素，建立原子节点
L->tag = ATOM;
L->atom = s[];
}else{ //表节点 ,表尾
L->tag = LIST;
GList p,q;
p = L; //p是指向当前子表(表尾节点)的指针
string sub;
sub = s.substr(,s.size()-); //去掉外层括号
string hsub;
do{ //重复建立n个子表
sever(sub,hsub); //sub中分理出表头串hsub ，同时，sub去除了hsub
CreateGList(p->ptr.hp,hsub);
q = p; //记录p，下面sub不为空，要再建立一个表尾节点，q记录上一层的p，用以连接q->ptr.tp = q
if(!sub.empty()) {
p = (GList)malloc(sizeof(GLNode));
if(!p)exit();
p -> tag = LIST;
q -> ptr.tp = p;
}//if
}while(!sub.empty());
q -> ptr.tp = NULL;
// printf("has complete\n");
}
}
} int main(){
// string s = "1232342342";
// if(s.compare("123") == 0){
// printf("13");
// }
// printf("\n");
// s = s.substr(1,s.size()-2);
// for(int i = 0;i<s.size();i++){
// printf("%c",s[i]);
// } string ss = "(2,3,4,(1,2))";
GList L;
CreateGList(L,ss);
printf("深度：");
printf("%d",GListDepth(L));
return ;
}