逻辑结构？存储结构？傻傻分不清……

对于数据结构与算法的学习，我相信不管是新手还是老手，都会对“逻辑结构、存储结构”产生很多的疑问。你可能觉得不就是两个简单的概念嘛，早就了然于胸了。

Wait！

先不要急着下定论，我们还是先来看一道题目。实践是检验真理的唯一标准嘛！（萌新略过）

• 例题1

3xoodT

选哪个呢？是不是很纠结？有答案了没？

别急，我们再来看一道题。

• 例题2

TVmcFc

如果这两道题你觉得very easy，那么接下来的内容，恭喜你，不必再看了；如果仍然觉得哪里有问题，以及不敢确定自己的答案，还是来跟着我过一遍知识吧，在阅读的过程中，思考上面的两个问题。

注：以上例题来源于王道：《数据结构与算法》

逻辑结构：我不要你觉得

你应该知道，数据结构的三要素是：逻辑结构、存储结构、数据运算。

首先我们来回答一个问题：什么是逻辑结构呢？

从定义的角度来说，所谓逻辑结构，指的就是数据之间的逻辑关系，从逻辑关系上来描述数据。逻辑结构又包括线性结构和非线性结构两种，线性表是一种典型的线性结构，图是一种典型的非线性结构，特别注意：逻辑结构与存储结构无关。

看了定义是不是觉得非常混乱？

那么，你觉得什么是逻辑上的关系呢？我们来思考这个问题：”顺序表是逻辑结构吗？“

如果你认为，”线性表是一种线性结构，顺序表是属于线性表的，所以，顺序表应该是一种逻辑结构。“

很不幸，这种想法是非常错误的！！！

所以，我们在判断逻辑关系的时候，不要想当然，不要你觉得，应该理性判断。

我们可以认为逻辑结构是一种”依赖关系“，描述的仅仅是数据元素之间的关系，除了描述数据元素之间的关系外，再也没有其他的含义了。

比如，我们回顾刚刚的问题，”顺序表是逻辑结构吗？“

答案：不是。虽然顺序表是一种线性结构，但是你要注意，顺序表背后包含着”顺序存储的意思“。也就是说，顺序表既能够描述逻辑结构，也能够描述物理结构。所以，这是一种混合类型。

再来，”有序表是逻辑结构吗？“

显然，是的。有序表指的是数据元素按照一定顺序排列的线性表，除了描述“两个元素之间有序”的依赖关系以外，它再也没有别的意思了。

所以，你是不是能够体会到逻辑结构的独特之处了？

总结一下，逻辑结构指的就是数据元素之间的关系，这种关系可以是如下的几种：

• 没有关系：一个集合，里面的元素除了同属一个集合以外，没有其他任何关系。很明显，这是一种非线性的关系。
• 一对一：线性结构。线性结构中的元素都是一对一的。你可以简单的把它理解为一个串，仅有一个开端和一个结尾结点，并且除了开端和结尾外，每个结点只能有一个前驱结点和一个后继结点。比如字符串，如图所示：

WJse0V

• 一对多：图或者树就是两种典型的一对多的非线性关系。从图中可以看到，非线性结构的树和图中的结点除了第一个结点和最后一个结点以外，其余结点能够有一个或者多个前驱和后继。

qro9Uz

最后，如果让你判断一个名词是否为逻辑结构，我们应该怎么做？可以考虑以下几点：

• 首先，判断名词是属于线性结构还是非线性结构
• 其次，由于数据的逻辑结构是独立于存储结构的，所以考虑名词背后是否暗含存储结构？如：顺序表。（别急，关于存储结构，我们马上就讲）如果暗含存储结构，那么一定不是逻辑结构。

存储结构：我要我觉得

存储结构就非常好理解了，存储结构，也被称作是物理结构，表述的是含有某种逻辑关系的元素在计算机中存储的方式。可以理解为数据元素在存储器上的排列方式。

总的来说，存储结构只有四种，分别是顺序存储、链式存储、索引存储、散列存储（哈希存储）。

1. 顺序存储：所谓顺序存储，就是把逻辑上相邻的数据元素，存储到计算机的存储器上时，在物理上也是相邻的。最简单的实现就是数组，我们可以直接把一列元素存储在数组中。显然，这种实现存储的方式优点是：能够实现随机存取，即通过数组的下标，我们能够很轻松的找到数据元素获取或者修改它。
2. 链式存储：链式存储，就是我们所熟知的链表。我们无需像顺序存储那样，单独开辟一片连续的存储空间，只需要用到的时候直接分配空间，用指针来实现整个一对一逻辑结构的实现。这样子做虽然节省了空间、动态扩容，但是问题也很明显：当你想找到编号为n的元素，只能从表头开始遍历。

uB0G8b

1. 索引存储：这种存储方式类似于我们的书和目录的关系。比如书中”第五章“的内容在35页，我们想要找到它，只需要浏览目录，然后通过页码找到相关的内容。一般存储的时候都是【关键字，地址】这种形式。
2. 散列存储：对于散列存储，我们可以设想这样一个场景。博主我买了一套房子（买不起的，别想了.jpg），本来买的时候选中了0322这间，但是由于施工问题，整栋楼是从0000开始编号的（买的时候是按照0001编号），这样就造成了一个问题，现在的0322号已经不是我的了，我的是0321。就是原来的房间号减去1。所以，散列存储实际上就是做了一个函数关系的映射，由x去找y，如果y=x+1，那么x=1的元素就应该去y=2位置寻找。这样理解起来应该没有困难了吧。

回过头来，我们看文章开头的第二个问题：

A选项，循环队列，实际上是用数组实现的，也就是顺序存储；B选项，链表，很明显，这是一种链式存储；C选项，哈希表，这已经是明示了——哈希存储；最后一个，栈是一种很重要的逻辑结构，既能够用顺序存储实现也能够由链式存储实现。所以，答案就是D。

存储结构的核心是：只有这四种，我要我觉得，再也没有其他的可能了。