数据结构

复杂度

时间复杂度

线性结构

结构名	特性	应用
线性表	无	大整数、多项式	约瑟夫环
栈	先入后出	表达式计算
队列	先入先出	火车车厢重排问题	排队系统模拟

树

一些定义

定义	描述
根节点	唯一一个没有直接前驱的结点
叶节点	没有后继的结点
度	结点直接后继的数目，树中所有结点度的最大值是树的度
父结点、子结点	直接前驱、直接后继
兄弟结点	同一个结点的子结点
祖先结点、子孙结点	到根结点路径上所有结点、子树上所有结点

二叉树

定义	描述
满二叉树	任一层的结点都达到了最大值
完全二叉树	在满二叉树底层从右至左删除若干结点
前序遍历	依次输出根结点、左儿子、右儿子
中序遍历	依次输出左儿子、根结点、右儿子
后序遍历	依次输出左儿子、右儿子、根结点

二叉树应用

1. 表达式树
2. 霍夫曼编码

优先级队列（堆）

定义 是一颗完全二叉树。满足子节点大于父节点。

入堆 插入到最后，然后向上冒泡

出堆 移除堆顶，把最后一个移动到堆顶，然后向下调整该元素经过的每一个三角形，确保其最小的数在父节点。

建堆 从有儿子的最后一个节点开始，向前调整三角形。

集合

二叉查找树

操作	描述
插入	从根节点开始，若当前为空，则在当前结点插入，若小于当前结点，在左子树中插入； 反之在右子树插入
删除	首先查找到要删除的结点。然后找出右子树最小的结点复制到该位置，再在右子树中 删除该最小结点。若要删除的结点没有右子树，则将结点左子树挂载到要删除的位置

AVL 树

为了避免有序数据的插入使二叉查找树退化为链表，AVL 树满足任何一个结点的左右子树高度之差不超过 1。为维持这种平衡，在二叉查找树的插入删除操作之后，必须检查 AVL 树的平衡。 见 AVL 树的一些探究

排序

算法	做法
直接选择排序	每次遍历找出最小放到数组开头
直接插入排序	每次从数组中取出一个，直接插入有序数组中
堆排序	建一个堆，然后不断出堆
冒泡排序	easy
快速排序	取第一个值作为中间值，通过一次扫描把数组分成两段，这两段再变成四段……直至每一段都只有一个数
归并排序	每一个无序片段分成两份，将这两份分别进行归并排序后，进行排序
基数排序	选择基数，不停倒袋子

排序时间复杂度

排序算法	平均时间复杂度	最好情况	最坏情况	输入有序	输入逆序
直接选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
直接插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(n)$	$O(n^2)$
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(n)$	$O(n^2)$
快速排序	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$
基数排序	$O(nk)$	$O(nk)$	$O(nk)$	$O(nk)$	$O(nk)$

外排序

B Tree

一个 $M$ 叉查找树。树上结点保存数据。节点的键作为分隔符存在，故子节点最多可以保存 $M-1$ 个键。$M$ 取决于数据大小。内存至少要能读取子节点所有键。

插入 直接插入。若插入的节点满了（有 $M$ 个键），向上分裂。分裂导致父节点满了则继续分裂。

删除 直接删除。若删除后的节点键数少于 $M/2$ ，向左侧或右侧节点借一个。借不到则说明可以向上借，即合并。合并导致父节点键数不满足要求，则继续借。

B+ Tree

一个 M 叉查找树。树上结点不保存数据，数据全部在叶节点中。

图

基本术语

