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

下面，实现了广义表的两种定义，以及基于递归的一些操作。

  1 #include<bits/stdc++.h>
  2 #define AtomType int
  3 typedef enum{ATOM,LIST}ElemTag; //ATOM = 0：原子；LIST = 1:子表 
  4 /*线性表存储之链式*/
  5 typedef struct GLNode{
  6     ElemTag tag; //枚举类型的标志域，只能取定义了的枚举值
  7     union{      //union联合体，下面两部分只能取其一；要么取AtomType;要么取结构体ptr,ptr包括两个指针hp,tp 
  8         AtomType atom;
  9         struct{
 10             struct GLNode *hp,*tp;
 11         }ptr;
 12     }; 
 13 }*GList; //定义广义表类型，GList为指针 
 14 
 15 /*线性表存储之扩展线性表 = 子表法*/ 
 16 typedef struct GLNode2{
 17     ElemTag tag;
 18     union{
 19         AtomType atom;
 20         struct GLNode2 *hp;     //对于原子，tp就是指向其相同层次的下一个元素 
 21                              //对于列表，hp指向本列表内部第一个元素，而tp是指向本层次上的下一个元素 
 22     };
 23     struct GLNode2 *tp;
 24 } *GList2;
 25 /*
 26 *    讨论广义表的递归算法 ： 分治法进行递归算法设计
 27 *    1. 问题可拆解成子问题，与原问题性质相同，规模变小
 28 *    2. 有递归终止条件 
 29 */ 
 30 
 31 /*求广义表的深度 - 采用链式存储结构时 
 32 *    广义表的深度：（）的重数  空表() 深度为1.原子深度为0 
 33 *    
 34 */
 35 int GListDepth(GList L) {
 36     if(!L) return 1; //空表1
 37     if(L->tag ==ATOM ) return 0;
 38     GList pp;
 39     //遍历同一层，递归下一层，取表尾，取表头，第一步先去一个表头 
 40     int max;
 41     for(max = 0, pp =L;pp!=NULL;pp = pp->ptr.tp){
 42         int dep = GListDepth(pp->ptr.hp) ;
 43         if(dep > max) max = dep; //这一步比较，是比较同一层的depth 
 44     }
 45     return max+1;
 46 }
 47 //练习
 48 int depth_my(GList L) {
 49     if(L == NULL){
 50         return 1;
 51     }
 52     if(L->tag == ATOM){
 53         return 0;
 54     }
 55     int max = 0;
 56     GList pp;
 57     for(max = 0,pp=L;pp!=NULL;pp = pp->ptr.tp){
 58         int dep = depth_my(pp->ptr.hp);
 59         if(dep >max) max = dep;
 60     }
 61     return max+1;
 62 }
 63 
 64 /*
 65     求Depth2 == 子表法求dep 
 66 */
 67 int GListDepth_2(GList2 L){
 68     if(L == NULL) return 1;
 69     if(L->tag == ATOM) return 0;
 70     int max = 0;
 71     GList2 pp;
 72     for(max = 0,pp=L->hp;pp!=NULL;pp = pp->tp){
 73         int dep = GListDepth_2(pp);
 74         if(dep >max) max = dep;
 75     }
 76     return max+1;
 77 }
 78 /*********************分界*****************************/
 79 /*
 80 *    复制广义表：copy深复制 -- 链式存储 
 81 *    分别复制表头、表尾，然后合成即可==递归 
 82 */
 83 void CopyGList(GList &T,GList L) { 
 84     //头尾链表存储，将L赋值给T 
 85     if(!L) T = NULL; //空 
 86     else{
 87         //创建一个节点 ，这个节点要么是ATOM，要么是广义表 
 88         T = (GList)malloc(sizeof(GLNode));
 89         if(!T) exit(0);
 90         T->tag = L->tag;
 91         if(L->tag == ATOM) //是原子的话，复制原子 
 92             T->atom = L->atom; 
 93         //复制广义表
 94         else{
 95             //分别复制表头和表尾 
 96             CopyGList(T -> ptr.hp,L->ptr.hp);
 97             CopyGList(T->ptr.tp,L->ptr.tp);
 98         } 
 99     }
100 }
101 //练习
102 void copy_my(GList&T,GList L) {
103     if(L == NULL) T = NULL;
104     else{
105         T = (GList)malloc(sizeof(GLNode));
106         if(!T) exit(0);
107         T -> tag = L -> tag;
108         if(L->tag == ATOM){
109             T->atom = L->atom;
110         }else{
111             copy_my(T -> ptr.hp,L->ptr.hp);
112             copy_my(T ->ptr.tp,L->ptr.tp);
113         }
114     }
115 }
116 /**********************分割线*************************/
117 /*
118 *    创建一个广义表：必考内容 
119 *    广义表的书写，看成一个字符串S
120 *    下面头尾链表法创建一个广义表 
121 */ 
122 using namespace std;
123 string emp = "()" ;
124 
125 void sever(string &str,string &hstr){
126     //将非空串str分割成两部分，hstr是表头
127     int n = str.size();
128     int i = -1;
129     int k = 0; //k记录尚未配对的“(” 数
130     char ch;    
131     do{ //搜索最外层第一个( 
132         ++i;
133         ch = str[i];
134         if(ch == '(') ++k;
135         else if(ch == ')') --k;
136     }while(i<n&&(ch != ','||k!=0));
137      if(i<n){
138          hstr =str.substr(0,i);
139          //printf("in\n");
140          str = str.substr(i+1,n-i-1);
141          //printf("out\n");
142      }else{
143          hstr = str.substr(0,str.size());
144          str.clear();
145      }
146 }
147 
148 void CreateGList(GList &L,string s){
149     //采用头尾链表存储结构，创建L
150     if(s.compare(emp) == 0) L = NULL;
151     else{
152         L = (GList)malloc(sizeof(GLNode));
153         if(!L) exit(0);
154         if(s.size() == 1){ //单个元素，建立原子节点 
155             L->tag = ATOM;
156             L->atom = s[0];
157         }else{ //表节点 ,表尾 
158             L->tag = LIST;
159             GList p,q;
160             p = L; //p是指向当前子表(表尾节点)的指针 
161             string sub;
162             sub = s.substr(1,s.size()-2); //去掉外层括号 
163             string hsub;
164             do{ //重复建立n个子表 
165                 sever(sub,hsub); //sub中分理出表头串hsub ，同时，sub去除了hsub
166                 CreateGList(p->ptr.hp,hsub);
167                 q = p; //记录p，下面sub不为空，要再建立一个表尾节点，q记录上一层的p，用以连接q->ptr.tp = q 
168                 if(!sub.empty()) {
169                     p = (GList)malloc(sizeof(GLNode));
170                     if(!p)exit(0);
171                     p -> tag = LIST;
172                     q -> ptr.tp = p;
173                 }//if
174             }while(!sub.empty());
175             q -> ptr.tp = NULL;
176         //    printf("has complete\n");
177         }
178     }
179 }
180  
181 
182 int main(){
183 //    string s = "1232342342";
184 //    if(s.compare("123") == 0){
185 //        printf("13");
186 //    }
187 //    printf("\n");
188 //    s = s.substr(1,s.size()-2);
189 //    for(int i = 0;i<s.size();i++){
190 //        printf("%c",s[i]);
191 //    }
192     
193     string ss = "(2,3,4,(1,2))";
194     GList L;
195     CreateGList(L,ss);
196     printf("深度：");
197     printf("%d",GListDepth(L));
198     return 0;
199 }