逻辑结构与物理结构

逻辑结构

简单的来说，逻辑结构就是数据之间的关系。逻辑结构常见有四种类型：集合结构，线性结构，树形结构，图形结构。

集合结构

表面意思，没有什么深刻意义，就是数据元素同属一个集合，单个数据元素之间没有任何关系。如下图所示。

线性结构

线性结构类似于线性关系，也就是说，线性结构中的数据元素之间是一对一的关系。注意：重点在一对一。如下图所示。

树形结构

树形结构中的数据元素之间存在一对多的关系。（各元素及元素关系所组成图形类似于树状图）。注意：关系为一对多。如下图所示。

图形结构

数据元素之间是多对多的关系。如下图所示。

物理结构

又叫存储结构，分为两种，一种是顺序存储结构一种是链式存储结构，指的是数据在物理存储空间上选择集中存放还是分散存放。假设要存储大小为 10G 的数据，则集中存放就如图 3a) 所示，分散存放就如图 3b）所示。

如果选择集中存储，就使用顺序存储结构；反之，就使用链式存储。至于如何选择，主要取决于存储设备的状态以及数据的用途。

我们知道，集中存储（顺序存储）（底层实现使用的是数组）需要使用一大块连续的物理空间，假设要存储大小为 1G 的数据，若存储设备上没有整块大小超过 1G 的空间，就无法使用顺序存储，此时就要选择链式存储，因为链式存储是随机存储数据，占用的都是存储设备中比较小的存储空间，因此有一定几率可以存储成功

并且，数据的用途不同，选择的存储结构也不同。将数据进行集中存储有利于后期对数据进行遍历操作，而分散存储更有利于后期增加或删除数据。因此，如果后期需要对数据进行大量的检索（遍历），就选择集中存储；反之，若后期需要对数据做进一步更新（增加或删除），则选择分散存储（链式存储）。

逻辑结构与物理结构这两者并不冲突，一个指的是数据之间的关系，而另一个指这种关系在计算机中的表现形式。比如，线性表中的栈，数据元素之间的关系是一对一的，除头和尾结点之外的每个结点都有唯一的前驱和唯一的后继，这体现的是逻辑结构；而对于栈中的结点来说，它们可以顺序存储（也就是顺序栈），取一段连续的存储空间，将栈结点按顺序存入，每个结点和其前驱和后继在物理上都是相邻的。同时，栈结点也可以链式存储（链栈），每个结点中包括数据域和指针域，而指针域就是用来指向其后继的，在访问时就可以通过指针来找到其后继进行访问，每个结点之间物理上可以相邻也可以不相邻。