§1 数据结构与算法概论

「我们远远低估了中国选手的数据结构水平。」——xiaolilsq

§1.1 数据结构概述

数据是信息的载体，能够被计算机识别、存储和加工处理，数据包括文字、表格、图像等。信息是数据的内涵，即数据所表达的意义。

数据项（字段、域、属性）：具有独立意义的不可分割的最小标识单位。
数据元素（节点、记录）：数据的 基本单位。一个数据元素可以由若干个数据项组成。
数据对象：具 有相同类型 的数据元素的集合。在数据结构中除特别指定外数据通常都是数据对象。

数据结构：数据 + 结构，相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系构成了某种结构。包括：

逻辑结构：
数据元素之间的逻辑关系（主要指数据元素之间的 相邻关系）的整体，是数据结构在用户面前呈现的形式。
表示：二元组 $S=(D,R)$ ， $D$ 是由有限个数据元素所构成的集合， $R$ 是 $D$ 上的关系（ $D \to D$ 的关系，记作 $r_{i}$ ）的有限集合，每个关系 $r_{i}$ 用 序偶集合 来表示，一个序偶表示两个元素的关系，用 尖括号 $\left<a,b\right>$ 表示有向关系（存在元素 $a$ 到 $b$ 的关系），用 圆括号 $(a,b)$ 表示无向关系（既存在元素 $a$ 到 $b$ 的关系，又存在元素 $b$ 到 $a$ 的关系）。
定义 后继元素、前驱元素，开始元素、终端元素、内部元素
分类：
- 集合（最松散的关系）；
- 线性结构（一对一的关系）；
- 树结构（非线性，一对多的关系）；
- 图结构（非线性，多对多的关系）。
存储结构：
数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构。同一种逻辑结构可以设计多种存储结构，在不同的存储结构中，实现同一种运算的算法可能不同。
分类：
- 顺序存储结构（采用一组连续的存储单元存放所有的数据元素，逻辑上相邻的元素的存储单元也相邻，具有 随机存取特性）；
- 链式存储结构（每个结点单独存储，占用一片连续的存储区域，所有结点无需占用一整块存储空间，为了表示结点之间的关系，给每个结点附加指针字段，用于存放相邻结点的存储地址）；
- 索引存储结构（数据表 + 索引表，索引表中的每一项称为 索引项（关键字，对应地址），其中 对应地址 为该关键字的记录在数据表中的存储地址，通过索引表按关键字 查找速度快）；
- 哈希（Hash, 散列）存储结构（通过哈希函数将键映射到表中一个位置来访问记录，不是薯饼 Hash Brown 那个哈希）
运算：对数据施加的操作，运算定义（或运算描述，确定运算的功能，是抽象的）+ 运算实现（在 存储结构 上确定对应运算实现算法，是具体的）。

抽象数据类型：数据逻辑结构 + 运算定义

§1.2 算法和算法分析

§1.2.1 算法及其描述

算法设计应满足：

正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是最重要、最基本的要求。
可使用性：要求算法能够很方便地使用。这个特性也称 用户友好 性。
可读性：算法应该 易于人的理解，即可读性好。算法的逻辑必须是清晰的、简单的和结构化的。
健壮性：要求算法具有很好的 容错性，即提供异常处理，能够对不合理的数据进行检查。
高效率与低存储量需求：好的时间和空间效率。

算法的特性：

有限性：一个算法必须总是（对任何合法的输入值）在执行 有限步之后结束，且每一步都可在 有限时间内完成。
确定性：算法中每一条指令必须有确切的含义，不会产生二义性。
可行性：算法中 每一条运算 都必须是足够基本的，就是说它们原则上都能 精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。
输入性：一个算法有零个或多个输入。
输出性：一个算法有一个或多个输出。

通常用函数返回值表示算法能否正确执行，另外还可以带有形参。任何算法（用函数描述）都是 被调用的，如果一个函数不被调用，这样的函数是没有意义的。

§1.2.2 算法分析

不是分析算法是否正确或是否容易阅读，主要是考察算法的 时间和空间效率，以求改进算法或对不同的算法进行比较。

有两种衡量算法效率的方法：事后统计法、事前分析估算法。事后统计法的缺点一是必须执行程序，二是存在其他因素掩盖算法本质。因此通常采用 事前分析估算法 来分析算法效率。

时间复杂度：算法中所有语句的频度之和记做 $T(n)$ ，它是问题规模 $n$ 的函数。当问题规模 $n$ 趋向无穷大时， $T(n)$ 的 数量级 称为渐进时间复杂度，简称为时间复杂度，记作 $T(n)=\mathrm{O}(f(n))$ ，例如：

一个没有循环的算法中基本运算次数与问题规模 $n$ 无关，记作 $\mathrm{O}(1)$ ，也称作常数阶。
一个只有一重循环的算法中基本运算次数与问题规模 $n$ 的增长呈线性增大关系，记作 $\mathrm{O}(n)$ ，也称线性阶。
其余常用的还有：平方阶 $\mathrm{O}(n^2)$ 、立方阶 $\mathrm{O}(n^3)$ 、对数阶 $\mathrm{O}(\log n)$ 、指数阶 $\mathrm{O}(2^{n})$ 等等。

空间复杂度：一个算法的存储量包括形参所占空间和临时变量所占空间等。对算法进行存储空间分析时，只考察 临时变量 所占空间。算法的临时空间一般也作为问题规模 $n$ 的函数，同样以 数量级 形式给出，记作 $S(n) = \mathrm{O}(g(n))$ 。若算法所需临时空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作。若所需临时空间依赖于特定的输入，则通常按最坏情况来考虑。