博客

什么是广义表

广义表的定义

线性表

线性表指的是n≥0个元素a1, a2, a3…的有序数列，并且线性表的元素具有原子性，即结构上是不可分割的一个整体。

广义表

(Generalized list) 而广义表则是线性表的一种扩展延伸。相对于线性表，广义表最大的特点在于其元素既可以是一个确定的类型，同时也可以是另一个有不定数量的元素组成的表（广义表）。

不难看出从广义表的定义是递归的。广义表是线性表的递归数据结构。

广义表的基本概念

1. 广义表的表示
   
   我们通常可以用 GL = (a1, a2, a3… an)来表示一个广义表，其中n为表的长度，n>=0，当n==0时，我们称广义表为空表，GL为广义表的名字。

为了能更好的区分广义表中的元素我们有以下定义：


原子

如果ai是单个元素，我们称之为GL的原子


子表

如果ai是一个广义表，我们陈之为GL的子表

我们通常把广义表中的原子用小写字母表示，而子表用大写字母表示。例如

A=() //空表

B=(e) //只含有一个原子的广义表

C=(a,(b,c,d)) //含有一个原子和一个子表的广义表

D=(A,B,C)=((),(e),(a,(b,c,d))) //含有三个子表的广义表，且第一个表为空表

E=(a,E) //广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

2. 广义表的深度和长度
   
   
   广义表的长度：
   
   广义表中元素的个数（包括原子和子表）
   
   
   广义表的深度：
   
   广义表中括号的最大层数叫广义表的深度。

3. 广义表的表头和表尾
   
   
   表头：
   
   当广义表不为空表时，第一个元素（可能为子表和原子）称为表头
   
   
   表尾：
   
   除去表头，剩余元素组成的新广义表称为表尾

例如：

• LS=(1,(1,2,3),5), 其中表头Head(LS)为原子1，表尾为Tail(LS)=((1,2,3),5)
• LS=(1), 其中表头Head(LS)为原子1，表尾为空表

广义表的存储结构

广义表是一种递归的数据结构，它的元素具有两种，因此很难为广义表分配固定的存储空间，所以其存储结构适合用链式存储结构。

为了能使原子和子表在结构上抱持一致，又容易区分我们通常采用如下结构：

广义表的第一种存储结构

用C语言表示为

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是表结点的指针域,ptr.hp 和ptr.tp分别指向表头和表尾
    };
} *Glist;  //广义表类型

例子


表示（a,(b,c,d)）

广义表的第二种存储结构

第二种表示形式实际上就只是在原子中添加了tp指针指向下一个原子和子表

用C语言实现：

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

例子

同样我们画一下结构图

广义表的计算（以第二种存储结构为例）

广义表长度的计算（类似于链表的长度，直接统计tp）

 int GLLength(GLNode *g)  
 //g为一个广义表头节点的指针
 {  int n=0;
    g=g->hp; //g指向广义表的第一个元素
    while (g!=NULL) 
    {  n++;
       g=g->tp;
    }
    return n;
}

广义表的深度

对于带头节点的广义表g,广义表深度的递归定义是它等于所有子表中表的最大深度加1。若g为原子,其深度为0。

求广义表深度的递归模型f()如下：、


代码

int GLDepth(GLNode *g) //求带头节点的广义表g的深度
{  int max=0,dep;
   if (g->tag==0) return 0;  //为原子时返回0
   g=g->hp;       //g指向第一个元素
   if  (g==NULL) return  1;   //为空表时返回1
   while (g!=NULL) //遍历表中的每一个元素
   {  if (g->tag==1)     　　　//元素为子表的情况
      {  dep=GLDepth(g); //递归调用求出子表的深度
         if (dep>max) max=dep;   
            //max为同一层所求过的子表中深度的最大值
      }
      g=g->tp;  //使g指向下一个元素
   }
   return(max+1); //返回表的深度
}

参考：

广义表