广义表的定义及用法

时间:2022-09-25 21:19:08

转自http://blog.csdn.net/fanzheng220112583/article/details/7719228

广义表(Lists,又称列表)是线性表的推广。线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项,原子是作为结构上不可分割的成分,它可以是一个数或一个结构,若放松对表元素的这种限制,容许它们具有其自身结构,这样就产生了广义表的概念。

     广义表是n (n>=0)个元素a1,a2,a3,…,an的有限序列,其中ai或者是原子项,或者是一个广义表。通常记作LS=(a1,a2,a3,…,an)。LS是广义表的名字,n为它的长度。若ai是广义表,则称它为LS的子表。





通常用圆括号将广义表括起来,用逗号分隔其中的元素。为了区别原子和广义表,书写时用大写字母表示广义表,用小写字母表示原子。若广义表LS(n>=1)非空,则a1是LS的表头,其余元素组成的表(a2,…an)称为LS的表尾。

    显然广义表是递归定义的,这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下:

(1)A=()——A是一个空表,其长度为零。

(2)B=(e)——表B只有一个原子e,B的长度为1。

(3)C=(a,(b,c,d))——表C的长度为2,两个元素分别

         为原子a和子表(b,c,d)。

(4)D=(A,B,C)——表D的长度为3,三个元素

        都是广义表。显然,将子表的值代入后,

         则有D=(( ),(e),(a,(b,c,d)))。

(5)E=(E)——这是一个递归的表,它的长度为2,E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).

从上述定义和例子可推出广义表的三个重要结论:

(1)广义表的元素可以是子表,而子表的元素还可以是子表,。由此,广义表是一个多层次的结构,可以用图形象地表示。P108

 

难以用顺序存储结构

(2)广义表可为其它表所共享。例如在上述例(4)中,广义表A,B,C为D的子表,则在D中可以不必列出子表的值,而是通过子表的名称来引用。

 

(3)广义表的递归性。

     综上所述,广义表不仅是线性表的推广,也是树的推广。

由表头、表尾的定义可知:任何一个非空广义表其表头可能是原子,也可能是列表,而其表尾必定是列表

          gethead(B)=e         gettail(B)=(  )

          gethead(D)=A        gettail(D)=(B,C)

 

      由于(B,C)为非空广义表,则可继续分解得到:

         gethead(B,C)=B         gettail(B,C)=(C)

  

    注意广义表( )和( ( ) )不同。前者是长度为0的空表,

对其不能做求表头的和表尾的运算;而后者是长度为1的非空表(只不过该表中唯一的一个元素是空表)。对其可进行分解,得到表头和表尾均为空表( )。

 

 

广义表的存储结构

由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构,(或是原子,或是广义表),因此,难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可用一个结点表示。

    由于广义表中有两种数据元素,原子或广义表,因此,需要两种结构的结点:一种是表结点,用以表示列表;一种是原子结点,用以表示原子。 

 

  若列表不空,则可分解成表头和表尾;反之,一对确定的表头和表尾可唯一确定列表。由此,一个表结点可由三个域组成:标志域、指示表头的指针域和指示表尾的指针域;而原子结点只需两个域:标志域和值域。

1、仅有表结点由三个域组成:

    标志域、指示表头的指针域和指示表尾的指针域;而原子域只需两个域:标志域和值域。

广义表的定义及用法

头尾链表存储表示

[cpp] view plain copy print?
  1. typedef enum {ATOM,LIST } ElemTag;  //ATOM==0:表示原子,LIST==1:表示子表  
  2. typedef struct GLNode {  
  3.     ElemTag  tag;  //公共部分,用以区分原子部分和表结点  
  4.     union {       //原子部分和表结点的联合部分  
  5.       AtomType  atom; //atom是原子结点的值域,AtomType由用户定义  
  6.       struct { struct GLNode *hp, *tp;} ptr;  
  7.              // ptr是表结点的指针域,ptr.hp 和ptr.tp分别指向表头和表尾  
  8.     };  
  9. } *Glist;  //广义表类型  
广义表的定义及用法
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;  //广义表类型


示例如图:

广义表的定义及用法

这种存储结构的三个特点:

1。除空表的表头指针为空外,对任何非空列表,其表头指针均指向一个表结点,且该结点中的hp域指示列表表头,tp域指向列表表尾(除非表尾为空,则指针为空,否则必为表结点);

2。容易分清列表中原子和子表所在层次。如在列表D中,原子e和a在同一层次上,而b、c和d在同一层次且比e和a低一层,B和C是同一层的子表;

3。最高层的表结点个数即为列表的长度。

 

2、表结点和原子结点均由三个域组成:标志域、指示表头的指针域和指示表尾的指针域;原子结点的三个域为:标志域、值域和指示表尾的指针域。


广义表的定义及用法

其类型定义如下:

 

扩展线性链表存储表示

[cpp] view plain copy print?
  1. Typedef enum { ATOM,LIST} ElemTag;                                
  2.     //ATOM==0:表示原子,LIST==1:表示子表  
  3. Typedef struct GLNode {  
  4.     ElemTag    tag;  //公共部分,用以区分原子部分和表结点  
  5.     union {  //原子部分和表结点的联合部分  
  6.         AtomType    atom;  //原子结点的值域  
  7.         struct GLNode  *hp;  //表结点的表头指针  
  8.         };  
  9.         struct GLNode    *tp;    
  10.                 //相当于线性链表的next,指向下一个元素结点  
  11. } *Glist;  //广义表类型Glist 是一种扩展的线性链表  

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 是一种扩展的线性链表


示例如图:

广义表的定义及用法


注意:

(1)若广义表Ls非空(n≥1),则al是LS的表头,其余元素组成的表(a2,a2,…,an)称为Ls的表尾。所以取广义表的表尾是取除表头外的后面元素。

(2)若一个广义表的表头为空表,则此广义表亦为空表是错的

  • 广义表()和(())不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表()