数据结构 ---广义表及实现

Andrew Huang

 

一.什么是广义表？

--------------------------------------------------------------------------------

 

  广义表(generalized list.)是指一种顺序存储结构,它有如下特点：广义表的结点 可以是基本数据(原子Atom)，又可以是另外一个广义表。这样可以在广义表上实现任何可以用递归来实现的数据结据，最典型就是广义表与二叉树的结构的互换。又因为广义表是顺序结构。因此可以用数组或文件来存储和操作广义表。

 

 

      

1.1 广义表的抽象表示书写格式:

      广义表通常用圆括号括起来，用逗号分隔其中的元素。
    　为了区分原子和广义表，书写时用大写字母表示广义表(名)，用小写字母表示原子。

      下面是具体的书写规则。

 

     　① E=()
     　E是一个空表，其长度为0。
　　    ② L=(a，b)
     　L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
　　   ③ A=(x，L)=(x，(a，b))
     　A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
　　   ④ B=(A，y)=((x，(a，b))，y)
　     B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
　　   ⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
     　C的长度为2，两个元素都是子表。
　  　⑥ D=(a，D)=(a，(a，(a，(…))))
     　D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。

 

 

 

    广义表层数：即最大子表的层数,或者指一个表的"深度"是指表展开后所含括号的层数。上述表的层数分别是表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。

 

 

带名字的广义表表示
    　如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字(大写)，于是上例中的各表又可以写成：
①E()
②L(a，b)
③A(x，L(a，b))
④B(A(x，L(a，b))，y)
⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
⑥D(a，D(a，D(…)))

 

  1.2 广义表的图示：

    若用圆圈和方框分别表示表和单元素,并用线段把表和它的元素(元素结点应在其表结点的下方)连接起来,则可得到一个广义表的图形表示。例如,上面五个广义表的图形表示如下图所示

          

  或者简化用字符描述

 

 D(A(c), B(e), C(a, L(b, c, d))) 简要图示
 
               D
            /  |  \
            A  B   C
            |  |  /  \
            c  e  a  L
                   / | \
                  b  c  d

  

          

J1(J2(J1, a, J3(J1)), J3(J1)) 简要图示

            J1
          /    \
          J2    J3
        / | \    |
        J1 a J3  j1
              |
              J1

        

         

   1.2 广义二叉表

   比如用广义表表二叉树，有一定的规范，这称为广义二叉链表(Generalized Binary Linked List,简称GBL).

     即广义表中子表的元素最大不超过2个。

 

 

二.广义表数据构造二叉树

 

 

三.广义表的链式实现。