广义表

维基百科，自由的百科全书

广义表是一种非线性的数据结构。但如果广义表的每个元素都是原子，它就变成了线性表。广义表广泛地用于人工智能等领域的LISP语言。

广义表一般记作 LS = (a1, a2, •••, an), n是它的长度，ai可以是单个元素(原子)，也可以是广义表(子表)，当广义表非空时，称第一个元素a1为LS的表头，称其余元素组成的表为LS的表尾。注意：表头是元素(可以是原子，也可以是广表)，表尾一定是广义表。E=(a, E)是一个递归的表。D=(( ),(e),(a,(b,c,d)))是多层次的广义表，长度为3，深度为3。例：((a),a)的表头是(a)，表尾是(a)，((a))的表头是(a)，表尾是( )。

目录 1 头尾链表存储表示 1.1 存储结构 1.2 基本操作 2 扩展线性链表存储表示 2.1 存储结构 2.2 基本操作

[编辑] 头尾链表存储表示

[编辑] 存储结构

/* 广义表的头尾链表存储表示 */
typedef enum{ATOM,LIST}ElemTag; /* ATOM==0：原子，LIST==1：子表 */
typedef struct GLNode
{
  ElemTag tag; /* 公共部分，用于区分原子结点和表结点 */
  union /* 原子结点和表结点的联合部分 */
  {
    AtomType atom; /* atom是原子结点的值域，AtomType由用户定义 */
    struct
    {
      struct GLNode *hp,*tp;
    }ptr; /* ptr是表结点的指针域，prt.hp和ptr.tp分别指向表头和表尾 */
  }a;
}*GList,GLNode; /* 广义表类型 */

[编辑] 基本操作

/* 广义表的头尾链表存储的基本操作(11个) */
#include"func5-1.c" 
void InitGList(GList *L)
{ /* 创建空的广义表L */
  *L=NULL;
}

void CreateGList(GList *L,SString S) /* 算法5.7 */
{ /* 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()" */
  SString sub,hsub,emp;
  GList p,q;
  StrAssign(emp,"()"); /* 空串emp="()" */
  if(!StrCompare(S,emp)) /* S="()" */
    *L=NULL; /* 创建空表 */
  else /* S不是空串 */
  {
    *L=(GList)malloc(sizeof(GLNode));
    if(!*L) /* 建表结点 */
      exit(OVERFLOW);
    if(StrLength(S)==1) /* S为单原子，只会出现在递归调用中 */
    {
      (*L)->tag=ATOM;
      (*L)->a.atom=S[1]; /* 创建单原子广义表 */
    }
    else /* S为表 */
    {
      (*L)->tag=LIST;
      p=*L;
      SubString(sub,S,2,StrLength(S)-2); /* 脱外层括号(去掉第1个字符和最后1个字符)给串sub */
      do
      { /* 重复建n个子表 */
        sever(sub,hsub); /* 从sub中分离出表头串hsub */
        CreateGList(&p->a.ptr.hp,hsub);
        q=p;
        if(!StrEmpty(sub)) /* 表尾不空 */
        {
          p=(GLNode *)malloc(sizeof(GLNode));
          if(!p)
            exit(OVERFLOW);
          p->tag=LIST;
          q->a.ptr.tp=p;
        }
      }while(!StrEmpty(sub));
      q->a.ptr.tp=NULL;
    }
  }
}
void DestroyGList(GList *L)
{ /* 销毁广义表L */
  GList q1,q2;
  if(*L)
  {
    if((*L)->tag==LIST) /* 删除表结点 */
    {
      q1=(*L)->a.ptr.hp; /* q1指向表头 */
      q2=(*L)->a.ptr.tp; /* q2指向表尾 */
      DestroyGList(&q1); /* 销毁表头 */
      DestroyGList(&q2); /* 销毁表尾 */
    }
    free(*L);
    *L=NULL;
  }
}

void CopyGList(GList *T,GList L)
{ /* 采用头尾链表存储结构，由广义表L复制得到广义表T。 */
  if(!L) /* 复制空表 */
    *T=NULL;
  else
  {
    *T=(GList)malloc(sizeof(GLNode)); /* 建表结点 */
    if(!*T)
      exit(OVERFLOW);
    (*T)->tag=L->tag;
    if(L->tag==ATOM)
      (*T)->a.atom=L->a.atom; /* 复制单原子 */
    else
    {
      CopyGList(&((*T)->a.ptr.hp),L->a.ptr.hp); /* 递归复制子表 */
      CopyGList(&((*T)->a.ptr.tp),L->a.ptr.tp);
    }
  }
}

int GListLength(GList L)
{ /* 返回广义表的长度，即元素个数 */
  int len=0;
  while(L)
  {
    L=L->a.ptr.tp;
    len++;
  }
  return len;
}

