新建 文本文档.txt

通过编写递归算法

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 */
{int i;

  GList ptr[20];

  GList p;                 

  if(L->tag||L->un.ptr.tp)

  {

    for(i=0,p=L;p;p=p->un.ptr.tp,i++)

    {

    if( p->un.ptr.hp )Reverse( p->un.ptr.hp );

    ptr[i] = p->un.ptr.hp;

    }

    for(p=L;p;p=p->un.ptr.tp)p->un.ptr.hp = ptr[--i];

  }


}