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

 Status CreateMarkGList(GList &L,SString S) // 由bo5-51.cpp改
 { // 采用頭尾鏈表存儲結構,由廣義表的書寫形式串S創建廣義表L。設emp="()"
   SString sub,hsub,emp;
   GList p,q;
   StrAssign(emp,"()");
   if(!StrCompare(S,emp))
     L=NULL; // 創建空表
   else
   {
     if(!(L=(GList)malloc(sizeof(GLNode)))) // 建表結點
       exit(OVERFLOW);
     if(StrLength(S)==1) // S為單原子
     {
       L->tag=ATOM;
       L->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->ptr.hp,hsub); // 改
         q=p;
         if(!StrEmpty(sub)) // 表尾不空
         {
           if(!(p=(GLNode *)malloc(sizeof(GLNode))))
             exit(OVERFLOW);
           p->tag=LIST;
           p->mark=0; // 加
	   q->ptr.tp=p;
         }
       }while(!StrEmpty(sub));
       q->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->ptr.hp; // q指向*p的表頭
         if(q&&q->mark==0)
           if(q->tag==0)
             q->mark=1; // ATOM,表頭為原子結點
           else
           { // 繼續遍歷子表
             p->ptr.hp=t;
             p->tag=ATOM;
             t=p;
             p=q;
           }
       } // 完成對表頭的標志
       q=p->ptr.tp; // q指向*p的表尾
       if(q&&q->mark==0)
       { // 繼續遍歷表尾
         p->ptr.tp=t;
         t=p;
         p=q;
       }
       else // BackTrack(finished)的細化
       {
         while(t&&t->tag==1) // LIST,表結點,從表尾回溯
         {
           q=t;
           t=q->ptr.tp;
           q->ptr.tp=p;
           p=q;
         }
         if(!t)
           finished=TRUE; // 結束
         else
         { // 從表頭回溯
           q=t;
           t=q->ptr.hp;
           q->ptr.hp=p;
           p=q;
           p->tag=LIST;
         } // 繼續遍歷表尾
       }
     }
   }
 }

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

 void visit(GList p)
 {
   if(p->tag==ATOM)
     printf("mark=%d %c\n",p->mark,p->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);
 }