一、数据结构

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

1.1 数据结构分类

数据结构可按照逻辑结构和存储结构划分

1.1.1 逻辑结构

系统的逻辑结构是从思想的角度上对系统分类，把系统分成若干个逻辑单元，不同逻辑单元分别实现自己的功能。数据的逻辑结构是对数据之间关系的描述，如顺序关系,隶属关系等，有时就把逻辑结构简称为数据结构，数据的逻辑结构分为以下四种：

1. 集合结构：集合结构的集合中任何两个数据元素之间都没有逻辑关系，组织形式松散。
2. 线性结构：数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。
3. 树状结构：树状结构是一个或多个节点的有限集合。
4. 网络结构：网络结构是指通信系统的整体设计，它为网络硬件、软件、协议、存取控制和拓扑提供标准。

数据结构可分为线性结构和非线性结构：

• 线性结构：线性结构又可以继续细分为：顺序表、链表、栈和队列、串、数组和广义表。
• 非线性结构：非线性结构可以分为集合、树(二叉树)、图。

1.1.2 存储结构

存储结构是指一个数据集合在计算机内存里是怎么样存储的，或者说在内存里怎么给一群数据分配内存。

数据的存储结构是指数据的逻辑结构在计算机中的表示。数据的存储结构分为顺序存储结构和链接存储结构两种。

1. 顺序存储结构：顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。
2. 链接存储结构：链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。

从存储结构可分为顺序存储和非顺序存储(或链式存储)：

• 顺序存储：顺序存储的内存地址一定是连续的；存储密度大；比链式节约空间；支持随机存取，方便操作；适用于频繁查询时使用。
• 链式存储：内存地址不一定连续；因为链式结构每一个节点都有一个指针存储域，比较占空间；在插入和删除上比顺序方便；适用于频繁插入、删除、更新元素时使用。

1.2 常用的数据结构(重要)

二、算法

在中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。

2.1 算法的五个特征

1. 有穷性：对于任意一组合法输入值，在执行又穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。
2. 确定性：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。
3. 可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。
4. 有输入：作为算法加工对象的量值，通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。
5. 有输出：它是一组与“输入”有确定关系的量值数据结构及算法基础 java，是算法进行信息加工后得到的结果，这种确定关系即为算法功能。

2.2 算法的设计原则

1. 正确性：首先，算法应当满足以特定的“规则说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：

   一、程序语法错误。
   二、程序对于几组输入数据能够得出满足需要的结果。
   三、程序对于精心选择的、典型、苛刻切带有*难性的几组输入数据能够得出满足要求的结果。
   四、程序对于一切合法的输入数据都能得到满足要求的结果。

   PS：通常以第三层意义的正确性作为衡量一个算法是否合格的标准。

2. 可读性：算法为了人的阅读与交流，其次才是计算机执行。因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。
3. 健壮性：当输入的数据非法时，算法应当恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序执行，而是应当返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
4. 高效率与低存储量需求：通常算法效率值得是算法执行时间；存储量是指算法执行过程中所需要的最大存储空间，两者都与问题的规模有关。

前面三点正确性，可读性和健壮性相信都好理解。对于第四点算法的执行效率和存储量，我们知道比较算法的时候，可能会说“算法比算法快两倍”之类的话，但实际上这种说法没有任何意义。

因为当数据项个数发生变化时，算法和算法的效率比例也会发生变化，比如数据项增加了，可能算法比算法快三倍，但是如果数据项减少了，可能算法和算法速度一样。

所以描述算法的速度必须要和数据项的个数联系起来。也就是“大”表示法，它是一种算法复杂度的相对表示方式，这里我简单介绍一下，后面会根据具体的算法来描述。

• 相对()：你只能比较相同的事物。你不能把一个做算数乘法的算法和排序整数列表的算法进行比较。但是，比较个算法所做的算术操作(一个做乘法，一个做加法)将会告诉你一些有意义的东西；
• 表示()：大O(用它最简单的形式)把算法间的比较简化为了一个单一变量。这个变量的选择基于观察或假设。例如，排序算法之间的对比通常是基于比较操作(比较2个结点来决定这2个结点的相对顺序)。这里面就假设了比较操作的计算开销很大。但是，如果比较操作的计算开销不大，而交换操作的计算开销很大，又会怎么样呢？这就改变了先前的比较方式；
• 复杂度()：如果排序个元素花费了我1秒，那么排序1百万个元素会花多少时间？在这个例子里，复杂度就是相对其他东西的度量结果。

然后我们在说说算法的存储量，包括：

• 程序本身所占空间；
• 输入数据所占空间；
• 辅助变量所占空间；

