1.2.1　数据的逻辑结构

什么是数据结构

在现实生活中，数据元素之间的关系复杂而多样，但数据元素之间的逻辑关系仅可以分为4种：无关系、一对一关系、一对多关系、多对多关系，这4种逻辑关系统称数据的逻辑结构。

根据数据元素之间逻辑关系的不同，数据的逻辑结构可分为以下4类，如图1-3所示。

● 集合。集合包含的所有数据元素之间无关系，即数据元素的次序是任意的。集合中各个数据元素均是“平等”的，它们属于同一个集合，如图1-3（a）所示。例如，在操场上玩耍的学生，快递车上运输的快递包裹，在展览馆参观的游客等。又如，火车票管理系统中的每个旅客都是“平等”的，旅客之间没有关系。

● 线性结构。线性结构包含的数据元素之间存在一对一的关系，即数据元素构成一个有序序列。若存在多个数据元素，则第一个数据元素之前没有数据元素，最后一个数据元素之后也没有数据元素。除了第一个数据元素和最后一个数据元素，其余数据元素前面都有唯一的一个数据元素（称为前驱），后面也都有唯一的一个数据元素（称为后继），如图1-3（b）所示。例如，《水浒传》中的108条好汉形成了一个数据集合，他们的排列是有次序的，宋江排第一，卢俊义排第二，以此类推。又如，在火车票管理系统中，列车运行计划里每个车次所途经的站点是一个接一个的，形成了一个有序序列。

● 树形结构。树形结构包含的数据元素之间存在一对多的关系，即数据元素之间形成层次关系。除了根元素，每个数据元素有且仅有一个前驱，后继数目不限，根元素没有前驱，如图1-3（c）所示。例如，一个家族的家谱就可以表示为树形结构，老祖宗是树根，老祖宗的儿子是老祖宗的后继，每个人可以有多个儿子，因此后继数目不限，但每个人只能有一个父亲，因此只有一个前驱。

● 图形结构。图形结构包含的数据元素（顶点）之间存在多对多的关系，即每个数据元素的前驱和后继数目都不限。图形结构是最常见的数据逻辑结构，如图1-3（d）所示。例如，互联网的拓扑关系就是一个图形结构；朋友关系也是一个图形结构。又如，在火车票管理系统的列车运行图中，站点之间要么直接连接，要么不直接连接，构成图形结构。

图1-3　数据的逻辑结构示意图

数据的逻辑结构对应以下4类常见的操作（运算）：

● 构造和析构，包括数据结构的创建、初始化，以及必要的结构操作；

● 属性操作，包括读取数据结构各基本属性的值；

● 查找，包括特定搜索、访问和遍历数据元素的操作；

● 更新，包括插入、删除或修改数据元素的内容或更新数据元素之间的关系。