[数据结构与算法]考研数据结构与算法（一）绪论

一、数据结构概念

引用《数据结构-严蔚敏》的解释： 数据结构是相互之间存在一种或者多种特定关系的数据元素的集合

我们再来看维基百科的解释： 数据结构（英语：data structure）是计算机中存储、组织数据的方式。

其实数据结构可以简单的理解为字面意思， 数据的结构 ，比如说一本书的数据有着：价格、页码、出版社、书名……等等信息，对于这些信息而言我们把它们放在一起 构成一个整体的结构 ，这就是对于这本书而言的数据结构，实际上就是把一个事务的特征信息抽象出来用数据描述。

PS：数据结构一般和算法联系起来，数据结构是为了解决特定情况下的问题而设计的 存储数据的方式 ，而 操作该数据结构 的方法就是算法

1. 1 数据的逻辑结构

• 集合：结构中的数据元素只有同属一个集合的关系
• 线性结构：结构中的元素存在 一对一 的关系
• 树形结构：结构中的元素之间存在 一对多 的关系
• 图状结构或网状结构：结构中那个元素存在 多对多 关系

1.2 数据的存储结构

• 顺序存储 ： 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中 ，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间，缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
• 链式存储 ： 不要求逻辑上相邻的元素在物理位置上也相邻 ，借助指示元素存储地址的指针来表示元素之间的逻辑关系 。其优点是不会出现碎片现象，能充分利用所有存储单元缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
• 索引存储 ： 在存储元素信息的同时，还建立附加的索引表 。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。其优点是检索速度快：缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
• 散列存储 ： 根据元素的关键字直接计算出该元素的存储地址 ，又称哈希（ Hash ）存储其优点是检索、增加和删除结点的操作都很快，缺点是若散列函数不好， 可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

二、基本术语

2.1 数据

数据是信息的 载体 ，是描述客观事物属性的 所有能输入到计算机中并被计算机程序识别和处理 的符号的集合，如数字、字符等

2.2 数据元素

数据元素是数据的 基本单位 ，一个数据元素可以由若干个 数据项 组成，数据项是构成数据元素的最小不可分割的单位，举例，如上面所说的一本书就是一个数据元素，而书的价格、页码、出版社、书名……等信息就是数据项

2.3 数据对象

数据对象是 性质相同 的数据元素的集合，是数据的一个子集，例如对于正整数数据的对象是集合 $N=0,1,2,\dots \dots$

2.4 数据类型

• 原子数据类型：其值不可再分的数据类型
• 结构数据类型：其值可以再分解为若干成分（分量）的数据类型。
• 抽象数据类型：抽象数据组织及与之相关操作

三、抽象数据类型ADT

先来看看维基百科上面的解释： 抽象数据类型（Abstract Data Type，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的操作以及这些操作的效果的数学约束（与可能的代价）。

其实所谓的抽象就是抽出事务普遍的本质，而抽象数据类型其实就是 封装一个事务 ，将这个事务的数据抽象成数学模型（用数字，或字符等表示），然后加上数据元素之间的关系（比如重载对元素排序），以及对数据的操作（函数），我们举一个简单的例子， 队列 这个抽象数据类型，我们的原子数据类型可能是整形、也可能是一个抽象数据结构，那么元素之间的关系就是集合关系，数据的操作基础的就有 pop() 、 push 两个操作，那么这个所谓的抽象数据类型其实就是将事务的数据、关系、行为封装在一起，这其实也是面向对象的一种思想。

四、算法和算法分析

4.1 算法

上面也谈到过，操作数据结构的方法就是算法，但是算法不只是操作数据结构的方法，只要是对特定的问题的求解有一定步骤那都能称为算法，算法也有五个比较重要的特征：

• 有穷性：算法的执行时间一定是有限时间内
• 确定性：算法中的每一条指令都有明确的含义，不能产生歧义
• 可行性：算法的操作都是基于一些以及实现的作为基础的
• 输入：输入的数据取决于特定的对象的集合
• 输出：输出的数据取决于我们想要得到的数据

4.2 好算法的标准

• 正确性：好的算法不能仅仅通过部分测试数据，而是要在指定范围内所有数据都能通过，一般来说只需要通过一些边界数据就不会有什么问题给
• 可读性：算法应当利于人的阅读和交流
• 健壮性：当输入数据非法的时候也应当做出相应的操作
• 效率：效率一般指时间效率，我们自然希望算法的时间效率能更高，但是在一定情况下，我们也希望空间效率也能更好，所以一个好的算法应当适应其应用的时间空间场景

4.3 时间复杂度

先来看维基百科的解释：

在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 $n$ （必须比 $n_0$ 大）的输入，它至多需要 $5n^3+3n$ 的时间运行完毕，那么它的 渐近时间复杂度 是 $O(n^3)$。

一个语句的频度是指该语句在算法中被重复执行的次数 。算法中所有语旬的频度之和记为 $T(n)$ 时，它是该算法问题规模 $n$ 的函数，时间复杂度主要分析 $T(n)$ 的数量级。算法中基本运算（最深层循环内的语句）的频度与 $T(n)$ 同数量级，因此通常采用算法中基本运算的频度 $f(n)$ 来分析算法 的时间 复杂度②。 因此，算法的时间复杂度记为
$$T(n)=O(f(n))$$
其中O的含义就是 $T(n)$ 的数量级

这里列举一下常见的渐进时间复杂度：
$$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<0(2^n)<O(n!)<O(n^n)$$

其实我们平时所讲的时间复杂度是一个 平均时间复杂度 或者说是 渐进时间复杂度 ，假设数据规模为 $n$ ，那么我们每做一次相近数据规模的操作，复杂度的指数就会增加 $1$ ，例如我们对一个长度为 $n$ 的数组做一个循环，那么这个渐进时间复杂度就是 $O(n)$ ，如果说我们循环的是一个 $n\times n$ 的二维矩阵，那么复杂度就为 $O(n^2)$ 假设说我们的二维数组的每一行的数据都是有序的，我们需要从中找到指定的元素的位置，这时我们使用二分查找加速每一行的查找，那么我们发现复杂度就变成了 $O(nlo{g}_{2}n)$

关于少算的那一部分次数，我们将其称为 常数 ，有的时候常数也是能影响一个算法的

更加复杂的时间复杂度分析，例如分析递归函数的时间复杂度可以去参考 势能分析法

4.4 空间复杂度

与时间复杂度相对应的就是空间复杂度了，都说算法就是 “时间换空间，空间换时间” ，在一般的算法题目中其实对空间的限制并不明显，但是同样需要学习分析，在一些老的OJ，例如HDU、POJ就会有炸空间的可能，假设问题的规模同样是 $n$ ，则算法的空间复杂度记为$S(n)=O(g(n))$

其实和时间复杂度类似，只不过从计数的方式从 操作次数 变为了整个算法的 最大内存空间的占用时刻 ，这些空间可能由输入数据、输出数据、中间数据占用。