​​​​

1.什么是数据结构？

当我们遇到一个实际问题时，首先需要解决两件事：

（1）如何将数据存储在计算机中；
（2）用什么方法和策略解决问题。

前者是数据结构，后者是算法。只有数据结构没有算法，相当于只把数据存储在计算机中，而没有有效的方法去处理，就像一栋只有框架的烂尾楼；若只有算法没有数据结构，就像沙漠里面的海市蜃楼，只不过是空中楼阁罢了。

在我们开始学习数据结构和算法之前，我们先从总体上来了解一下什么是数据结构和算法。顾名思义，数据是一切输入计算机中信息的总和，结构是指数据之间的关系。数据结构就是将数据及其之间的关系有效的存储在计算机中并进行基本操作。而算法就是对特定问题求解步骤的一种描述，通俗的讲就是解决问题的方法和策略。在遇到实际问题时，要充分利用自己所学的数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效地实现。这就是Niklaus Wirth教授所说的：

程序=数据结构+算法

呃呃呃，感觉好深奥......但是，我们学习编程，想成为编程大神，那么我们就一定要精通数据结构跟算法。我们先来举一个生活中的例子:如果给你一堆书你会怎么放？这还不简单，想怎么放就怎么放。如果书不多，我们一般是一本挨着一本的放着。那么要是书的规模很大呢？如学校图书馆里面的书如果是按上述一本一本的放，那么以后需要找书的时候是不是累死人了。如下图：

所以如何摆书我们需要首先考虑是书的规模。如果书很少，我们直接摆就行了，如果书很多，我们又该怎么办呢？同学们可以说说嘛？这就好比我们做题目的时候，如果数据不是很大，我们暴力枚举就可以了，如果数据太大的话，你可能就要寻找别的方法了。

学习数据结构，我们需要从几个概念入手。首先什么是数据？

数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合，包括文本、声音、图像等等。在我们的例子里面，所谓的数据就是图书馆中所有的书。

数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。在我们的例子里面，数据元素指的就是书。

数据项：一个数据元素可以由若干个数据项组成。在我们的例子里面，数据项其实就是书名、作者、出版社等等。

数据对象：是性质相同的数据元素的集合，是数据的子集。在我们的例子里面，其实就是某一类书，例如《信息学奥赛一本通》和《信息学奥赛课课通》就是同一类书籍。

了解了什么是数据之后，那结构又是什么呢？所谓的结构，简单的理解就是指关系。严格的说，结构是指各个组成部分互相搭配和排列的方式。在现实生活中，不同数据元素之间不是独立的，而是存在特定关系的，我们把这种关系称为结构。那数据结构是什么呢？

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

为编写出一个“完美”的程序，必须认真分析待处理对象的特性及各处理对象之间存在的关系。这也就是研究数据结构的意义。根据不同的角度，我们把数据结构分为逻辑结构和物理结构。

逻辑结构：是指数据对象中数据元素之间的相互关系。包括集合结构、线性结构、树形结构、图形结构。

集合结构∶集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是"平等"的，它们的共同属性是"同属于一个集合"。数据结构中的集合关系就类似于数学中的集合。

线性结构：线性结构中的数据之间是**一对一**的关系。

树形结构：树形结构中的数据之间存在一种**一对多**的层次关系。

图形结构：图形结构的数据元素是**多对多**的关系。

逻辑结构是针对具体问题的，是为了解决某个问题的，在遇到具体问题时，我们需要选择合适的数据结构来表示数据元素之间的逻辑关系。说完了逻辑结构，我们再来看看数据的物理结构。

物理结构：是指数据的逻辑结构在计算机中的存储形式。数据元素的存储形式主要有两种，分别是**顺序存储**和**链式存储**。

顺序存储：是把数据元素存放在地址连续的存储单元里。这种数据结构很简单，数组就是最典型的顺序存储结构。顺序存储就好像大家按顺序排好队，每个人占用一小段空间，谁也不会插队。但是实际生活中总会有人想插队，也有人因为上厕所放弃排队，显然，对这种时常要变化的结构，顺序存储就显得不是很科学了。你能说说这是为什么吗？

在现在的银行、医院、饭店等地方，都设置了排队系统，也就是每个人去了，先领一个号，等着叫号。在等待的时候，你爱去哪里就去哪里，只要及时回来就行。你关注的是前一个号有没有被叫到，叫到了，下一个就是你了。链式存储就很类似于这种形式。那么，什么是链式存储呢？

链式存储：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。那么如何才能实现链式存储呢？不知道你们有没有什么思路呢？

链式存储就像一个铁链子，一环扣一环才能连在一起。要想这条铁链子一环环的连在一起，不仅需要知道这个铁环是多少，还需要知道下一个铁环的位置是多少。因此在链式存储中每个节点除了要存储一个数据域之外还需要一个指针域来存储元素的地址（这里的指针域我们可以利用数组实现）。

