数据结构逻辑结构和物理存储结构的一个疑问

Question

数据结构逻辑结构和物理存储结构的一个疑问
最近看数据结构相关内容时, 看到有 逻辑结构和物理存储结构这么两种结构
比较好奇的是, 这个逻辑结构和物理结构到底是什么关系

比如 线性表这种逻辑结构, 它可以有 顺序存储和链式存储 这两种物理存储结构
但是像 树形结构, 它也可以有 顺序存储和链式存储 这两种物理存储结构

假设要做一个数据存储然后用来搜索, 用线性表的顺序存储结构? 还是树形结构的顺序存储?
线性和树形 既然底层都能是顺序存储结构 那到底区别在哪儿

Answer 1

先来看线性表吧，所谓顺序存储就是用『数组』来实现的，链式存储使用『链表』来实现的，结构大概如下：

array = [1,2,3,4,5]
list = (1)->(2)->(3)->(4)->(5)

而树形结构，拿下面这个二叉树来说:

     b
    / \
   a   c

顺序存储需要用三个『数组』来实现：

ele = ["a","b","c"]
left = [null,0,null]
right = [null,2,null]

你看啊：
0号位存的元素是ele[0]为"a"，0号位的左节点位置left[0]为null，右节点的位置right[0]为null；
1号位存的元素是ele[1]为"b"，1号位的左节点位置left[1]为0，进而推出1号位左节点的元素为ele[left[1]]为ele[0]也就是"a"，同理1号位的右节点的元素就是ele[right[1]]为ele[2]也就是"c"；
2号位存的元素是ele[2]为"c"，2号位的左节点位置left[2]为null，右节点的位置right[2]为null；
这就是一个数组来实现的二叉树。

链表实现的二叉树这里就不展开了。

可以看到，对于需要搜索的线性表，最好用数组来实现，毕竟可以一次性排序之后用二分查找，而链表排序很麻烦，只能从头搜到尾；
而对于需要搜索的树形结构，一般用链式存储，毕竟树形结构（排序二叉树、平衡树）可以很方便的往里面插入、删除数据，并且插入、删除、搜索效率都是O(logN)，数组实现的二叉树虽然效率一样，不过一开始不知道数据的规模，难以估计三个数组需要开多大的空间出来。

需要注意的是数组实现的线性表，插入、删除的效率很低为O(N)，所以如果你需要高效率的插入、删除、查找数据，你还需要再学习一下平衡树的知识，这里就不展开了。

以上我大概说明白了吗？希望能帮助到你。

Answer 2

我们一般说的数据结构首先就有两类，一是逻辑上的，二是物理上的。

逻辑上的就是那么三种，一对一的线性表，一对多的 tree，多对多的图。

物理上的就那么两种，顺序，和链式。什么叫物理的逻辑结构呢。就是说，逻辑上连续的 node 在内存中的地址，是连续的，还是不连续的。连续的叫顺序存储，不连续的叫链式存储。

知道这个前提后，我们再来看，我们一般说的线性表，只是指逻辑上一对一的，那自然在物理上可以连续，也可以不连续，连续的一般就是 array，不连续的一般就是 linked list。

在思考什么时候选择连续的，还是不连续的存储，首先我们要知道一点，我们平时是怎么访问一块内存的数据的？

显然，我们要访问一块内存的数据，我们需要找到这块内存，我们就需要它的 address，无论是连续还是不连续都是这样的。

那么连续的内存，我们是怎么访问数据的呢？我们是先知道第一块内存地址，也就是所谓的首地址，然后我们要知道其他内存距离第一块内存有多远，即偏移量，然后我们再加上首地址，就找到了这块内存。

那么我们要访问一块连续存储中的地址，我们需要首地址和偏移量，首地址和偏移量我们是容易知道的，所以连续的内存我们可以谁时访问哪块内存，也就是所谓的随机访问。

而不连续的内存呢？我们又是怎么访问一块内存的地址呢？由于内存不是连续的，所以对于任何一个 node，要访问它下一块内存，我们都得知道下一块内存的地址，而我们一般是怎么做的呢？很简单，我们把下一块内存的地址存在这个 node 里。

那么我们要访问一块不连续内存中某个内存，我们需要怎么做呢？我们需要知道前一个 node 的地址，因为要访问内存的地址在上一个 node 里，那么怎么才能访问上一块内存呢？很显然，我们一直这样推下去，我们就得知道第一块内存，而且对于任何一块内存，如果我们要访问其中一块的话，我们都得从第一块开始访问，这就是所谓的，不支持随机访问。

现在如果我们有了一个需求，要存线性表，问你，我们选择顺序存储还是链式存储呢？你可能就有点出发点了，根据上面的我们知道，如果我们要经常对其中某块内存进行查找的话，显然顺序存储是比较好。

这只是其中一点，还有一点。。。就是增删，容量。。。Todo