还有三天考试，粗略的过一下这门熟悉(? 并非)的知识吧

1 什么是数据结构与算法

1.1 数据结构

数据结构就是在我们使用计算机解决实际问题的过程中，把问题建模为数学模型后，互相之间存在着一种或多种特定关系的数据元素的集合

1.2 算法

算法就是解决问题的一系列步骤，它有输入、输出，它必须有着：

• 确定性：对于每个情况下的每个操作，它都是明确的，不会产生歧义
• 有限性：算法的运行不能出现死循环，对于每个输入它必须都有结束的时候
• 可行性：算法的每个操作都可以通过已经实现的基本操作运算执行有限次实现

即数据结构与算法相互关联，相互配合解决一个被建模为数学模型后的实际问题，数据结构定义数据元素之间的逻辑关系，算法关注如何高效实现数学模型上的相应操作，从而求解

2 数据

• 数据：客观事物的符号表示，计算机加工处理的对象，所有能输入到计算机中并能被计算机处理的符号总称
• 数据元素：在这里类似面向对象编程的对象的概念，组成数据的、有一定意义的基本单位
• 数据项：在这里的意义类似对象的成员变量，例如每个家庭成员(数据元素)包含姓名、性别、出生日期等数据项
• 数据对象：性质相同的数据元素的集合

2.1 结构

操作对象之间的关系称为结构，逻辑结构就是描述元素之间的逻辑关系，不考虑具体存储，分为线性结构和非线性结构，种类：

• 线性结构：数据元素之间存在一对一的关系，像一条线串在一起
• 树形结构：数据元素之间存在一对多的关系，像是树干和树枝
• 图状结构：数据元素之间存在多对多的关系，离散数学学过的
• 集合元素：数据结构之间的关系是属于同一个集合

2.2 数据结构表示形式

数据结构形式定义：二元组，比如Data_structure=(D,S)，这里的D表示这个数据结构所有操作对象的集合，S表示这些对象之间的关系的集合

2.3 数据结构的物理结构

物理结构就是数据结构在计算机内存中的表示，包含所有数据元素的值和他们之间的逻辑关系，两种存储结构：

• 顺序存储映像：顺序存储结构，借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系，比如编程语言中常见的数组，就是这种存储方式，拿一元数组举例，第一个位置存第一个元素的信息，第二个存第二个以此类推，以存储位置表示逻辑关系
• 非顺序存储映像：链式存储结构，借助指向每个数据元素存储地址的指针来表述数据元素之间的关系，比如链表，它的每个结点包含两部分：值和指针，指针存放的是和本数据元素有逻辑关系的元素的地址，比如链表结点指针里存的就是它的前驱或后继，树结点如果用这种方式表示，它存储的就是它的孩子结点

2.4 逻辑结构和物理结构的关系

• 物理结构是逻辑结构在计算机存储中的实现
• 一种逻辑结构可以采取不同的数据结构，比如树可以用上述的链式存储结构存储，也可以通过顺序存储结构邻接矩阵来表示
• 算法运算的定义与存储结构无关，但其实现依赖于具体的存储结构

2.5 数据类型的表示和实现

数据结构采用程序设计语言中的数据类型实现，整型、浮点型、字符…，这里不再赘述

2.6 抽象数据类型

C语言中的结构体乃至面向对象语言的对象在这里叫做抽象数据类型，它包括数据对象(就是成员变量)，数据关系(对象的成员变量之间的逻辑联系)，基本操作(成员方法)

课程教的其定义表示方法如下

ADT ADT_Name{
    数据对象：一个集合，包含数据类型的所有数据对象
    数据关系：一个集合，表示数据对象之间的逻辑关系
    基本操作：//一些函数，包括初始条件和操作结果
        InitList(&L)
            初始条件：L不存在
            操作结果：构造一个空的线性表
        DestoryList(&L)
            初始条件：L存在
            操作结果：销毁线性表L
}

