# 数据结构初探 数据的存储方式可分为线性表、树和图三种存储结构，而每种存储结构又可细分为顺序存储结构和链式存储结构。数据存储方式如此之多，针对不同类型的数据选择合适的存储方式是至关重要的。 那么，到底如何选择呢？数据存储结构的选择取决于两方面，即数据的逻辑结构和存储结构（又称物理结构）。 ## 逻辑结构 数据的逻辑结构，简单地理解，就是指的数据之间的逻辑关系。以上所说，父子、兄弟等这些关系都指的是数据间的逻辑关系，假设我们要存储这样一张家庭成员关系图，不仅要存储张平、张华等数据，还要存储它们之间的关系，两者缺一不可。 一组数据成功存储到计算机的衡量标准是要能将其完整的复原。例如图 1 所示的成员关系图，如果所存储的数据能将此成员关系图彻底复原，则说明数据存储成功。 数据之间的逻辑关系可细分为三类，“一对一”、“一对多”和“多对多”： - “一对一”：类似集合 `{1,2,3,...,n}` 这类的数据，每个数据的左侧有且仅有一个数据与其相邻（除 1 外）；同样，每个数据的右侧也只有一个数据与其相邻（除 n 外），所有的数据都是如此，就说数据之间是“一对一”的逻辑关系； - “一对多”：图 1 中的数据就属于“一对多”，因为对于张平来说，有且仅有一个父亲（张亮），但是有 2（多）个孩子； - “多对多”：拿图 2 来说，从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，对于V1、V2、V3和V4来说，它们之间就是“多对多”的关系； 通过学习数据结构，我们可以学到 3 种存储结构分别存储这 3 类逻辑关系的数据，换句话说： 1. 线性表用于存储具有“一对一”逻辑关系的数据； 2. 树结构用于存储具有“一对多”关系的数据； 3. 图结构用于存储具有“多对多”关系的数据； 由此，我们可以通过分析数据之间的逻辑关系来决定使用哪种存储结构，但具体使用顺序存储还是链式存储，还要通过数据的物理结构来决定。 ## 存储结构（物理结构） 数据的存储结构，也就是物理结构，指的是数据在物理存储空间上选择集中存放还是分散存放。假设要存储大小为 10G 的数据。 如果选择集中存储，就使用顺序存储结构；反之，就使用链式存储。至于如何选择，主要取决于存储设备的状态以及数据的用途。 我们知道，集中存储（底层实现使用的是数组）需要使用一大块连续的物理空间，假设要存储大小为 1G 的数据，若存储设备上没有整块大小超过 1G 的空间，就无法使用顺序存储，此时就要选择链式存储，因为链式存储是随机存储数据，占用的都是存储设备中比较小的存储空间，因此有一定几率可以存储成功。 并且，数据的用途不同，选择的存储结构也不同。将数据进行集中存储有利于后期对数据进行遍历操作，而分散存储更有利于后期增加或删除数据。因此，如果后期需要对数据进行大量的检索（遍历），就选择集中存储；反之，若后期需要对数据做进一步更新（增加或删除），则选择分散存储。 ## 时间复杂度和空间复杂度 在学习具体的数据结构和算法之前，每一位初学者都要掌握一个技能，即善于运用时间复杂度和空间复杂度来衡量一个算法的运行效率。 所谓算法，即解决问题的方法。同一个问题，使用不同的算法，虽然得到的结果相同，但耗费的时间和资源肯定有所差异。就比如拧一个螺母，扳手和钳子都可以胜任，但使用钳子拧螺母肯定没有扳手的效率高。 这也就意味着，如果解决问题的算法有多种，我们就需要从中选出最好的那一个。那么，怎么判断哪个算法更好（或者更优）呢？ ## “好”算法的标准 解决一个问题的方法可能有很多，但能称得上算法的，首先它必须能彻底解决这个问题（称为准确性），且根据其编写出的程序在任何情况下都不能崩溃（称为健壮性）。 > 注意，程序和算法是完全不同的概念。算法是解决某个问题的想法、思路；而程序是在根据算法编写出来的真正可以运行的代码。例如，要依次输出一维数组中的数据元素的值，首先想到的是使用循环结构，在这个算法的基础上，我们才开始编写程序。 在满足准确性和健壮性的基础上，还有一个重要的筛选条件，即通过算法所编写出的程序的运行效率。程序的运行效率具体可以从 2 个方面衡量，分别为： - 程序的运行时间。 - 程序运行所需内存空间的大小。 根据算法编写出的程序，运行时间更短，运行期间占用的内存更少，该算法的运行效率就更高，算法也就更好。 那么，如何衡量一个算法所编写出程序的运行效率呢？数据结构中，用时间复杂度来衡量程序运行时间的多少；用空间复杂度来衡量程序运行所需内存空间的大小。 ## 时间复杂度 判断一个算法所编程序运行时间的多少，并不是将程序编写出来，通过在计算机上运行所消耗的时间来度量。原因很简单，一方面，解决一个问题的算法可能有很多种，一一实现的工作量无疑是巨大的，得不偿失；另一方面，不同计算机的软、硬件环境不同，即便使用同一台计算机，不同时间段其系统环境也不相同，程序的运行时间很可能会受影响，严重时甚至会导致误判。 实际场景中，我们更喜欢用一个估值来表示算法所编程序的运行时间。所谓估值，即估计的、并不准确的值。注意，虽然估值无法准确的表示算法所编程序的运行时间，但它的得来并非凭空揣测，需要经过缜密的计算后才能得出。 也就是说，表示一个算法所编程序运行时间的多少，用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。 那么，如何预估一个算法所编程序的运行时间呢？很简单，先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间。 以一段简单的 C 语言程序为例，预估出此段程序的运行时间： ```c //n+1 for(int i=0; i 事实上，对于一个算法（或者一段程序）来说，其最简频度往往就是最深层次的循环结构中某一条语句的执行次数。例如 2n+1 最简为 n，实际上就是 a++ 语句的执行次数；同样 2n2+2n+1 简化为 n2，实际上就是最内层循环中 num++ 语句的执行次数。 得到最简频度的基础上，为了避免人们随意使用 a、b、c 等字符来表示运行时间，需要建立统一的规范。数据结构推出了大 O 记法（注意，是大写的字母 O，不是数字 0）来表示算法（程序）的运行时间。发展至今，此方法已为大多数人所采纳。 大 O 记法的表示方法也很简单，格式如下： O(频度) > 其中，这里的频度为最简之后所得的频度。 例如，用大 O 记法表示上面 2 段程序的运行时间，则上面第一段程序的时间复杂度为 O(n)，第二段程序的时间复杂度为 O(n2)。 如下列举了常用的几种时间复杂度，以及它们之间的大小关系： O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶) > 注意，这里仅介绍了以最坏情况下的频度作为时间复杂度，而在某些实际场景中，还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的平均时间复杂度。 ## 空间复杂度 和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示。 要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如： - 程序代码本身所占用的存储空间； - 程序中如果需要输入输出数据，也会占用一定的存储空间； - 程序在运行过程中，可能还需要临时申请更多的存储空间。 首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码。 程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。 事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。 举个例子： ``` int n;scanf("%d", &n);int a[10]; ``` 通过分析不难看出，这段程序在运行时所申请的临时空间，并不随 n 的值而变化。而如果将第 3 行代码改为： ``` int a[n]; ``` 此时，程序运行所申请的临时空间，和 n 值有直接的关联。 所以，如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系： - 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示; - 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示； - 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示； - 等等。 > 在多数场景中，一个好的算法往往更注重的是时间复杂度的比较，而空间复杂度只要在一个合理的范围内就可以。 ## 数据结构和算法的关系和区别 由于大量数据结构教程中都将数据结构的知识和算法掺杂起来讲，使很多初学者认为数据结构就是在讲算法，这样理解是不准确的。 数据结构和算法之间完全是两个相互独立的学科，如果非说它们有关系，那也只是互利共赢、“1+1>2”的关系。 最明显的例子，如果你认为数据结构是在讲算法，那么大学我们还学《算法导论》，后者几乎囊括了前者使用的全部算法，有什么必要同时开设这两门课程呢？ 我们还可以从分析问题的角度去理清数据结构和算法之间的关系。通常，每个问题的解决都经过以下两个步骤： 1. 分析问题，从问题中提取出有价值的数据，将其存储； 2. 对存储的数据进行处理，最终得出问题的答案； 数据结构负责解决第一个问题，即数据的存储问题。通过前面的学习我们知道，针对数据不同的逻辑结构和物理结构，可以选出最优的数据存储结构来存储数据。 而剩下的第二个问题，属于算法的职责范围。算法，从表面意思来理解，即解决问题的方法。我们知道，评价一个算法的好坏，取决于在解决相同问题的前提下，哪种算法的效率最高，而这里的效率指的就是处理数据、分析数据的能力。 因此我们得出这样的结论，数据结构用于解决数据存储问题，而算法是思考如何利用存储的数据快速无误地解决问题，它们是完全不同的两类学科。 也正因为如此，你可以认为数据结构和算法存在“互利共赢、1+1>2”的关系。在解决问题的过程中，数据结构要配合算法选择最优的存储结构来存储数据，而算法也要结合数据存储的特点，用最优的策略来分析并处理数据，由此可以最高效地解决问题。 ![顺序表存储数据示意图](http://c.biancheng.net/uploads/allimg/190426/1F2162264-0.gif) 图 1 顺序表存储数据示意图 例如，有这样一个问题，计算“1+2+3+4+5”的值。这个问题我们可以这样来分析： - 计算 1、2、3、4 和 5 的和，首先要选择一种数据存储方式将它们存储起来，通过前面的学习我们知道，数据之间具有“一对一”的逻辑关系，最适合用线性表来存储。结合算法的实现，我们选择顺序表来存储数据（而不是链表），如图 1 所示； - 接下来，我们选择算法。由于数据集中存放，因此我们可以设计这样一个算法，使用一个初始值为 0 的变量 num 依次同存储的数据做“加”运算，最后得到的新 num 值就是最终结果。 选择顺序表而不是链表的原因，是顺序表遍历数据比链表更高效。 ## 数据结构和算法如何学习 首先我认为，学习数据结构和算法有一个很重要的前提，就是至少熟练掌握一门编程语言。学习数据结构和算法，实践是非常重要的，如果仅仅是空有理论而不实践，反复学多少遍都没用。 本教程以 C 语言作为教学语言，当然读者也可以在掌握 C++、Java、Python 等语言的基础上学习数据结构和算法。因为无论是数据结构还是算法，它教会我们的是解决问题的思想，并不挂靠某一门具体的编程语言。换句话说，在掌握任何一门编程语言的基础上，都可以学习数据结构和算法。 其次对于初学者来说，好的学习资源是非常重要的。要知道，学习数据结构需要读者有一定的空间想象能力，所以强烈建议读者在看文字资料的同时，再找一套相应的视频资料，两者结合来学习，往往会事半功倍。 那么，有哪些不错的学习资源呢？我个人强烈推荐严蔚敏老师的《数据结构(C语言版)》以及她录制的一整套数据结构视频资料。如果读者刚刚接触数据结构和算法，可以跟随本教程学习，同时配以严蔚敏老师录制的视频资料。 > 本教程就是以严蔚敏老师的数据结构为原型进行编写的，和后者相比，本教程的语言通俗易懂，同时配有完整的 C 语言代码，非常适合初学者入门使用。 另外，市面上还有很多不错的学习资料，例如《大话数据结构》、《数据结构与算法分析》等，同时慕课（mooc）上也有很多讲解数据结构和算法的视频资料，这里不再一一举例。 除了熟练精通一门编程语言、有一套不错的学习资料之外，最重要的是找到一个好的学习方法。其实数据结构和算法并不难，之所以有读者认为它很难，是因为你的学习方法不对。 在这里，我把自己的学习方法推荐给大家，可以总结为 6 个字：多动笔、多动手。 所谓“多动笔”，在学习数据结构和算法的过程中，要边学习边画图。因为，对于数据结构中的存储结构来说，尤其是树结构和图结构，存储结构确实比较复杂，仅靠空间想象难免会有纰漏，而通过亲手画图往往能避免很多“坑”。 以学习链表（后续章节会做详细讲解）为例，如果我们想象不到它是怎样存储数据，就应该尝试动手将它画出来，如图 1 所示： ![画链表](http://c.biancheng.net/uploads/allimg/200709/1-200F9212502214.gif) 图 1 链表 由此，我们就画了一个存有 {1,2,3,4} 数据的链表。 不仅如此，假设在图 1 的基础上想删除存储元素 3 的结点，也可以先通过画图来实现： ![删除某个结点](http://c.biancheng.net/uploads/allimg/200709/1-200F92125295J.gif) 图 2 删除某个结点 如上图所示，整个画图的过程，也是我们思考如何通过程序实现删除指定节点的过程： 1. 为了删除存有元素 3 的结点，先要找到它的前驱结点，也就是结点 2，并用一个指针 p 来标记； 2. 借助指针 p，可以顺利找到结点 3，因为它最终要被摘除，考虑到该结点占用的空间要手动释放，因此还要用一个指针 q 来标记它； 3. 借助指针 p 和 q（也就是图中的第 3 步），就可以成功将目标结点摘下来； 4. 最后借助指针 q，可以释放被删除节点所占用的存储空间。 以上就是为了删除存储元素 3 的结点，整个画图的流程。 > 再次强调，画图的过程是思考如何用程序实现的过程，并不是随意勾画。 除此之外，在学习某些算法时，也可以借助画图来加深自己的理解。甚至在阅读它人实现的代码时，可以边阅读代码边画图，这样可以更快理清代码的实现逻辑。 在通过“多动手”实现理解存储结构和实现逻辑的基础上，初学者还要“多动手”编写实现代码。注意，对于某一种存储结构或者算法，没有 3 遍以上自己独立的实现过程，是很难做到融会贯通的。 另外，很多初学者都存在“当时搞清楚了，过段时间又忘了”的情况。其原因大致有 2 个，一个是当时学的时候就没有彻底搞懂，或者处于“似懂非懂”的状态；另一个原因就是长时间没有再接触过它，所以淡忘了。其中如果是第一种原因导致的，那只能从头再学；对于第二种情况，读者不需要过度懊恼，只要我们再回顾一遍，通常是可以快速回忆起来的。 总之，数据结构确实是一门比较难理解的学科，而且学习过程没有任何捷径可走。这意味着，想要学好数据结构，除了找一套适合自己的学习资料和学习方法外，更要有一种“死磕”的精神，有句话说的很好，“不逼自己一把，永远不知道自己有多大的潜力”。 ## 随便谈谈 前面已经详细的讲解了如何用“大 O 记法”来评判一个算法的时间复杂度，那么下面 C 语言代码的时间复杂度是多少呢？ ```c i = 1; while(i