下载掌阅APP，畅读海量书库
立即打开
什么是数据结构
在现实生活中，数据元素之间的关系复杂而多样，但数据元素之间的逻辑关系仅可以分为4种：无关系、一对一关系、一对多关系、多对多关系，这4种逻辑关系统称数据的逻辑结构。
根据数据元素之间逻辑关系的不同，数据的逻辑结构可分为以下4类，如图1-3所示。
● 集合 。集合包含的所有数据元素之间无关系，即数据元素的次序是任意的。集合中各个数据元素均是“平等”的，它们属于同一个集合，如图1-3（a）所示。例如，在操场上玩耍的学生，快递车上运输的快递包裹，在展览馆参观的游客等。又如，火车票管理系统中的每个旅客都是“平等”的，旅客之间没有关系。
● 线性结构 。线性结构包含的数据元素之间存在一对一的关系，即数据元素构成一个有序序列。若存在多个数据元素，则第一个数据元素之前没有数据元素，最后一个数据元素之后也没有数据元素。除了第一个数据元素和最后一个数据元素，其余数据元素前面都有唯一的一个数据元素（称为前驱），后面也都有唯一的一个数据元素（称为后继），如图1-3（b）所示。例如，《水浒传》中的108条好汉形成了一个数据集合，他们的排列是有次序的，宋江排第一，卢俊义排第二，以此类推。又如，在火车票管理系统中，列车运行计划里每个车次所途经的站点是一个接一个的，形成了一个有序序列。
● 树形结构 。树形结构包含的数据元素之间存在一对多的关系，即数据元素之间形成层次关系。除了根元素，每个数据元素有且仅有一个前驱，后继数目不限，根元素没有前驱，如图1-3（c）所示。例如，一个家族的家谱就可以表示为树形结构，老祖宗是树根，老祖宗的儿子是老祖宗的后继，每个人可以有多个儿子，因此后继数目不限，但每个人只能有一个父亲，因此只有一个前驱。
● 图形结构 。图形结构包含的数据元素（顶点）之间存在多对多的关系，即每个数据元素的前驱和后继数目都不限。图形结构是最常见的数据逻辑结构，如图1-3（d）所示。例如，互联网的拓扑关系就是一个图形结构；朋友关系也是一个图形结构。又如，在火车票管理系统的列车运行图中，站点之间要么直接连接，要么不直接连接，构成图形结构。
图1-3 数据的逻辑结构示意图
数据的逻辑结构对应以下4类常见的操作（运算）：
● 构造和析构 ，包括数据结构的创建、初始化，以及必要的结构操作；
● 属性操作 ，包括读取数据结构各基本属性的值；
● 查找 ，包括特定搜索、访问和遍历数据元素的操作；
● 更新 ，包括插入、删除或修改数据元素的内容或更新数据元素之间的关系。