1.2.4 数据的逻辑结构

数据的逻辑结构是从逻辑关系（主要是指相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。在不会产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构主要分为以下几类。

1. 集合

集合是指数据元素之间除了“同属于一个集合”的关系，别无其他关系。

2. 线性结构

线性结构是指该结构中的结点之间存在一对一的关系，其特点是开始结点和终端结点都是唯一的。除了开始结点和终端结点，其余结点都有且仅有一个直接前驱，有且仅有一个直接后继。顺序表就是一种典型的线性结构。

3. 树形结构

树形结构是指该结构中结点之间存在一对多的关系，其特点是每个结点最多只有一个直接前驱，但可以有多个直接后继，可以有多个终端结点。二叉树就是一种典型的树形结构。

4. 图形结构

图形结构或称为网状结构，是指该结构中的结点之间存在多对多的关系，其特点是每个结点的直接前驱和直接后继的个数都可以是任意的。因此，图形结构可能没有开始结点和终端结点，也可能有多个开始结点和多个终端结点。

树形结构和图形结构统称为非线性结构，该结构中的结点之间存在一对多或多对多的关系。由线性结构、树形结构和图形结构的定义可知，线性结构是树形结构的特殊情况，而树形结构又是图形结构的特殊情况，以上各类结构对应的示例如图1-2所示。

例1-2　有数据结构B₁=(D, R)，其中：

D = {a, b, c, d, e, f, g, h, i, j}

R = {r}

r = {(a, b), (a, c), (a, d), (b, e), (c, f), (c, g), (d, h), (d, i), (d, j)}

画出其逻辑结构。

解　对应B₁的逻辑结构如图1-3所示。从该例中可以看出，每个结点有且仅有一个直接前驱（除根结点外），但有多个直接后继（叶子结点可看作具有0个直接后继）。这种数据结构的特点是数据元素之间的关系为一对多关系，即层次关系，因此是一种树形结构。

例1-3　有数据结构B₂=(D, R)，其中：

D = {a, b, c, d, e}

R = {r}

r = {(a, b), (a, c), (b, c), (c, d), (c, e), (d, e)}

画出其逻辑结构。

解　对应B₂的逻辑结构如图1-4所示。从该例中看出，每个结点可以有多个直接前驱和多个直接后继。这种数据结构的特点是数据元素之间的关系为多对多关系，即图形关系，因此是一种图形结构。