术语	含义
顶点	Vertex，也叫做结点，是一个数据元素
边	Edge，描述顶点间的关系。如果这种关系是有向的，则用 <$V_i, V_j$> 表示，反之用 ($V_i, V_j$)表示。边是无方向的，则为无向图，反之则为有向图。
邻接	($V_i, V_j$)是一条边，则 $V_i$, $V_j$ 邻接；<$V_i, V_j$> 是一条边，则 $V_i$ 邻接到 $V_j$，或说 $V_j$ 与 $V_i$ 邻接
度	与该结点关联的边数。如果是有向图，指向结点的关系数称为入度，结点指出的关系称为出度
子图	两个图 $G_1=(V, E),\ G_2=(V', E')$，若 $V'\subseteq V, E'\subseteq E$，则 $G_2$ 为 $G_1$ 的子图
路径	两个结点之间存在若干条边，可以连接这两个结点。路径的不加权长度就是边的条数，加权长度就是边的权值之和。
有向无环图	不含环的有向图
简单路径	一条中间没有出现重复元素的路径。但允许首尾结点重复，即成为一个环
连通图	针对无向图而言。任意两个结点之间都存在至少一条路径就是一个连通图。非连通图可以分成若干极大的连通部分，称为连通分量
强连通图	与连通图类似，但针对有向图而言。
完全图	任意两个结点之间都邻接的图。
生成树	无向图的最小联通子图。包含所有的 $n$ 个顶点和 $n-1$ 条边
深度优先搜索	欧拉回路
广度优先搜索	拓扑序列

各种应用

表达式计算

一般过程：依次压栈，遇到后括号就可以开始计算一部分，直至前括号。如果扫描到的运算符优先级比操作符栈栈顶元素低，则可以执行之前的运算符。计算时，操作符出栈一个，运算数出栈两个，其结果再压栈回去一个。

e.g.

---

后缀表达式计算过程：依次入栈，操作符不入栈，直接计算。

火车车厢重排问题

问题描述

有一批火车应该按序开出，但是它们到达车站的顺序是不对的。车站有几条缓冲轨道，先到的火车可以在缓冲轨道中等候。现模拟该过程。

解决方案

第一辆火车开入缓冲轨道。接下来的火车按如下逻辑操作：如果之前的轨道中最后一辆火车先开，就可以进入该轨道；如果有多条轨道符合，则挑一条与自己出发时间最近的轨道进入；否则自己独占一条缓冲轨道。能够开出时可以立即开出。

排队系统模拟

单纯的队列应用，注意一下事件的生成。

表达式树

以运算符作为运算数的父节点。所有的运算数都在树的叶结点。

依次扫描，如果扫描到运算符，就从根节点开始，向其右儿子出发，与路径中的运算符相比较，直到找到优先级比它高（相同则考虑左结合）的结点，将该结点作为它的左儿子，然后读取下一个运算数作为其右儿子。遇见括号则将括号中的表达式构建为一棵树，当作一个操作数进行插入。

哈夫曼编码

问题描述

非等长编码可以用一棵树来表示。如果用 0 代表向左儿子找，用 1 表示向右儿子找，则字符都可以容易地在这棵树的叶结点上找到。比如下面这棵树，00 代表 C，01代表E，1 代表 D。

一棵树

graph TB;
A( ) --> B( ) --> C(C);
B( ) --> E(C);
A( ) --> D(E);

在非等长编码的情境中，需要找到一颗树，使得最常出现的字符所用编码最小，从而减小文件占用空间。这棵树就叫做霍夫曼树。

解决方案

构建霍夫曼树的步骤如下：

1. 将所有字符作为根节点，得到一片森林。
2. 按照权值（出现频率），每次选择权值最小的两棵树进行合并，合并后权值为两棵树权值之和。
3. 重复 2 直到只剩下一棵树。

欧拉回路

欧拉回路存在条件：

1. 若只有两个结点有奇数条边，则从这两个结点中任一个出发有欧拉回路。
2. 超过两个则不存在；全是偶数则任一个结点出发都有。

寻找欧拉回路

1. 进行深度优先搜索，删除路过的边，直至无路可走。无路可走说明已经回到了原点。
2. 对前一次生成的路径作遍历，从之中还有边未访问的结点出发继续作深度优先搜索。无路可走时说明已经回到了该结点。将这段路径拼接进来。
3. 重复 2 直至找到欧拉回路。

拓扑序列

存在条件

1. 有向无环图

寻找方法

1. 作广度优先搜索。只有入度为 0 的点可以放入队列中进行搜索。