逻辑结构
我们从上可以发现:上面这三种逻辑结构之间的节点与节点之间的关系是不一样的,对于线性结构来说,节点之间的关系是一对一的;树形结构的节点是一对多;图形结构的节点是多对多的关系。
线性结构:开始节点和终端节点都是唯一的,我们可以把第一个节点认为是开始节点,第四个节点认为是终端节点。除了开始节点和终端节点以外,其余节点都有且仅有一个前驱节点,有且仅有一个后继节点。对于第二个节点来说,它的前驱节点就是第一个节点,它的后继节点是第三个节点。
树形结构:开始节点唯一,终端节点不唯一,开始节点就是指的根节点,终端节点就是指的最下面的节点。除终端节点以外,每个节点有一个或多个后继节点,在根节点的左节点中有三个后继节点,右节点有两个后继节点,除开始节点外(根节点没有前驱节点),每个节点有且仅有一个前驱节点。
图形结构:没有开始节点和终端节点,所有节点都可能有多个前驱节点和多个后继节点,也就是说形成了一个多对多的图形结构,我们在图形结构中也看到了,节点之间是相互连接的。
下面这张图是数据逻辑结构的层次组织关系
数据逻辑结构主要分为线性结构和非线性结构,在非线性结构中又包括了之前讲过的树和图两种结构,在树结构中又分为一般树和二叉树,图结构又分为有向图和无向图;在线性结构中包括了一般的线性表,受限线性表,线性表推广等,在受线性表中分为栈和队列。因此我们应该根据数据逻辑结构把所有的数据结构中的内容通过上图的方式组织起来,起码做到对这张图有个印象,这将会指导后面的学习。
另外,我们在学习掌握数据的逻辑结构时,还应该掌握逻辑结构的二元组表示方法。对于线性结构,树形结构,图形结构都可以通过这种二元组来表示.
存储结构
数据的存储方式可分为线性表、树和图三种存储结构,而每种存储结构又可细分为顺序存储结构和链式存储结构。数据存储方式如此之多,针对不同类型的数据选择合适的存储方式是至关重要的。
那么,到底如何选择呢?数据存储结构的选择取决于两方面,即数据的逻辑结构和存储结构(又称物理结构)。
逻辑结构
数据的逻辑结构,简单地理解,就是指的数据之间的逻辑关系。
例如,图 1 显示是一张家庭的成员关系图,从图中可以看到,张平、张华和张群是兄弟,他们的父亲是张亮,其中张平有两个儿子,分别是张晶和张磊。
以上所说,父子、兄弟等这些关系都指的是数据间的逻辑关系,假设我们要存储这样一张家庭成员关系图,不仅要存储张平、张华等数据,还要存储它们之间的关系,两者缺一不可。
一组数据成功存储到计算机的衡量标准是要能将其完整的复原。例如图 1 所示的成员关系图,如果所存储的数据能将此成员关系图彻底复原,则说明数据存储成功。
- 线性表用于存储具有“一对一”逻辑关系的数据;
- 树结构用于存储具有“一对多”关系的数据;
- 图结构用于存储具有“多对多”关系的数据;
由此,我们可以通过分析数据之间的逻辑关系来决定使用哪种存储结构,但具体使用顺序存储还是链式存储,还要通过数据的物理结构来决定。
存储结构(物理结构)
数据的存储结构,也就是物理结构,指的是数据在物理存储空间上选择集中存放还是分散存放。假设要存储大小为 10G 的数据,则集中存放就如图 3a) 所示,分散存放就如图 3b)所示。
如果选择集中存储,就使用顺序存储结构;反之,就使用链式存储。至于如何选择,主要取决于存储设备的状态以及数据的用途。
我们知道,集中存储(底层实现使用的是数组)需要使用一大块连续的物理空间,假设要存储大小为 1G 的数据,若存储设备上没有整块大小超过 1G 的空间,就无法使用顺序存储,此时就要选择链式存储,因为链式存储是随机存储数据,占用的都是存储设备中比较小的存储空间,因此有一定几率可以存储成功。
并且,数据的用途不同,选择的存储结构也不同。将数据进行集中存储有利于后期对数据进行遍历操作,而分散存储更有利于后期增加或删除数据。因此,如果后期需要对数据进行大量的检索(遍历),就选择集中存储;反之,若后期需要对数据做进一步更新(增加或删除),则选择分散存储。