线性表——广义表_广义表头尾链表存储结构怎么画

7广义表

广义表是递归定义的线性表，广义表是一个多层次的线性结构

ai 可以是单个元素(原子，用小写字母表示)，也可以是广义表(子表，用大写字母表示)

  A = (  )
  F = (d, (e))
  D = ((a,(b,c)), F)
  C = (A, D, F)
  B = (a, B) = (a, (a, (a, ... ,  ) ) )

7.1结构特点

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

广义表的深度定义为所含括号的重数;

一般用〇表示子表，用□表示原子

 

任何一个非空广义表LS=(a1,a2,…,an)均可分解为表头和表尾两部分：
表头Head(LS)=a1
表尾Tail(LS)=(a2,…,an)

例如：

Head( (( b,c)) )=(b,c)   Tail( ((b,c)) )=( )

Head( (b,c) )=b          Tail( (b,c) )=(c)

Head( (c) )=c            Tail( (c) )=( )

 

练习：

给出以下各广义表运算的结果：
(1) Head[((a,b),(c,d))]
(2) Tail[((a,b),(c,d))]
(3) Head[Tail[((a,b),(c,d))] ]
(4) Tail[Head[((a,b),(c,d))] ]
(5) Head[Tail[Head[((a,b),(c,d))]]]
(6) Tail[Head[Tail[((a,b),(c,d))]]]

（1） (a,b)
(2)     ((c,d))
(3)     (c,d)
(4)     (b)
(5)      b
(6)     (d)

7.2存储结构

  广义表的数据元素为不同的结构(或为原子，或为子表)，

难以用顺序存储结构表示，

常采用链式存储结构，每个元素用一个结点表示。

7.2.1头尾链表存储表示

若表不空，可分解成表头，表尾；
所以在表中存在两种结构的结点：元素结点和表结点。

类型描述：
 

typedef enum { ATOM，LIST } ElemTag;
 
typedef struct GLNode
{ 
 
   ElemTag tag;//tag=0表示元素结点,tg=1表示表结点
  
   union
   { 
     AtomType  atom;//表示元素数据
 
     struct { struct GLNode * hp, * tp; }ptr;//hp表示表头,tp表示表尾
   };
 
}*GList;

 

试画A2=（a,(b,c)）的头尾链表存储结构示意图

 

7.2.2扩展线性表存储表示

类型描述

typedef enum { ATOM，LIST } ElemTag;
      typedef struct GLNode
      { ElemTag tag; //区别原子结点tag==0表结点tag==1
        union  
        { AtomType  atom;   //原子结点的值
          struct GLNode * hp；//表结点的表头指针
        };
        struct GLNode * tp; //相当于线性链表的next，指向该结点的下一个结点
      }*GList;