int GListDepth(GList L)
{ /* 采用头尾链表存储结构，求广义表L的深度。*/
  int max,dep;
  GList pp;
  if(!L)
    return 1; /* 空表深度为1 */
  if(L->tag==ATOM)
    return 0; /* 原子深度为0，只会出现在递归调用中 */
  for(max=0,pp=L;pp;pp=pp->a.ptr.tp)
  {
    dep=GListDepth(pp->a.ptr.hp); /* 递归求以pp->a.ptr.hp为头指针的子表深度 */
    if(dep>max)
      max=dep;
  }
  return max+1; /* 非空表的深度是各元素的深度的最大值加1 */
}

Status GListEmpty(GList L)
{ /* 判定广义表是否为空 */
  if(!L)
    return TRUE;
  else
    return FALSE;
}

GList GetHead(GList L)
{ /* 生成广义表L的表头元素，返回指向这个元素的指针 */
  GList h,p;
  if(!L) /* 空表无表头 */
    return NULL;
  p=L->a.ptr.hp; /* p指向L的表头元素 */
  CopyGList(&h,p); /* 将表头元素复制给h */
  return h;
}

GList GetTail(GList L)
{ /* 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针 */
  GList t;
  if(!L) /* 空表无表尾 */
    return NULL;
  CopyGList(&t,L->a.ptr.tp); /* 将L的表尾拷给t */
  return t;
}

void InsertFirst_GL(GList *L,GList e)
{ /* 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头) */
  GList p=(GList)malloc(sizeof(GLNode)); /* 生成新结点 */
  if(!p)
    exit(OVERFLOW);
  p->tag=LIST; /* 结点的类型是表 */
  p->a.ptr.hp=e; /* 表头指向e */
  p->a.ptr.tp=*L; /* 表尾指向原表L */
  *L=p; /* L指向新结点 */
}

void DeleteFirst_GL(GList *L,GList *e)
{ /* 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值 */
  GList p=*L; /* p指向第1个结点 */
  *e=(*L)->a.ptr.hp; /* e指向L的表头 */
  *L=(*L)->a.ptr.tp; /* L指向原L的表尾 */
  free(p); /* 释放第1个结点 */
}

void Traverse_GL(GList L,void(*v)(AtomType))
{ /* 利用递归算法遍历广义表L */
  if(L) /* L不空 */
    if(L->tag==ATOM) /* L为单原子 */
      v(L->a.atom);
    else /* L为广义表 */
    {
      Traverse_GL(L->a.ptr.hp,v); /* 递归遍历L的表头 */
      Traverse_GL(L->a.ptr.tp,v); /* 递归遍历L的表尾 */
    }
}

[编辑] 扩展线性链表存储表示

[编辑] 存储结构

/* 广义表的扩展线性链表存储表示 */
typedef enum{ATOM,LIST}ElemTag; /* ATOM==0：原子，LIST==1：子表 */
typedef struct GLNode1
{
  ElemTag tag; /* 公共部分，用于区分原子结点和表结点 */
  union /* 原子结点和表结点的联合部分 */
  {
    AtomType atom; /* 原子结点的值域 */
    struct GLNode1 *hp; /* 表结点的表头指针 */
  }a;
  struct GLNode1 *tp; /* 相当于线性链表的next，指向下一个元素结点 */
}*GList1,GLNode1; /* 广义表类型GList1是一种扩展的线性链表 */

[编辑] 基本操作

/* 广义表的扩展线性链表存储(的基本操作(13个) */
#include"func5-1.c" 

void InitGList(GList1 *L)
{ /* 创建空的广义表L */
  *L=NULL;
}

void CreateGList(GList1 *L,SString S) 
{ /* 采用扩展线性链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()" */
  SString emp,sub,hsub;
  GList1 p;
  StrAssign(emp,"()"); /* 设emp="()" */
  *L=(GList1)malloc(sizeof(GLNode1));
  if(!*L) /* 建表结点不成功 */
    exit(OVERFLOW);
  if(!StrCompare(S,emp)) /* 创建空表 */
  {
    (*L)->tag=LIST;
    (*L)->a.hp=(*L)->tp=NULL;
  }
  else if(StrLength(S)==1) /* 创建单原子广义表 */
  {
    (*L)->tag=ATOM;
    (*L)->a.atom=S[1];
    (*L)->tp=NULL;
  }
  else /* 创建一般表 */
  {
    (*L)->tag=LIST;
    (*L)->tp=NULL;
    SubString(sub,S,2,StrLength(S)-2); /* 脱外层括号(去掉第1个字符和最后1个字符)给串sub */
    sever(sub,hsub); /* 从sub中分离出表头串hsub */
    CreateGList(&(*L)->a.hp,hsub);
    p=(*L)->a.hp;
    while(!StrEmpty(sub)) /* 表尾不空，则重复建n个子表 */
    {
      sever(sub,hsub); /* 从sub中分离出表头串hsub */
      CreateGList(&p->tp,hsub);
      p=p->tp;
    };
  }
}