一个算法的效率越高越好，而存储量是越低越好。

2.3 算法复杂度

如何去衡量不同算法之间的优劣呢？主要还是从算法所占用的时间和空间两个维度去考量。

• 时间维度：是指执行当前算法所消耗的时间，通常用时间复杂度来描述。
• 空间维度：是指执行当前算法需要占用多少内存空间，通常用空间复杂度来描述。

因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而有时候时间和空间却又是不可兼得的，那么我们就需要从中去取一个平衡点。

2.3.1 时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度。记作：T(n)=O(f(n))。它表示随问题n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中，f(n)是问题规模n的某个函数。

这样用大写O()来体现算法时间复杂度的记法，我们称之为大0记法。

这段代码的时间复杂度为：O(n)，为什么呢?在大O符号表示法中，时间复杂度的公式是：(T(n) = O(f(n)))，其中f(n)表示每行代码执行次数之和，而O表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

我们继续看上面的例子，假设每行代码的执行时间都是一样的，我们用1颗粒时间来表示，那么这个例子的第一行耗时是1个颗粒时间，第三行的执行时间是n个颗粒时间，第四行的执行时间也是n个颗粒时间(第二行和第五行是符号，暂时忽略)，那么总时间就是1颗粒时间 + n颗粒时间 + n颗粒时间，即(1+2n)个颗粒时间，即：(T(n) = (1+2n) * 颗粒时间)，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：(T(n) = O(n))。

常见的时间复杂度量级有：

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

下面选取一些较为常用的来讲解一下(没有严格按照顺序)：

1. 常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

讯享网

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

2. 线性阶O(n)

这个在最开始的代码示例中就讲解过了，如：

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

3. 对数阶O(logN)

还是先来看代码：

讯享网

从上面代码可以看到，在while循环里面，每次都将i乘以2，乘完之后，i距离n就越来越近了。我们试着求解一下，假设循环x次之后，i就大于2了，此时这个循环就退出了，也就是说2的x次方等于n，那么x = log2^{n。也就是说当循环log2}n次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)。

4. 线性对数阶O(nlogN)

线性对数阶O(nlogN)其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

5. 平方阶O(n²)

平方阶O(n²)就更容易理解了，如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n²)了。

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是O(n*n)，即O(n²)。如果将其中一层循环的n改成m，即：

那它的时间复杂度就变成了O(m*n)

6. 立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²)去理解就好了，O(n³)相当于三层n循环，其它的类似。

除此之外，其实还有平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度的分析方法，有点复杂，这里就不展开了。

2.3.2 空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用S(n)来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

1. 空间复杂度O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为O(1)

代码中的i、j、m所分配的空间都不随着处理数据量变化，因此它的空间复杂度(S(n) = O(1))

2. 空间复杂度O(n)

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即(S(n) = O(n))

2.4 常用排序算法(重要)

三、数据类型

3.1 数据类型(DT)

数据类型()是一个值的集合和定义在这个值集上的一组操作的总称。

• 原子类型：如语言的整形、字符型等标准类型及指针等简单的导出类型和空类型。
• 结构类型：其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的，通常是由标准类型派生的。例如，C/C++中的数组、结构等类型。

在中我们可能首先会想到像这样的词，这是中的基本数据类型，一个数据类型会涉及到两件事：

1. 拥有特定特征的数据项
2. 在数据上允许的操作

比如中的数据类型，它表示整数，取值范围为：，还能使用各种操作符，+、-、*、/等对其操作。数据类型允许的操作是它本身不可分离的部分，理解类型包括理解什么样的操作可以应用在该类型上。

那么当年设计计算机语言的人，为什么会考虑到数据类型？

我们先看这样一个例子，比如，大家都需要住房子，也都希望房子越大越好。但显然，没有钱，考虑房子没有意义。于是就出现了各种各样的商品房，有别墅的、复式的、错层的、单间的……甚至只有两平米的胶囊房间。这样做的意义是满足不同人的需要。

同样，在计算机中，也存在相同的问题。计算这样的表达式不需要开辟很大的存储空间，不需要适合小数甚至字符运算的内存空间。于是计算机的研究者们就考虑，要对数据进行分类，分出来多种数据类型。比如，比如。

虽然不同的计算机有不同的硬件系统，但实际上高级语言编写者才不管程序运行在什么计算机上，他们的目的就是为了实现整形数字的运算，比如等。他们才不关心整数在计算机内部是如何表示的，也不管是如何计算的。于是我们就考虑，无论什么计算机、什么语言都会面临类似的整数运算，我们可以考虑将其抽象出来。抽象是抽取出事物具有的普遍性本质，是对事物的一个概括，是一种思考问题的方式。

