《数据结构与算法》知识点整理

1 概述

1.1 数据结构

数据结构：抽象数据类型的物理实现。以主机的运行时间和内存的存储空间来权衡。
数据结构三要素：
逻辑结构：基本元素和元素之间的相互关系。
存储结构：具体表现方式，包括基本元素的表示和关系的表示。
操作：各种行为在存储结构上的具体实现算法。
数据结构的分类：
按逻辑结构分类：逻辑结构可用二元组$B = \langle K, R \rangle$来表示，$K$是结点的有穷集合，$R$是$K$上的一个关系。$K$上的二元组是$K$中元素的有序对，记为$\langle k, k’ \rangle$。$k$是$k’$的前驱，$k’$是$k$的后继。根据$R$的特点分为线性结构（每个结点最多一个前驱和一个后继）；树形结构（每个结点最多一个前驱，可有多个后继）；复杂结构（前驱、后继结点个数不限）。
按存储结构分类：顺序表示；链接表示；散列表示；索引表示。

1.2 算法

算法：由有穷规则构成的为解决某一类问题的运算序列（方法或过程）。可以由若干输入，通常有若干个输出。
算法的性质：
有穷性：一个算法必须在执行了有穷步后结束。
确定性：算法的每一步需要执行的动作必须严格清楚地给出规定。
可行性：算法中的每个动作原则上都能由机器或人准确完成。
算法的正确性：如果一个算法以一组满足初始条件的输入为开始，那么算法的执行一定会终止并得到满足要求的结果。
算法的设计方法：
贪心法：将整个问题分成若干阶段，每一个阶段都选择局部最优方案。
分治法：将规模较大问题分成几个较小问题，求解子问题再合并子问题的解，如二分法。
回溯法：采用一步一步向前试探的方法，当某一步有多种选择时先任选一种继续向前，无法前进时后退回上一层，即深度优先策略，如迷宫问题。
动态规划法：与分治法类似，但分解的子问题较多且子问题相互包含，需要保存计算的中间结果，通常自底向上进行。
分枝界限法：与回溯法类似，但采取广度优先策略，利用最优解属性的上下界控制分枝。

2 算法分析

大$O$表示法：若某个算法的代价为$T(n) = O(f(n))$，则存在常数$c > 0$，$N > 0$，当$n > N$时该算法的代价$T(n) \le c\cdot f(n)$。一般使用上确界。
其它表示法：
$T(n) = \Omega(f(n))$表示法：$T(n) \ge c\cdot f(n)$。
$T(n) = \Theta(f(n))$表示法：$T(n) = O(f(n))$且$T(n) = \Omega(f(n))$。

3 基本数据结构

3.1 线性表

线性表：简称表，可用二元组$L = \langle K, R \rangle$表示，$K = \{k_0, k_1, \cdots, k_{n-1}\}$，$R = \{\langle k_i, k_{i+1} \rangle\mid 0\le i \le n-2\}$。结点之间满足线性关系，第一个元素仅有一个后继，最后一个元素仅有一个前驱，其他元素仅有一个前驱和一个后继。
顺序表示：假设每个元素沿用$c$个存储单元，则$\text{loc}(k_i) = \text{loc}(k_0) + i \times c$。只要确定了首地址，线性表中的元素可以随机存储。
时间复杂度：插入删除$O(n)$，无序查找$O(n)$，有序查找$O(\log n)$，取值$O(1)$。
链接表示：每个结点包括数据域（存放元素信息）和指针域（指向后继元素）。每个结点只有一个指针域的链表为单链表。有时为了处理方便可以在单链表的第一个结点前加一个头结点。
时间复杂度：插入删除$O(1)$，查找取值$O(n)$。
循环链表：最后一个结点的指针指向第一个结点。从任一结点出发都能访问所有结点。
双链表：每个结点保存前驱和后继。克服单链表单向性的缺点。此外还有循环双链表。
有序表：数据项依照其可比性质（如整数大小）来决定在列表中的位置。对于有序表可以利用结点有序排列的特点节省查找时间，但添加时必须比较数据项选择合适位置插入。
顺序表与链表比较：
顺序表示优点：随机存取任一元素；缺点：插入删除效率低，估计最大空间困难。
单链表存储密度比顺序表低；插入删除效率高。

3.2 栈和队列

栈：所有的插入和删除都限制在表的同一端进行。允许操作的一端为栈顶，另一端为栈底。无元素的栈称为空栈。特点：后进先出。
队列：只允许在表的一端进行插入，在另一端删除。允许删除的一端为表头，允许插入的一端为队尾。无元素的队列称为空队。特点：先进先出。
队列的实现：环形队列，维护头结点和尾结点。
双端队列：数据项可以从两端分别插入和删除。集成了栈和队列的能力。

4 递归

递归：函数自己调用自己的做法。三定律：
递归算法必须有一个基本结束条件（最小规模问题的直接解决）。
递归算法必须能改变状态向基本结束条件演进（减小问题规模）。
递归算法必须调用自身（解决减小了规模的相同问题）。
递归调用的实现：栈。
动态规划：保存计算的中间结果。

