/* algo8-3.c 實現算法8.3的程序 */
 #include"c1.h"
 typedef char AtomType; /* 定義原子類型為字符型 */
 #include"c8-3.h"
 #include"bo5-51.c"

 Status CreateMarkGList(GList *L,SString S) /* 由bo5-51.c改 */
 { /* 采用頭尾鏈表存儲結構,由廣義表的書寫形式串S創建廣義表L。設emp="()" */
   SString sub,hsub,emp;
   GList p,q;
   StrAssign(emp,"()");
   if(!StrCompare(S,emp))
     *L=NULL; /* 創建空表 */
   else
   {
     *L=(GList)malloc(sizeof(GLNode));
     if(!*L) /* 建表結點 */
       exit(OVERFLOW);
     if(StrLength(S)==1) /* S為單原子 */
     {
       (*L)->tag=ATOM;
       (*L)->a.atom=S[1]; /* 創建單原子廣義表 */
       (*L)->mark=0; /* 加 */
     }
     else
     {
       (*L)->tag=LIST;
       (*L)->mark=0; /* 加 */
       p=*L;
       SubString(sub,S,2,StrLength(S)-2); /* 脫外層括號 */
       do
       { /* 重復建n個子表 */
         sever(sub,hsub); /* 從sub中分離出表頭串hsub */
         CreateMarkGList(&p->a.ptr.hp,hsub); /* 改 */
         q=p;
         if(!StrEmpty(sub)) /* 表尾不空 */
         {
           p=(GLNode *)malloc(sizeof(GLNode));
           if(!p)
             exit(OVERFLOW);
           p->tag=LIST;
           p->mark=0; /* 加 */
           q->a.ptr.tp=p;
         }
       }while(!StrEmpty(sub));
       q->a.ptr.tp=NULL;
     }
   }
   return OK;
 }

 void MarkList(GList GL) /* 算法8.3 */
 { /* 遍歷非空廣義表GL(GL!=NULL且GL->mark==0),對表中所有未加標志的結點加標志。*/
   GList t,p,q;
   Status finished;
   if(GL!=NULL&&GL->mark==0)
   {
     t=NULL; /* t指示p的母表 */
     p=GL;
     finished=FALSE;
     while(!finished)
     {
       while(p->mark==0)
       {
	 p->mark=1; /* MarkHead(p)的細化 */
         q=p->a.ptr.hp; /* q指向*p的表頭 */
         if(q&&q->mark==0)
           if(q->tag==0)
             q->mark=1; /* ATOM,表頭為原子結點 */
           else
           { /* 繼續遍歷子表 */
             p->a.ptr.hp=t;
             p->tag=ATOM;
             t=p;
             p=q;
           }
       } /* 完成對表頭的標志 */
       q=p->a.ptr.tp; /* q指向*p的表尾 */
       if(q&&q->mark==0)
       { /* 繼續遍歷表尾 */
         p->a.ptr.tp=t;
         t=p;
         p=q;
       }
       else /* BackTrack(finished)的細化 */
       {
         while(t&&t->tag==1) /* LIST,表結點,從表尾回溯 */
         {
           q=t;
           t=q->a.ptr.tp;
           q->a.ptr.tp=p;
           p=q;
         }
         if(!t)
           finished=TRUE; /* 結束 */
         else
         { /* 從表頭回溯 */
           q=t;
           t=q->a.ptr.hp;
           q->a.ptr.hp=p;
           p=q;
           p->tag=LIST;
         } /* 繼續遍歷表尾 */
       }
     }
   }
 }

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

 void visit(GList p)
 {
   if(p->tag==ATOM)
     printf("mark=%d %c\n",p->mark,p->a.atom);
   else
     printf("mark=%d list\n",p->mark);
 }

 void main()
 {
   char p[80];
   SString t;
   GList l;
   printf("請輸入廣義表l(書寫形式：空表:(),單原子:a,其它:(a,(b),b)):\n");
   gets(p);
   StrAssign(t,p);
   CreateMarkGList(&l,t);
   Traverse_GL(l,visit);
   MarkList(l);
   printf("加標志后:\n");
   Traverse_GL(l,visit);
 }