5.34.c

来自「数据结构习题及答案」· C语言 代码 · 共 39 行

5.34⑤ 试编写递归算法，逆转广义表中的数据元素。
例如：将广义表
    (a,((b,c),()),(((d),e),f))
逆转为：
    ((f,(e,(d))),((),(c,b)),a)。

要求实现以下函数：
void Reverse(GList &L);
/* 递归逆转广义表L */

广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
   ElemTag tag;
   union {
      char atom;
      struct { 
         GLNode *hp, *tp;
      } ptr;
   }un;
} *GList;
void Reverse(GList &L)
/* 递归逆转广义表L */
{
 GList q,p;
 q=L; 
 p=q->un.ptr.tp; 
 if(!p&&q->tag) Reverse(L->un.ptr.hp);
 while(p)
  {q->un.ptr.tp=p->un.ptr.tp;
   p->un.ptr.tp=L;
   L=p;
   p=q->un.ptr.tp;
   if(L->tag)
     Reverse(L->un.ptr.hp);
  }     
}