5 排序与搜索

散列法：选择一个从关键码到地址的映射函数$h$（散列函数），对于每个关键码为$\text{key}$的元素，计算$h(\text{key})$（散列地址），期望把对应的元素存放到该地址。
碰撞：不相等的两关键码经散列函数计算得到相同散列地址。
完美散列函数：给定一组关键码，散列函数能把每个关键码映射到不同的地址。
负载因子$\alpha$：$\alpha = \cfrac {字典中节点数目}{基本区域能容纳的结点数}$。
散列函数设计：
三个特性：冲突最少、计算难度低、充分分散数据项。
求余数：关键码除以散列表大小，将余数作为地址。
折叠法：将数据项按照位数分为若干段，再将几段数字相加，最后对散列表大小求余，得到散列值。
平方取中法：首先将数据项做平方运算，然后取平方数的中间两位，再对散列表的大小求余。
冲突解决方案：
开地址法（开放寻址法）：在存储区域内形成探查序列，沿此序列逐个查找，知道找到要查找的元素或碰到未被占用的地址。线性探查法：即从冲突位置向后逐个扫描。也可每次增加$\text{skip}$个地址，但需要保证$\text{skip}$与散列表大小互质。
拉链法：在每个地址中开辟一个链表，先由$h(\text{key})$确定数据项在哪一条链表中，再在链表中进行插入、删除、检索等操作。
排序算法：
冒泡排序：对无序表进行多次比较交换，每次两两相邻比较，并将逆序数据项互换位置。时间开销为$O(n^2)$，空间开销为$O(1)$。
选择排序：每次比较记录最大项位置，最后与本次比较最后一项交换顺序。时间开销为$O(n^2)$，空间开销为$O(1)$。不稳定。
插入排序：维持一个已经排好序的子列表，每次将下一个数据项插入已排序列表中。时间开销为$O(n^2)$，空间开销为$O(1)$。
希尔排序：将整个列表按照$d_1$间隔分割为几个小列表，在小列表内排序，再取间隔为$d_2$（$d_2 < d_1$）分割列表，直到$d_n = 1$。时间开销为平均$O(n\log^2 n)$，最坏$O(n^2)$，空间开销为$O(1)$。
归并排序：利用递归算法，将列表分为两半，分别调用归并排序算法，直到子列表仅有一个项；然后按照大小顺序合并两个子列表。时间开销为$O(n\log n)$，空间开销为$O(n)$。
快速排序：选取“中值”将列表分为两半，左边项均小于中值，右边项均大于中值，然后在左右列表递归调用快速排序算法。时间开销为平均$O(n\log n)$，最坏$O(n^2)$，空间开销为$O(\log n)$。

6 树及其算法

树：由一个根结点和几棵互不相交的子树组成。二叉树：有两棵子树，分别为左子树和右子树。概念：
父结点、左（右）子结点、边：若$x$是二叉树的根结点，$y$是$x$左（右）子树的根结点，则$x$是$y$的父结点，$y$是$x$的左（右）子结点，有序对$\langle x,y\rangle$称为从$x$到$y$的边。
兄弟、祖先、子孙：具有同一父节点的结点彼此为兄弟。若结点$y$在以结点$x$为根的左（右）子树中且$y\neq x$，则$x$是$y$的祖先，$y$是$x$的子孙。
树叶、分支结点：左右子树均为空二叉树的结点称为树叶，否则称为分支结点。
路径、路径长度：若$x$是$y$的祖先，存在节点序列$x_0, x_1, \cdots, x_n$满足$x_0 = x$，$x_n = y$，则称该序列为从$x$到$y$的一条路径，$n$称为路径长度。
层数、高度：规定根的层数为$0$，其余结点的层数是父节点层数加$1$。二叉树中结点的最大层数称为二叉树的高度（深度）。结
度数：点的非空子树的个数叫做结点的度数。二叉树每个结点度数最大为$2$。
特殊的二叉树：
满二叉树：若一棵二叉树的任何结点或者是树叶或是两棵非空子树，则称为满二叉树。
完全二叉树：若一棵二叉树中只有最下面两层结点度数小于$2$，其余各层结点度数都等于$2$，且最下面一层的结点都集中在最左边，则称为完全二叉树。
二叉树的实现：嵌套列表法、结点链接法。
树的周游（遍历）：深度优先周游、广度优先周游。
深度优先周游：按照访问根节点的顺序，分为先根次序（前序遍历）、后根次序（后序遍历）、中根次序（中序遍历）。
广度优先周游：从$0$到$h$逐层从左往右访问每个结点。
实现：递归算法。
堆：对$n$个元素的序列，若满足$\begin{cases}k_i \le k_{2i+1}, \\ k_i \le k_{2i+2},\end{cases}$则称次序列为最小堆。可以用完全二叉树实现堆。
优先队列：遵循“最小元素先出”的规则。通过堆实现优先队列：
加入优先队列：先把新元素放在最后位置，再通过与父节点比较交换结点顺序，直到堆序性满足。
删除最小元素：先删除根节点，然后将最后一个结点放入根节点位置，再与子节点比较交换节点顺序，直到堆序性满足。
二叉排序树（二叉搜索树）：每个父结点的左子树结点值都比父节点小，右子树结点值都比父节点大。
检索：类似二分法，比较要查找的结点与左右子节点的大小关系，然后在左右子树中搜索。
插入：若根节点为空则插入根节点，否则若插入值等于根节点值则已存在，若插入值小于根节点值则插入左子树，否则插入右子树。
删除：找到被删除的结点，若其没有左子树，则将其右子树代替被删除结点。否则找到左子树中最右下的结点（在左子树中值最大），让被删除结点的右子树称为该结点的右子树，再让被删除节点的左子树代替被删除结点。
最佳二叉排序树：在检索过程中平均比较次数$E(n)$最小的二叉排序树。
构造（各结点等概率）：现将所有元素排序，然后对每个元素的值按二分法检索，将检索中遇到的还未在二叉排序树中的元素插入二叉排序树中。
平衡二叉排序树（AVL树）：每个结点左右子树高度之差的绝对值不超过$1$的二叉排序树。
平衡因子：结点右子树高度与左子树高度之差。
插入：若新结点插入不影响父结点为根的树的高度，则不破坏平衡；否则应调整。主要手段：将不平衡的子树进行旋转。
最小不平衡子树：离插入结点最近且根节点平衡因子绝对值大于$1$的树。
调整平衡：左重则先检查左子节点是否右重，若右重则先左旋转，然后原结点右旋转；右重相反。

