// bo5-6.cpp 廣義表的擴展線性鏈表存儲(存儲結(jié)構(gòu)由c5-6.h定義)的基本操作(13個)
 #include"c4-2.h" // 定義HString類型
 #include"bo4-2.cpp" // HString類型的基本操作
 // 廣義表的書寫形式串為HString類型
 Status InitGList(GList &L)
 { // 創(chuàng)建空的廣義表L
   L=NULL;
   return OK;
 }

 Status sever(HString &str,HString &hstr) // 同bo5-52.cpp
 { // 將非空串str分割成兩部分:hstr為第一個','之前的子串,str為之后的子串
   int n,i=1,k=0; // k記尚未配對的左括號個數(shù)
   HString ch,c1,c2,c3;
   InitString(ch); // 初始化HString類型的變量
   InitString(c1);
   InitString(c2);
   InitString(c3);
   StrAssign(c1,",");
   StrAssign(c2,"(");
   StrAssign(c3,")");
   n=StrLength(str);
   do
   {
     SubString(ch,str,i,1);
     if(!StrCompare(ch,c2))
       ++k;
     else if(!StrCompare(ch,c3))
       --k;
     ++i;
   }while(i<=n&&StrCompare(ch,c1)||k!=0);
   if(i<=n)
   {
     StrCopy(ch,str);
     SubString(hstr,ch,1,i-2);
     SubString(str,ch,i,n-i+1);
   }
   else
   {
     StrCopy(hstr,str);
     ClearString(str);
   }
   return OK;
 }

 Status CreateGList(GList &L,HString S)
 { // 初始條件: S是廣義表的書寫形式串。操作結(jié)果: 由S創(chuàng)建廣義表L
   HString emp,sub,hsub;
   GList p;
   InitString(emp);
   InitString(sub);
   InitString(hsub);
   StrAssign(emp,"()"); // 設emp="()"
   if(!(L=(GList)malloc(sizeof(GLNode)))) // 建表結(jié)點不成功
     exit(OVERFLOW);
   if(!StrCompare(S,emp)) // 創(chuàng)建空表
   {
     L->tag=LIST;
     L->hp=NULL;
     L->tp=NULL;
   }
   else if(StrLength(S)==1) // 創(chuàng)建單原子廣義表
   {
     L->tag=ATOM;
     L->atom=S.ch[0];
     L->tp=NULL;
   }
   else // 創(chuàng)建一般表
   {
     L->tag=LIST;
     L->tp=NULL;
     SubString(sub,S,2,StrLength(S)-2); // 脫外層括號
     sever(sub,hsub); // 從sub中分離出表頭串hsub
     CreateGList(L->hp,hsub);
     p=L->hp;
     while(!StrEmpty(sub)) // 表尾不空,則重復建n個子表
     {
       sever(sub,hsub); // 從sub中分離出表頭串hsub
       CreateGList(p->tp,hsub);
       p=p->tp;
     };
   }
   return OK;
 }

 void DestroyGList(GList &L)
 { // 初始條件: 廣義表L存在。操作結(jié)果: 銷毀廣義表L
   GList ph,pt;
   if(L) // L不為空表
   { // 由ph和pt接替L的兩個指針
     if(L->tag) // 是子表
       ph=L->hp;
     else // 是原子
       ph=NULL;
     pt=L->tp;
     free(L); // 釋放L所指結(jié)點
     L=NULL; // 令L為空
     DestroyGList(ph); // 遞歸銷毀表ph
     DestroyGList(pt); // 遞歸銷毀表pt
   }
 }

 Status CopyGList(GList &T,GList L)
 { // 初始條件: 廣義表L存在。操作結(jié)果: 由廣義表L復制得到廣義表T
   if(!L) // L空
   {
     T=NULL;
     return OK;
   }
   T=(GList)malloc(sizeof(GLNode));
   if(!T)
     exit(OVERFLOW);
   T->tag=L->tag; // 復制枚舉變量
   if(L->tag==ATOM) // 復制共用體部分
     T->atom=L->atom; // 復制單原子
   else
     CopyGList(T->hp,L->hp); // 復制子表
   if(L->tp==NULL) // 到表尾
     T->tp=L->tp;
   else
     CopyGList(T->tp,L->tp); // 復制子表
   return OK;
 }

 int GListLength(GList L)
 { // 初始條件: 廣義表L存在。操作結(jié)果: 求廣義表L的長度,即元素個數(shù)
   int len=0;
   GList p;
   if(L->tag==LIST&&!L->hp) // 空表
     return 0; // 空表返回0
   else if(L->tag==ATOM) // 單原子表
     return 1;
   else // 一般表
   {
     p=L->hp;
     do
     {
       len++;
       p=p->tp;
     }while(p);
     return len;
   }
 }

 int GListDepth(GList L)
 { // 初始條件: 廣義表L存在。操作結(jié)果: 求廣義表L的深度
   int max,dep;
   GList pp;
   if(L==NULL||L->tag==LIST&&!L->hp)
     return 1; // 空表深度為1
   else if(L->tag==ATOM)
     return 0; // 單原子表深度為0
   else // 求一般表的深度
     for(max=0,pp=L->hp;pp;pp=pp->tp)
     {
       dep=GListDepth(pp); // 求以pp為頭指針的子表深度
       if(dep>max)
         max=dep;
     }
   return max+1; // 非空表的深度是各元素的深度的最大值加1
 }

 Status GListEmpty(GList L)
 { // 初始條件: 廣義表L存在。操作結(jié)果: 判定廣義表L是否為空
   if(!L||L->tag==LIST&&!L->hp)
     return OK;
   else
     return ERROR;
 }

 GList GetHead(GList L)
 { // 初始條件: 廣義表L存在。操作結(jié)果: 取廣義表L的頭
   GList h;
   InitGList(h);
   if(!L||L->tag==LIST&&!L->hp)
   {
     printf("\n空表無表頭!");
     exit(0);
   }
   h=(GList)malloc(sizeof(GLNode));
   if(!h)
     exit(OVERFLOW);
   h->tag=L->hp->tag;
   h->tp=NULL;
   if(h->tag==ATOM)
     h->atom=L->hp->atom;
   else
     CopyGList(h->hp,L->hp->hp);
   return h;
 }

 GList GetTail(GList L)
 { // 初始條件: 廣義表L存在。操作結(jié)果: 取廣義表L的尾
   GList T;
   if(!L)
   {
     printf("\n空表無表尾!");
     exit(0);
   }
   T=(GList)malloc(sizeof(GLNode));
   if(!T)
     exit(OVERFLOW);
   T->tag=LIST;
   T->tp=NULL;
   CopyGList(T->hp,L->hp->tp);
   return T;
 }

 Status InsertFirst_GL(GList &L,GList e)
 { // 初始條件: 廣義表存在
   // 操作結(jié)果: 插入元素e作為廣義表L的第一元素(表頭,也可能是子表)
   GList p=L->hp;
   L->hp=e;
   e->tp=p;
   return OK;
 }

 Status DeleteFirst_GL(GList &L,GList &e)
 { // 初始條件:廣義表L存在。操作結(jié)果:刪除廣義表L的第一元素,并用e返回其值
   if(L)
   {
     e=L->hp;
     L->hp=e->tp;
     e->tp=NULL;
   }
   else
     e=L;
   return OK;
 }

 void Traverse_GL(GList L,void(*v)(AtomType))
 { // 利用遞歸算法遍歷廣義表L
   GList hp;
   if(L) // L不空
   {
     if(L->tag==ATOM) // L為單原子
     {
       v(L->atom);
       hp=NULL;
     }
     else // L為子表
       hp=L->hp;
     Traverse_GL(hp,v);
     Traverse_GL(L->tp,v);
   }
 }