老狗啃骨头之数据结构-引言

  最近有不少朋友都在刷LeetCode 的题，挺有意思，想上学那会儿，严蔚敏老师的那本数据结构，翻得是相当熟练，顺势去鼓捣 ACM ，颇有趣味。工作之后，这有些东西却是慢慢模糊起来，于是想弄一波笔记，给自己长长记性，重温昔日的乐趣。先贴个严老师那时候课本的样子，致敬一下：

  数据结构，是咱们计算机科班的必修课，上学那会儿不少同学一开始也是很头痛，为什么呢？个人理解，数据结构这门课，难，倒也不难，但它是一个概念的重塑，所以一开始，对于不少同学就是折磨。
  我们存在的现实世界，是具象的，生活中的各种东西，是几十年反复加强的概念，锅碗瓢盆啤酒饮料矿泉水…但计算机是一个抽象世界，计算机是尝试用抽象的数据，来描述这个具象的世界，我们说，学计算机、学编程，这个东西一定要搞好，现实世界里的概念是如何在计算机里体现的，这时候，数据结构，就是这个体现最基础的东西，其重要性不言而喻。
  也有人问，数据结构怎么学才能学好啊，其实这种基础的东西，没什么捷径，多练习，在校同学一定要趁着没啥事儿的时候，多照着书撸撸代码，严蔚敏的那本书就挺好了。就好比我们说一个数组，你在怎么打比喻，再怎么去解释，去理解，都是比较肤浅的，直接写个程序，往里塞元素，塞不进去，往里取元素，取不了… 报几下异常，再弄个排序左左右右玩一轮，基本这辈子都忘不了数组这个东西了。

  数据结构，不同教材都尝试做一个比较贴又准确的名称定义，但作为一个老狗，再回头去看看，感觉有些还是拧巴，我们不管教材了，当然看看还是好。聊数据结构，就不能不提算法，数据结构就是各种特点的概念盒子、架子，是物件，摆在那里，是个死的，是一个被定义但没有灵魂的东西；算法就是各种折腾的方式、使用的技巧，死的东西折腾起来，就活了，生灵活现！
  还拿数组说事儿，一个数组，放在那里有什么意思，一定要玩起来，怎么查怎么找，左一个排序，右一个查找，怎么能再快点，还能不能再快点，出错了再试试….于是，贤者云：

数据结构 + 算法 = 程序
  对，说一百圈，我们就是要搞程序的，絮叨完之后，接下来会有几篇笔记，我们将通过程序实践，来重温那些典型的数据结构及其算法。

  数据结构，就是数据的结构。我们说数据在计算机里，我们一般说其逻辑结构，简单归类，主要是两种：线性结构和非线性结构。
  线性结构，线，顾名思义，一条绳，一根棍，一节管子，一组高铁… 现实中可以明确找出两头的，必须按着顺序来的，都可以拟化成线性结构，所以线性结构一般这么去抽象：
    线性结构是一个有序集合；
    有且仅有一个开始结点和一个终端结点；
    所有结点都最多只有一个直接前结点和一个直接后结点。
  我们经常说的，数组、链表，就是典型的线性结构，栈啊队列啊，也都是。
  非线性结构，就是相对线性结构而言，排除法，现实中，所有不符合线性结构特点的，都可以拿来拟化。如果说线性结构是相对简单的、独立的，非线性结构就是它的的复杂化、关系化，是一种延伸。一段铁轨，线性，铁路组网，就是非线性；蜘蛛拉丝，线性的吧，编织成网，就是非线性。
  所以非线性结构的一个典型特征，就是其节点可以和多个节点有连接关系。
  我们经常说的，树、图，都是非线性的。

  避免误人子弟，一定要说一下，不少教材，都会明确指出：数组和链表（广义表）是非线性结构。这个在学生考试的时候千万别被我坑了，一定要按照书上的来，考试的时候，他说啥就是啥！
  这个是为什么呢，因为，这是一个太过于严谨和刻板的学术定义：一维数组是可以勉强算线性结构，但也有二维数组啊，还有三维四维多维啊，数组元素也可以是各种东西啊…链表（广义表）也差不多类似原因，所以数组和链表（广义表）是非线性结构。
  这里来个插曲，小扯一下，这种问题差不多是研究学问研究的有点那啥，更容易给新手学习上带来混乱，这是整体抽象和具体细节的胡搅蛮缠：绳子怎么能拟化成线性概念呢？拿放大镜看，绳子是有很多股更小的纤维缠绕编织而成，复杂的厉害呢，怎么可能是线性的；拿电子显微镜再看，更不得了，这都是各种奇形怪状的碳氢氧氮组成的有机分子，各种钩拉缠绕在相互作用….这不可能是线性概念能说的——所以，绳子是非线性的！
  有时候一些概念定义是尝试帮助我们学习的工具，是帮助工具，不是真理，也没什么对错，要知道所以然所以不然，懂了就真懂了，学问勿成学究，它爱是啥是啥，当然，考试还是要走大纲。

  好了，聒噪至此，浪费大家时间，略表歉意，稍息片刻，接下来我们就简单的过一下，常见的八种数据结构。