考试时应该写的具体实现方法就是C语言的结构体吧，例：

typedef struct Point{
    double x; // 数据对象
    double y; // 数据对象
    double z; // 数据对象
} Point; // 数据关系就是x,y,z是一个点的三个坐标

void swapPoint(Point *p1,Point *p2){ // 基本操作
    Point temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

3 算法

算法的特性在前面说过，不赘述

3.1 算法的设计要求

• 正确性：对于任意合法输入，算法的输出对于对应问题来说都是正确的，不能存在错误输出的输入
• 健壮性：对于不合法的输入、异常情况，算法需要有合适的处理，而不会导致程序崩溃
• 可读性：算法的代码实现应该尽量优雅，变量、函数命名需要符合人类阅读习惯，能让别人读懂
• 效率和低存储量需求：算法的时间复杂度和空间复杂度应该尽量低，人话就是跑得快，内存占用小

3.2 算法效率的度量

最显然的想法就是算法设计全部完成后后，实际运行并测算其效率，但不利于宏观上的算法比较，因为运行算法的机器配置不同，用于测试的数据集也可能不同，所以我们有运行前的分析估算方法-Big O大人

3.2.1 时间复杂度

选取算法中对于该研究的问题来说可以说是基本操作的原操作，以这个操作重复执行的次数作为算法的时间量度，用公式表示就是

$$
T(n) = O(f(n))
$$

上面公式的解释：$T(n)$是一个算法不同语句执行的次数的和，整个含义是，随着问题规模n的增大，算法执行时间($T(n)$)的增长率和$f(n)$的增长率相同，$O(f(n))$称作算法的渐进时间复杂度，简称时间复杂度

再去深究这个式子的数学意义：设$T,f$是定义域为自然数的函数，$T(n)=O(f(n))$：若存在正数$c$和$n_{0}$，使得对一切$n\geq n_{0}$，$0<T(n)\leq cf(n)$，用极限表示就是

$$
\lim_{ n \to \infty }\frac{T(n)}{f(n)}=c<\infty
$$

人话就是：在输入数据规模n大到一定程度时，用$f(n)$乘上某个常数$c$就可以表征$T(n)$的大小，即$f(n)$可以表示$T(n)$的变化速度，从这里我们就可以看出，算法的时间复杂度只有在输入数据规模足够大的时候才有意义，它是从宏观上描述算法性能的一种方式，如果只是我们平时敲个代码，随便给几个小样例测试这种情况下，时间复杂度是没意义的(特别是在硬件设备越来越强强到没法再强的当下)

时间复杂度的估算差不多有以下原则：

• 对于不同操作，执行次数可能有阶数差异，比如某个算法的某个操作要执行n次，某个操作是$n^{2}$，则我们只取最大阶数的那一部分，这个算法的时间复杂度就是$O(n^{2})$
• 如果某个复杂操作，它要执行n次，这个复杂操作里包含的简单操作要执行$\log_{2}n$次，则整个算法时间复杂度就是两者相乘即$O(n\log_{2}n)$

常用时间复杂度：

• $O(1)$：常数，一般我们认为编程语言执行一次简单操作的时间是一个常数时间，比如一次比较、数据下标取值一次，算数运算、逻辑运算等
• $O(n),O(n^2),O(n^3)$：多项式型
• $O(\log n),O(n\log n)$：对数型
• $O(2^n),O(e^n)$：指数型

3.2.2 空间复杂度

空间复杂度和时间复杂度的思想差不多，是算法所需存储空间的量度

$$
S(n) = O(f(n))
$$

如果额外空间相对于输入数据量来说是常数，则称这个算法是原地工作，比如输入是一个长度为n的数组，算法全程在数组本身上操作，只建立了有限个与数组长度无关的辅助变量(比较绕，并不是不能建立辅助变量才叫原地工作，而是相对于输入数据量为常数个)