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

时间：2010-07-16 来源：bluedrum

Andrew Huang [email protected] 一.什么是广义表？ -------------------------------------------------------------------------------- 广义表(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个。二.广义表数据构造二叉树三.广义表的链式实现。