数据的逻辑结构

在上面提到数据分为逻辑结构和物理结构，其中逻辑结构有4种基本类型：集合、线性结构、树形结构和图形结构。线性表和树是最常用的两种高效数据结构，许多高效的算法都能用这两种数据结构来设计实现。下面通过实例来进一步理解后3类数据结构。

1.线性结构

如图1-2所示的英文字母表描述的逻辑结构是线性结构，表中的每一个英文字母是一个数据元素。该表中a和b相邻位于b的前面；对应的b位于a的后面。类似地，表中其他数据元素之间也可以得到这个结论。所以说，每个元素之间存在唯一的顺序关系。

如图1-3所示的队列示意图描述的是另一种线性结构。除了第一个和最后一个元素外，每个元素前后都只有一个元素，且元素之间存在唯一的顺序关系。

从图1-3可以看出，线性结构的逻辑关系包括以下几点。

·在非空的线性结构中，有且仅有一个开始结点a1,它没有直接前趋，而仅有一个直接后继a2.

·有且仅有一个终端结点an，他没有直接后继，而仅有一个直接前趋an-1。

·其余的内部结点ai(2≤i≤n-1)都且仅有一个直接前趋ai-1和一个直接后继ai+1.

2.树形结构

如图1-4所示描述的逻辑结构是树形结构图。树形结构是一种非线性结构，树中包含一个数据元素及若干指向其子树的分支。树中结点的关系是一对多的关系，类似于现实世界中导致的树。

从图1-4可以看出，树形结构的逻辑特征包括以下几点。

·其中有且只有一个称为根(root)的特定结点，它没有直接前趋，但有零个或多个直接后继，如图1-4(a)树的根为A。

·其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1、T2、T3、···、Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个相同的直接前驱，但有零个或多个直接后继。例如，图1-4(a)树Ti为最左边含有B、E、F、J、K的分支，T2为中间含有C、G的分支，而T3为最右边含有D、L、I的分支。

3.图形结构

如图1-5所示描述的逻辑结构是图形结构。图也是一种非线性结构，它是由非空的顶点集合和一个描述顶点之间的关系—边(或者弧)的集合组成。

从图1-5可以看出，图形结构的逻辑结构特征为：任何一个结点都可以有大于或等于零个前驱和大于等于零个后继。