3.2 抽象数据类型(ADT)

抽象数据类型()是指一个数学模型及定义在该模型上的一组操作。它仅取决于其逻辑特征，而与计算机内部如何表示和实现无关。

比如刚才说的整型，各个计算机，不管大型机、小型机、、平板电脑甚至智能手机，都有“整型”类型，也需要整形运算，那么整型其实就是一个抽象数据类型。

更广泛一点的，比如我们刚讲解的栈和队列这两种数据结构，我们分别使用了数组和链表来实现，比如栈，对于使用者只需要知道和方法或其它方法的存在以及如何使用即可，使用者不需要知道我们是使用的数组或是链表来实现的。

的思想可以作为我们设计工具的理念，比如我们需要存储数据，那么就从考虑需要在数据上实现的操作开始，需要存取最后一个数据项吗？还是第一个？还是特定值的项？还是特定位置的项？回答这些问题会引出的定义，只有完整的定义了后，才应该考虑实现的细节。

这在我们语言中的接口设计理念是相通的。

四、算术表达式

4.1 人如何解析算术表达式

如何解析算术表达式？或者换种说法，遇到某个算术表达式，我们是如何计算的：

①、求值3+4-5

这个表达式，我们在看到后都不能直接计算的值，知道看到后面的号，因为减号的优先级和前面的加号一样，所以可以计算的值了，如果后面是或者，那么就要在乘除过后才能做加法操作，比如：

②、求值3+4*5

这个不能先求的值，因为后面的运算级别比前面的+高。通过这两个表达式的说明，我们可以总结解析表达式的时候遵循的几条规则：

1. 从左到右读取算式。
2. 已经读到了可以计算值的两个操作数和一个操作符时，可以计算，并用计算结果代替那两个操作数和一个操作符。
3. 继续这个过程，从左到右，能算就算，直到表达式的结尾。

4.2 计算机如何解析算术表达式

对于前面的表达式，我们人是有思维能力的，能根据操作符的位置，以及操作符的优先级别能算出该表达式的结果。但是计算机怎么算？

计算机必须要向前(从左到右)来读取操作数和操作符，等到读取足够的信息来执行一个运算时，找到两个操作数和一个操作符进行运算，有时候如果后面是更高级别的操作符或者括号时，就必须推迟运算，必须要解析到后面级别高的运算，然后回头来执行前面的运算。我们发现这个过程是极其繁琐的，而计算机是一个机器，只认识高低电平，想要完成一个简单表达式的计算，我们可能要设计出很复杂的逻辑电路来控制计算过程，那更不用说很复杂的算术表达式，所以这样来解析算术表达式是不合理的，那么我们应该采取什么办法呢？

请大家先看看什么是前缀表达式，中缀表达式，后缀表达式：这三种表达式其实就是算术表达式的三种写法，以为例

①、前缀表达式：操作符在操作数的前面，比如
②、中缀表达式：操作符在操作数的中间，这也是人类最容易识别的算术表达式
③、后缀表达式：操作符在操作数的后面，比如

上面我们讲的人是如何解析算术表达式的，也就是解析中缀表达式，这是人最容易识别的，但是计算机不容易识别，计算机容易识别的是前缀表达式和后缀表达式，将中缀表达式转换为前缀表达式或者后缀表达式之后，计算机能很快计算出表达式的值，那么中缀表达式是如何转换为前缀表达式和后缀表达式，以及计算机是如何解析前缀表达式和后缀表达式来得到结果的呢？

4.3 后缀表达式

后缀表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则)。

由于后缀表达式的运算符在两个操作数的后面，那么计算机在解析后缀表达式的时候，只需要从左向右扫描，也就是只需要向前扫描，而不用回头扫描，遇到运算符就将运算符放在前面两个操作符的中间(这里先不考虑乘方类似的单目运算)，一直运算到最右边的运算符，那么就得出运算结果了。既然后缀表达式这么好，那么问题来了：

4.3.1 如何将中缀表达式转换为后缀表达式？

对于这个问题，转换的规则如下：

一、先自定义一个栈

二、前缀表达式转换为后缀表达式

三、测试

四、结果

五、分析

4.3.2 计算机如何实现后缀表达式的运算？

4.4 前缀表达式

前缀表达式，指的是不包含括号，运算符放在两个运算对象的前面，严格从右向左进行(不再考虑运算符的优先规则)，所有的计算按运算符出现的顺序。

注意：后缀表达式是从左向右解析，而前缀表达式是从右向左解析。

4.4.1 如何将中缀表达式转换为前缀表达式？

4.4.2 计算机如何实现前缀表达式的运算？