数据结构（超详细讲解！！）第二十二节 广义表

1.定义

广义表，顾名思义，也是线性表的一种推广。广义表被广泛地应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。

广义表又称列表，是n ( n 大于等于 0 ) 个元素的有限序列，记作A = ( a1, a2, …, an )。其中A是列表的名字，n是它的长度，ai可以是数据元素，也可以是列表。如果ai是列表，则称其为列表A的子表。

习惯上，用大写字母表示列表的名称，用小写字母表示数据元素。用圆括号把列表的元素括起来，用逗号分隔开列表中的元素。

在广义表GL=(d1, d2，d3，…，dn)中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的，因为在定义广义表时又使用了广义表的概念。

广义表是递归定义的线性结构， GL=(d1, d2，d3，…，dn) 其中：di  或为原子或为广义表

广义表是一个多层次的线性结构

列表的深度 ：列表展开后的最大括号层次数。

L = (a, b, c)    列表L长度为3，深度为1

E = ( )            E为空表，长度为0，深度为1

A = (x, L, z)   列表A的长度为3，深度为2

B = (A, y, E)  列表B的长度为3，深度为3

C = (A, B)     列表C的长度为2，深度为4

D = (z, D)      列表D的长度为2，深度为无穷大

列表是非终端结点（即交叉结点），数据元素是终端结点，空表作为一个特殊的终端结点。

纯表：通常把与树对应的列表称为纯表，它限制了表中成分的共享性和递归。例如列表L、A、B。

具有共享和递归特性的列表可以和有向图建立对应。

广义表 GL=(d1, d2，d3，…，dn)的结构特点:

1)  广义表中的数据元素有相对次序；

2)  广义表的长度定义为最外层包含元素个数；

3)  广义表的深度定义为所含括弧的重数；    

注意：“原子”的深度为 0               “空表”的深度为 1

4)  广义表可以共享；

5)  广义表可以是一个递归的表。      

递归表的深度是无穷值，长度是有限值。

6）任何一个非空广义表 GL=(d1, d2，d3，…，dn)    均可分解为            

表头  Head(GL) = d1   和   表尾  Tail(GL) = ( d2, …, dn) 两部分。

任何一个非空广义表的表头是表中第一个元素，可以是数据元素，也可以是子表，而其表尾一定是子表。

L = (a, b, c)       E = ( )     A = (x, L, z)      B = (A, y, E)     C = (A, B)      D = (z, D)

head(L) = a,  tail(L) = (b, c)

head(B) = A, tail(B) = (y, E)

head(tail(L)) = head(b, c) = b

tail(tail(tail(L))) = tail(tail(b, c)) = tail(c) = ( )

2.广义表的两种常用存储结构

1）头尾表示法

在广义表的“头尾表示法”中需要两种结点结构：表结点和原子结点。 其中，原子结点是原子元素的存储映像，它包括两个域：标志域和值域； 表结点是子表的存储映像，它包括三个域：标志域、指向表头的指针域和指向表尾的指针域。 标志域为0表示是原子结点，标志域为1表示是表结点。

空表      L=NULL

若表头为原子，则为

否则，依次类推。

/* 广义表的头尾链表存储结构 */
typedef enum {ATOM,  LIST} ElemTag;    
/* ATOM＝0，表示原子；LIST＝1， 表示子表 */
typedef struct GLNode
{ 
      ElemTag   tag;                /* 标志位tag用来区别原子结点和表结点 */                        
      union 
      {                         
        AtomType      atom;                    /* 原子结点的值域atom */
        struct { struct GLNode  * hp,  *tp; } htp;
        /* 表结点的指针域htp，  包括表头指针域hp和表尾指针域tp */ 
     } atom-htp;                
     /* atom-htp 是原子结点的值域atom和表结点的指针域htp的联合体域 */
}  *GList； 

2）左孩子右兄弟（子表）表示法

在此种表示法中，同样需要两种结点——表结点和原子结点来分别表示子表和原子元素。将子表中第一个元素（可以是原子元素也可以是子表）称为该子表的左孩子；将元素右边紧挨着它的元素（可以是原子元素也可以是子表）称为该元素的右兄弟。原子结点没有左指针域，但它需要存储原子元素的值。

typedef enum {ATOM, LIST} ElemTag;  /* ATOM＝0， 表示原子； LIST＝1， 表示子表 *
/
typedef struct GLNode
{ 
      ElemTag   tag;             
      union                   
 { 
 AtomType      atom;      
 struct GLNode  * hp;      
    } atom-hp;               
    /* atom-hp 是原子结点的值域atom和表结点的表头指针域hp的联合体域 */ 
  struct GLNode  * tp;         
} *GList; 

3.基本操作

1.求表头和表尾

//求广义表的表头和表尾。
GList Head(GList L)
{　
　if(L==NULL) return(NULL);    　　/* 空表无表头 */　
　if(L->tag==ATOM) exit(0);    	/* 原子不是表 */　
　else return(L->atom-htp.htp.hp);
}
GList Tail(GList L)
{　
　　if(L==NULL) return(NULL);   　/* 空表无表尾 */　
　　if(L->tag==ATOM) exit(0);    　/* 原子不是表*/　
　　else return(L->atom-htp.htp.tp);
} 

2.长度和深度

//求广义表的长度和深度。
int Length(GList L)
{ int k=0;　
　GLNode *s;　
　if(L==NULL) return(0);    		/* 空表长度为0 */　
　if(L->tag==ATOM) exit(0);    	/* 原子不是表 */　
　s=L;　
　while(s!=NULL)    　		/* 统计最上层表的长度 */
  　　{ k++;　
   　　　 s=s->atom-htp.htp.tp;
  　 }　
　return(k);
}
int Depth(GList L)
{ int d, max=0;　
　GLNode *s;　
　if(L==NULL) return(1);    /* 空表深度为1 */　
　if(L->tag==ATOM) return(0);    /* 原子深度为0 */　
　s=L;　
　while(s!=NULL)    /* 求每个子表的深度的最大值 */
  　{ d=Depth(s->atom-htp.htp.hp);　
   　　 if(d>max) max=d;　
　　    s=s->atom-htp.htp.tp;
  　 }　
return(max+1);    /* 表的深度等于最深子表的深度加1 */