7 图及其算法

图：由结点和边组成。有向图：每条边有方向。有向边表示为$\langle v_i, v_j \rangle$。无向图：每条边无方向。无向边表示为$(v_i, v_j)$。概念：
关联、邻接：若$\langle v_i, v_j \rangle$是有向边，则顶点$v_i$邻接到$v_j$或$v_j$邻接于$v_i$，边$\langle v_i, v_j \rangle$与顶点$v_i$，$v_j$相关联。若$(v_i, v_j)$是无向边，则$v_i$和$v_j$是相邻结点。
度、入度、出度：与顶点$v$相关联的边数称为度，记为$D(v)$。有向图以$v$为终点的边数称为入度$ID(v)$，为始点的边数称为出度$OD(v)$。
子图：设图$G = (V, E)$和图$G’ = (V’, E’)$，若$V’$是$V$的子集，$E’$是$E$的子集，则$G’$是$G$的子集。
根与有根图：有向图中若存在顶点$v$，从该顶点有路径可到达图中其他所有顶点，则称此图为有根图，$v$是图的根。
连通图、连通分量：无向图$G = (V, E)$中若从$v_i$到$v_j$之间有一条路径，则$v_i$和$v_j$是连通的。若$V(G)$中任意两个不同的顶点都是连通的，则$G$是连通图。无向图$G$中的最大连通子图称为$G$的连通分量。
强连通图、强连通分量：有向图$G = (V, E)$中若$V(G)$中任意两个不同的顶点都是连通的，则$G$是强连通图。有向图$G$中的最大连通子图称为$G$的强连通分量。
实现：
邻接矩阵：用二维矩阵，每行每列代表图中的顶点，若两个顶点之间连通则再相应行列值的矩阵分量中加以体现。
邻接列表：维护一个包含所有顶点的主列表，主列表中的每个顶点关联一个与自身连通的所有顶点的列表。
图的周游：深度优先周游（DFS）、广度优先周游（BFS）。
强连通分量算法：先对图$G$调用深度优先周游算法，为每个顶点计算结束时间，然后对$G$进行转置，得到$G^T$，再对$G^T$调用深度优先周游算法（以结束时间倒序搜索），最后深度优先森林中的每一棵树就是一个强连通分支。
Dijkstra算法：求顶点$v_0$到$v_n$的最短路径。维护两个集合$U$和$S$，其中$U$为已求出从$v_0$到它最短路径的顶点，$S = V - U$存放未确定最短路径的顶点。初始时$U$中只有$v_0$，其路径长度为$0$，$S$中为其它所有顶点，且与$v_0$直接相连的顶点路径长度已知，不直接相连的顶点路径长度为$+\infty$。每次从$S$中选取路径最短的顶点加入$U$中，并求出$v_0$通过$U$中顶点到达$S$中顶点的最短路径，重复操作直到$v_n$在$U$中。用优先队列实现可以使时间开销为$O((|V|+|E|)\log|V|)$。
最小生成树：对于连通的无向图或强连通的有向图，从任一顶点周游可以访问图中所有顶点，周游时形成的边称为图的一棵生成树。将生成树各边的权值加起来称为生成树的权，把权值最小的生成树称为最小生成树（MST）。
Prim算法：设$T = (U, TE)$是最小生成树，初始状态$T$为空树，先从$V$中任取一顶点放入$U$中，然后在所有一个顶点在$U$中、另一个顶点在$V - U$中的边中选取权最小的边放入$TE$，重复上述过程直到$U = V$。