说点题外话，大家知道读书的三种境界分别是什么吗？清代有位著名的学者王国维就提出了他的读书理论。王国维在《人间词话》说：“古今之成大事业、大学问者，必经过三种之境界：‘昨夜西风凋碧树，独上高楼，望尽天涯路’。此第一境也。‘衣带渐宽终不悔，为伊消得人憔悴。’此第二境也。‘众里寻他千百度，蓦然回首，那人却在灯火阑珊处’。此第三境也。”不知道同学们是如何理解这三种境界的，也不知道同学们现在又处于哪种境界。读书有三种境界，学习数据结构也有三种境界：

（1）会数据结构的基本操作。学会各种数据结构的基本操作，即取值、查找、插入、删除等。
（2）会利用数据结构解决实际问题。在掌握了书中的基本操作之后，就可以尝试利用数据结构解决一些实际问题了。
（3）熟练使用和改进数据结构，优化算法。这就是最高境界了，也是学习数据结构的精髓所在，单独学习数据结构是无法达到这种境界的。数据结构与算法相辅相成，需要在学习算法的过程中慢慢修炼。

2.什么是算法？

说了这么多关于数据结构的知识，那么什么又是算法呢？

还是图书馆的例子，如果一本一本找累死人，要是有个目录，先找哪一类，这样会快很多。如何查找其实就是算法。算法是解决问题步骤的有限集合，通常用某一种计算机语言进行伪码描述。通常用时间复杂度和空间复杂度来衡量算法的优劣。

我们来举一个简单的例子，写一个代码求1+2+3+...+10000的和是多少？大多数同学都会写出下面的代码：

int main()
{
    int i,s=0;
    for(i=1;i<=10000;i++)
    {
        s=s+i;
    }
    cout<<s;
}

//然而高斯同学是这么写的：

int main()
{
    int s=0,n=10000;
    cout<<(1+n)*n/2;
}

Copy

天才就是天才，电脑循环了10000次，高斯就用了一次。之前有同学问我，有没有什么通用的算法可以解决任何一个问题？这个问题其实问的很没有水平，就像你问医生有没有什么药可以包治百病一样。

现实世界中的问题千奇百怪，算法当然也就千变万化，没有通用的算法可以解决所有的问题。对于一个具体的问题，可能有很多很多种不同的算法，如何选择最优的算法也就是我们学习算法的意义所在。在学习算法之前，我们先了解下算法的五大特征。

算法具有五大特征：输入、输出、有穷性、确定性、可行性。

输入和输出：输入和输出特性比较容易理解，算法具有零个或多个输入。尽管对于绝大多数算法来说，输入参数都是必要的，但对于个别情况，如打印"hello world!"这样的代码，不需要任何输入参数，因此算法的输入可以是零个。算法至少有一个或多个输出，算法是一定需要输出的，不需要输出，你用这个算法干吗?

有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码，这就是不满足有穷性。当然这里有穷的概念并不是纯数学意义的，而是在实际应用当中合理的、可以接受的"有边界"。你说你写一个算法，计算机需要算上个二十年，一定会结束，它在数学意义上是有穷了，但它其实是没有意义的。

确定性：算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。

可行性：每一步都是可行的，每一步都能够通过执行有限次数的操作去完成。

刚才我们谈到了，算法不是唯一的。也就是说，同一个问题，可以有多种解决问题的算法。这可能让那些常年只做有标准答案题目的同学失望了，他们多么希望存在标准答案，只有一个是正确的，把它背下来，需要的时候套用就可以了。不过话说回来，尽管算法不唯一，相对好的算法还是存在的。掌握好的算法，对我们解决问题很有帮助，否则前人的智慧我们不能利用，就都得自己从头研究了。那么什么才叫好的算法呢?

一个好的算法一定具有这5个特性：正确性、可读性、健壮性、时间效率高和存储低。

正确性∶算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。但是算法的"正确"通常在用法上有很大的差别，大体分为以下四个层次。

1. 算法程序没有语法错误。
2. 算法程序对于合法的输入数据能够产生满足要求的输出结果。
3. 算法程序对于非法的输入数据能够得出满足规格说明的结果。
4. 算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果。

对于这四层含义，层次 1 要求最低，但是仅仅没有语法错误实在谈不上是好算法。这就如同仅仅解决温饱，不能算是生活幸福一样。而层次 4 是最困难的，我们学习编程就是一直在追求层次4这个境界。

可读性∶算法设计的另一目的是为了便于阅读、理解和交流。可读性高有助于人们理解算法，晦涩难懂的算法往往隐含错误，不易被发现，并且难于调试和修改。我们写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读，让人理解和交流，自己将来也可能阅读，如果可读性不好，时间长了自己都不知道写了些什么。

健壮性∶当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。

最后，好的算法还应该具备**时间效率高和存储量低的特点**。时间效率指的是算法的执行时间，对于同一个问题，如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。

存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时所占用的内存或外部硬盘存储空间。设计算法应该尽量满足时间效率高和存储量低的需求。在生活中，人们都希望花最少的钱，用最短的时间，办最大的事，算法也是一样的思想，最好用最少的存储空间，花最少的时间，办成同样的事就是好的算法。那么什么样的算法才是好的算法呢？

