/* bo5-5.c 廣義表的頭尾鏈表存儲(存儲結(jié)構(gòu)由c5-5.h定義)的基本操作(11個(gè)) */
 Status InitGList(GList *L)
 { /* 創(chuàng)建空的廣義表L */
   *L=NULL;
   return OK;
 }

 void DestroyGList(GList *L) /* 廣義表的頭尾鏈表存儲的銷毀操作 */
 { /* 銷毀廣義表L */
   GList q1,q2;
   if(*L)
   {
     if((*L)->tag==ATOM)
     {
       free(*L); /* 刪除原子結(jié)點(diǎn) */
       *L=NULL;
     }
     else /* 刪除表結(jié)點(diǎn) */
     {
       q1=(*L)->a.ptr.hp;
       q2=(*L)->a.ptr.tp;
       free(*L);
       *L=NULL;
       DestroyGList(&q1);
       DestroyGList(&q2);
     }
   }
 }

 Status CopyGList(GList *T,GList L)
 { /* 采用頭尾鏈表存儲結(jié)構(gòu),由廣義表L復(fù)制得到廣義表T。算法5.6 */
   if(!L) /* 復(fù)制空表 */
     *T=NULL;
   else
   {
     *T=(GList)malloc(sizeof(GLNode)); /* 建表結(jié)點(diǎn) */
     if(!*T)
       exit(OVERFLOW);
     (*T)->tag=L->tag;
     if(L->tag==ATOM)
       (*T)->a.atom=L->a.atom; /* 復(fù)制單原子 */
     else
     {
       CopyGList(&((*T)->a.ptr.hp),L->a.ptr.hp);
       /* 復(fù)制廣義表L->ptr.hp的一個(gè)副本T->ptr.hp */
       CopyGList(&((*T)->a.ptr.tp),L->a.ptr.tp);
       /* 復(fù)制廣義表L->ptr.tp的一個(gè)副本T->ptr.tp */
     }
   }
   return OK;
 }

 int GListLength(GList L)
 { /* 返回廣義表的長度,即元素個(gè)數(shù) */
   int len=0;
   if(!L)
     return 0;
   if(L->tag==ATOM)
     return 1;
   while(L)
   {
     L=L->a.ptr.tp;
     len++;
   }
   return len;
 }

 int GListDepth(GList L)
 { /* 采用頭尾鏈表存儲結(jié)構(gòu),求廣義表L的深度。算法5.5 */
   int max,dep;
   GList pp;
   if(!L)
     return 1; /* 空表深度為1 */
   if(L->tag==ATOM)
     return 0; /* 原子深度為0 */
   for(max=0,pp=L;pp;pp=pp->a.ptr.tp)
   {
     dep=GListDepth(pp->a.ptr.hp); /* 求以pp->a.ptr.hp為頭指針的子表深度 */
     if(dep>max)
       max=dep;
   }
   return max+1; /* 非空表的深度是各元素的深度的最大值加1 */
 }

 Status GListEmpty(GList L)
 { /* 判定廣義表是否為空 */
   if(!L)
     return TRUE;
   else
     return FALSE;
 }

 GList GetHead(GList L)
 { /* 取廣義表L的頭 */
   GList h,p;
   if(!L)
   {
     printf("空表無表頭!\n");
     exit(0);
   }
   p=L->a.ptr.tp;
   L->a.ptr.tp=NULL;
   CopyGList(&h,L);
   L->a.ptr.tp=p;
   return h;
 }

 GList GetTail(GList L)
 { /* 取廣義表L的尾 */
   GList t;
   if(!L)
   {
     printf("空表無表尾!\n");
     exit(0);
   }
   CopyGList(&t,L->a.ptr.tp);
   return t;
 }

 Status InsertFirst_GL(GList *L,GList e)
 { /* 初始條件: 廣義表存在 */
   /* 操作結(jié)果: 插入元素e作為廣義表L的第一元素(表頭,也可能是子表) */
   GList p=(GList)malloc(sizeof(GLNode));
   if(!p)
     exit(OVERFLOW);
   p->tag=LIST;
   p->a.ptr.hp=e;
   p->a.ptr.tp=*L;
   *L=p;
   return OK;
 }

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

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