【一】、什么是数据结构

前言

令人头疼的书啊，一切尽在不言中。

对数据结构的理解

首先从定义上来说的话，好像对数据结构没有什么一个统一的、标准的答案，我找了好几本书，挑了一个我认为还计较好理解的定义：

数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。

如果你没接触过数据结构，你看了定义能看懂吗？如果你能看懂，我很佩服你，我反正是不行，不过现在因为接触的东西比较多，听得多了，看了也能理解。我觉得对于新手，应该先让新手去理解，等有了自己的理解之后再看官方定义的话，效果会比较好，反正我是这么认为的。我用生活中的例子来解释什么是数据结构吧：
举例：如何在书架上摆放图书？
也就是说，现在有一些书架，还有一堆图书，你要怎样把它们放到书架上去呢？换言之说，有一堆数据，给了你一些存储空间，你要怎么把这些数据存起来呢？
其实这个问题问的不科学，因为你不知道所谓的书架是长什么样，可能是下面图片中的任意一种。

所以你就知道了，当有人问你一个数据怎么组织的时候，其实是跟这个数据的规模有关系的。不一样规模的问题，它处理起来的难度就不一样。难在什么地方呢？难不在说你要把它怎么放，而在于放这个书是为了做事情用的，所以说图书的摆放其实跟两个操作直接相关：

操作一：新书怎么插入
操作二：怎么找到某本指定的书

方法一：我不知道你们是怎样考虑的，我第一个感觉就是随便放，随便放一个好处就是：新书怎么插入，这个操作是非常简单的，哪有空就放哪，最简单的方法就是把所有的书一本一本挨着放，所以呢，所有的新书哪里有空放哪里，So easy！放起来简单，但第二个操作怎么办，如何查找？那就会成为一件很恐怖的事……累死你！什么时候累死呢，其实如果只是一个很小的书架，倒也累不死，但如果是上面第三张那样的书城，然后你想象，里面所有的图书都是随便放的，然后有人问你，这个书城里有没有某一本书，其实那本书没有，但是你忘了有没有，那你怎么能确定它到底有没有呢？你就只好从头到尾把每一本书都过一遍，然后才能叹一口气说……唉，不好意思，没有这本书。

方法二：那我们有没有稍微聪明一点的解决方法呢？就是怎样让我找书找的方便呢？第二个方法，就是按照书名的拼音字母顺序排放，有了这个字母序以后，查找就方便多了。一个最聪明的方法是二分查找什么是二分查找：比如说现在有一长排的书放在你面前，然后我们找一本叫《数据结构》的以S开头的书，那我先从这一排的中间找一本书出来看它的书名的首字母，假如说是《离散数学》，以L开头的书，那我们知道，S在L的后面，所以《离散数学》前面的书我就不用管它了，我的查找范围缩小了一半，从L开始往后找，然后再找这一半的中间，比如找到的一本书是《网络爬虫》，以W开头的，那S在L和W中间，《网络爬虫》后面的书我就不用管了，于是我的查找范围又缩小了一半，以此类推，我可以每次都找，然后跟中间这个比，很快就会把范围缩小到一本书上，我就会知道这本书到底是有还是没有。这个方法比前面的方法聪明多了，它很好的解决了查找的问题。但是，问题又来了，新书来了怎么插入呢？它就会成为新的令人头疼的问题。比如说，我新买了一本书叫《阿Q正传》，是以A开头的，呃……惨了,那我们得把几乎所有的书往后一本一本的错位，一直到前面留出一个空挡，把新书插进去，这个似乎也很头疼。

方法三：那如何找一个两全其美的方法呢？我们来想想，图书馆里是怎样来摆书的，我们假如说去图书馆，找《数据结构》，要怎么找，你不可能是从第一本开始找，也不可能是随便中间摸一本找，你进到图书馆里，第一件事情要找的是计算机类的书在哪里对不对？图书馆里的书通常是按照书的类别来分的，比如说我们有社会科学类、文学类、艺术类、理科、工科等，然后工科下面可能还会分的再细一点，比如说我们计算机类可能就分在工科的下面，这种分法有什么好处呢？把书架划分成几块区域，每快区域指定摆放某种类别的图书，在每种类别内，按照书名的拼音字母顺序排放，这样不管我在每一个类里做什么样的操作，总归来说，图书的规模小了很多，跟整个图书馆的规模相比，我是某一类的，无论是查找还是插入，都是非常方便的。查找呢，就是在二分查找之前，我们先定一个类别，然后在一个类的一个小范围里面做二分查找，就可以更快的找到我们要查找的书了。如果是插入，也是先定类别，用二分查找来确定一下它应该被插在什么位置，然后移空位这件事可能还是要做的，但是总归比我们刚开始要移的书的数量少多了。

那现在问题又来了：

问题一：空间如何分配？
问题二：类别应该分多细？

我们分的各种类别的书，它的藏书量是不一样的，你是统一都给它分……还是每一类都多少个书架，事先分好吗？这也是一个很头疼的问题，我太难了，你如果书架给多了，就会有一些空间始终空在那浪费着，你如果书架给小了，新书来的时候要不断地加新柜子，很讨厌。还有分类别要分多细的问题，你要是分的比较粗，那么同一类里面的书就会有很多，那你的工作量还是会很大，要是想减少工作量，最好还是类别分的细一点，但是类别一分细，就会有副作用，类别太多了，图书的量一多，也是麻烦。

说这些问题是想说明：

解决问题方法的效率，跟数据的组织方式是直接相关的

那我这介绍数据结构的组织方式的时候，其实有两个概念：
一、关于数据对象的逻辑结构
比如说，我们一开始把书架想象成简单的一长条，这么一层的架子，然后所有的书是一个一个挨着放的，除了一头一尾的书以外，每一本书的前面和后面都只有一本书，如果每一本书都有一个编号的话，那么这一个编号对应的就是一本书，那么这种结构是一对一的结构，我们管它叫线性结构。

另外一种组织方式是上面说的第三种方法，就是先把图书分类，如果我给每一个类一个编号的话，那么这一个类别的编号里面对应着很多本书，那么这是一个一对多的逻辑结构，这个结构有个名字叫做树。

再说图书馆，假设我们还统计这样一些信息：这一本书都有那些人买过，买了这本书的人还买过其它的什么书，于是呢，其实是一本书对应着很多人，而一个人又对应了很多本书，这是一个多对多的、很复杂的一个关系网，那么这个关系网对应的逻辑结构叫叫做图
二、关于对象的物理存储结构
除了逻辑结构之外，我们还有数据对象再计算机里面的物理存储结构，也就是我们说的这些逻辑结构在机器的内存里到底要怎么放，是连续放呢还是东一个西一个隔开放呢？也就是说用一个数组来存它呢，还是用一个链表来存它呢？这个就属于物理存储结构。