void DestroyGList(GList1 *L)
{ /* 初始条件：广义表L存在。操作结果：销毁广义表L */
  GList1 ph,pt;
  if(*L) /* L不为空表 */
  { /* 由ph和pt接替L的两个指针 */
    if((*L)->tag) /* 是子表 */
      ph=(*L)->a.hp;
    else /* 是原子 */
      ph=NULL;
    pt=(*L)->tp;
    DestroyGList(&ph); /* 递归销毁表ph */
    DestroyGList(&pt); /* 递归销毁表pt */
    free(*L); /* 释放L所指结点 */
    *L=NULL; /* 令L为空 */
  }
}

void CopyGList(GList1 *T,GList1 L)
{ /* 初始条件：广义表L存在。操作结果：由广义表L复制得到广义表T */
  *T=NULL;
  if(L) /* L不空 */
  {
    *T=(GList1)malloc(sizeof(GLNode1));
    if(!*T)
      exit(OVERFLOW);
    (*T)->tag=L->tag; /* 复制枚举变量 */
    if(L->tag==ATOM) /* 复制共用体部分 */
      (*T)->a.atom=L->a.atom; /* 复制单原子 */
    else
      CopyGList(&(*T)->a.hp,L->a.hp); /* 复制子表 */
    if(L->tp==NULL) /* 到表尾 */
      (*T)->tp=L->tp;
    else
      CopyGList(&(*T)->tp,L->tp); /* 复制子表 */
  }
}

int GListLength(GList1 L)
{ /* 初始条件：广义表L存在。操作结果：求广义表L的长度，即元素个数 */
  int len=0;
  GList1 p=L->a.hp; /* p指向第1个元素 */ 
  while(p)
  {
    len++;
    p=p->tp;
  };
  return len;
}

int GListDepth(GList1 L)
{ /* 初始条件：广义表L存在。操作结果：求广义表L的深度 */
  int max,dep;
  GList1 pp;
  if(L==NULL||L->tag==LIST&&!L->a.hp)
    return 1; /* 空表深度为1 */
  else if(L->tag==ATOM)
    return 0; /* 单原子表深度为0，只会出现在递归调用中 */
  else /* 求一般表的深度 */
    for(max=0,pp=L->a.hp;pp;pp=pp->tp)
    {
      dep=GListDepth(pp); /* 求以pp为头指针的子表深度 */
      if(dep>max)
        max=dep;
    }
  return max+1; /* 非空表的深度是各元素的深度的最大值加1 */
}

Status GListEmpty(GList1 L)
{ /* 初始条件：广义表L存在。操作结果：判定广义表L是否为空 */
  if(!L||L->tag==LIST&&!L->a.hp)
    return OK;
  else
    return ERROR;
}

GList1 GetHead(GList1 L)
{ /* 生成广义表L的表头元素，返回指向这个元素的指针 */
  GList1 h,p;
  if(!L||L->tag==LIST&&!L->a.hp) /* 空表无表头 */
    return NULL;
  p=L->a.hp->tp; /* p指向L的表尾 */
  L->a.hp->tp=NULL; /* 截去L的表尾部分 */
  CopyGList(&h,L->a.hp); /* 将表头元素复制给h */
  L->a.hp->tp=p; /* 恢复L的表尾(保持原L不变) */
  return h;
}

GList1 GetTail(GList1 L)
{ /* 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针 */
  GList1 t,p;
  if(!L||L->tag==LIST&&!L->a.hp) /* 空表无表尾 */
   return NULL;
 p=L->a.hp; /* p指向表头 */
 L->a.hp=p->tp; /* 在L中删去表头 */
 CopyGList(&t,L); /* 将L的表尾拷给t */
 L->a.hp=p; /* 恢复L的表头(保持原L不变) */
 return t;
}

void InsertFirst_GL(GList1 *L,GList1 e)
{ /* 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头) */
  GList1 p=(*L)->a.hp;
  (*L)->a.hp=e;
  e->tp=p;
}

void DeleteFirst_GL(GList1 *L,GList1 *e)
{ /* 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值 */
  if(*L&&(*L)->a.hp)
  {
    *e=(*L)->a.hp;
    (*L)->a.hp=(*e)->tp;
    (*e)->tp=NULL;
  }
  else
    *e=*L;
}

void Traverse_GL(GList1 L,void(*v)(AtomType))
{ /* 利用递归算法遍历广义表L */
  GList1 hp;
  if(L) /* L不空 */
  {
    if(L->tag==ATOM) /* L为单原子 */
    {
      v(L->a.atom);
      hp=NULL;
    }
    else /* L为子表 */
      hp=L->a.hp;
    Traverse_GL(hp,v);
    Traverse_GL(L->tp,v);
  }
}