虽然计算机能快速的完成运算处理，但实际上，它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序，我们就需要考虑到算法的效率。
算法的效率主要由时间复杂度和空间复杂度这两个复杂度来评估：

时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。

空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

设计算法时，一般是要先考虑系统环境，然后权衡时间复杂度和空间复杂度，选取一个平衡点。不过，时间复杂度要比空间复杂度更容易产生问题，因此算法研究的主要也是时间复杂度，不特别说明的情况下，复杂度就是指时间复杂度。那什么是时间复杂度呢？

时间复杂度：一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。前面提到的时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此我们引入时间复杂度的概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，它称为算法的渐进时间复杂度，简称时间复杂度。**（该段描述了解即可）。**

大O表示法：像前面用O( )来体现算法时间复杂度的记法，我们称之为大O表示法。算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度。大O表示法O(f(n))中的f(n)的值可以为1、n、logn、n²等，因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶，那么如何推导出f(n)的值呢？我们接着来看推导大O阶的方法。

推导大O阶，我们可以按照如下的规则来进行推导，得到的结果就是大O表示法：
1.用常数1来取代运行时间中所有加法常数。
2.修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常数阶：先举了例子，如下所示。

int sum=0, n=100;   //执行一次
sum=(1+n)*n/2;     //执行一次
cout<<sum;       //执行一次

Copy

上面算法的运行的次数的函数为f(n)=3，根据推导大O阶的规则1，我们需要将常数3改为1，则这个算法的时间复杂度为O(1)。如果sum=(1+n)*n/2;这条语句再执行10遍，因为这与问题大小n的值并没有关系，所以这个算法的时间复杂度仍旧是O(1)，我们可以称之为常数阶。

线性阶：线性阶主要要分析循环结构的运行情况，如下所示。

for(int i=1;i<=n;i++){

//时间复杂度为O(1)的算法...

}

Copy

上面算法循环体中的代码执行了n次，因此时间复杂度为O(n)。

对数阶：接着看如下代码：

int number=1,n;
cin>>n;
while(number<n){
    number=number*2;
    //时间复杂度为O(1)的算法...
}

Copy

可以看出上面的代码，随着number每次乘以2后，都会越来越接近n，当number不小于n时就会退出循环。假设循环的次数为X，则由2^x=n得出x=log₂n，因此得出这个算法的时间复杂度为O(logn)。

平方阶：下面的代码是循环嵌套：

for(int i=1;i<=n;i++){  
    for(int j=1;j<=n;j++){
        //复杂度为O(1)的算法
        //...
   }
}

Copy

内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，现在经过外层循环n次，那么这段算法的时间复杂度则为O(n²)。
接下来我们来算一下下面算法的时间复杂度：

 for(int i=1;i<=n;i++){  
   for(int j=i;j<n;i++){
        //复杂度为O(1)的算法
        //... 
   }
}

Copy

需要注意的是内循环中int j=i，而不是int j=0。当i=1时，内循环执行了n次；i=2时内循环执行了n-1次，当i=n时执行了1次，我们可以推算出总的执行次数为：

n+(n-1)+(n-2)+(n-3)+……+1n+(n−1)+(n−2)+(n−3)+……+1
=(n+1)n/2=(n+1)n/2
=n²/2+n/2=n²/2+n/2

根据此前讲过的推导大O阶的规则的第二条：只保留最高阶，因此保留n²/2。根据第三条去掉和这个项的常数，则去掉1/2,最终这段代码的时间复杂度为O(n²)。

其他常见复杂度：除了常数阶、线性阶、平方阶、对数阶，还有如下时间复杂度：
f(n)=nlognf(n)=nlogn时，时间复杂度为O(nlogn)O(nlogn)，可以称为nlognnlogn阶。
f(n)=n^3f(n)=n3时，时间复杂度为O(n^3)O(n3)，可以称为立方阶。
f(n)=2^nf(n)=2n时，时间复杂度为O(2^n)O(2n)，可以称为指数阶。
f(n)=n!f(n)=n!时，时间复杂度为O(n!)O(n!)，可以称为阶乘阶。
f(n)=√nf(n)=√n时，时间复杂度为O(√n)O(√n)，可以称为平方根阶。

复杂度的比较：下面将算法中常见的f(n)值根据几种典型的数量级来列成一张表，根据这种表，我们来看看各种算法复杂度的差异。

从上表可以看出，O(n)、O(logn)、O(√n )、O(nlogn )随着n的增加，复杂度提升不大，因此这些复杂度属于效率高的算法，反观O(2ⁿ)和O(n!)当n增加到50时，复杂度就突破十位数了，这种效率极差的复杂度最好不要出现在程序中，因此在动手编程时要评估所写算法的最坏情况的复杂度。

下边给出一个更加直观的图：其中x轴代表n值，y轴代表T(n)值（时间复杂度）。T(n)值随着n的值的变化而变化，其中可以看出O(n!)和O(2ⁿ)随着n值的增大，它们的T(n)值上升幅度非常大，而O(logn)、O(n)、O(nlogn)随着n值的增大，T(n)值上升幅度则很小。

常用的时间复杂度按照耗费的时间从小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)