5.32.c

数据结构习题及答案

5.32④  试编写判别两个广义表是否相等的递归算法。

要求实现以下函数：
Status Equal(GList A, GList B);
/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */

广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
     ElemTag tag;
     union {
       char atom;
       struct { 
         GLNode *hp, *tp;
       } ptr;
     }un;
} *GList;
Status Equal(GList A, GList B)
/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */
{ 
  if(!A&&!B) return 1;                             //空表
  if(!A->tag&&!B->tag&&A->un.atom==B->un.atom) return 1; //为原子结点且值相等
  if(A->tag&&B->tag&&Equal(A->un.ptr.hp,B->un.ptr.hp)&&Equal(A->un.ptr.tp,B->un.ptr.tp))return 1;//表头表尾都相等
  return 0;
  }