Skip to content

数据结构 ​

复杂度 ​

时间复杂度

线性结构 ​

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

树 ​

一些定义

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

二叉树

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

二叉树应用

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

优先级队列(堆) ​

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

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

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

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

集合 ​

二叉查找树 ​

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

AVL 树 ​

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

排序 ​

算法做法
直接选择排序每次遍历找出最小放到数组开头
直接插入排序每次从数组中取出一个,直接插入有序数组中
堆排序建一个堆,然后不断出堆
冒泡排序easy
快速排序取第一个值作为中间值,通过一次扫描把数组分成两段,这两段再变成四段……直至每一段都只有一个数
归并排序每一个无序片段分成两份,将这两份分别进行归并排序后,进行排序
基数排序选择基数,不停倒袋子
排序时间复杂度
排序算法平均时间复杂度最好情况最坏情况输入有序输入逆序
直接选择排序O(n2)O(n^2)O(n2)O(n^2)O(n2)O(n^2)O(n2)O(n^2)O(n2)O(n^2)
直接插入排序O(n2)O(n^2)O(n)O(n)O(n2)O(n^2)O(n)O(n)O(n2)O(n^2)
堆排序O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)
冒泡排序O(n2)O(n^2)O(n)O(n)O(n2)O(n^2)O(n)O(n)O(n2)O(n^2)
快速排序O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(n2)O(n^2)O(n2)O(n^2)O(n2)O(n^2)
归并排序O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)O(nlog⁡n)O(n \log n)
基数排序O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)O(nk)

外排序 ​

B Tree ​

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

插入 直接插入。若插入的节点满了(有 MM 个键),向上分裂。分裂导致父节点满了则继续分裂。

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

B+ Tree ​

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

图 ​

基本术语

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

各种应用 ​

表达式计算 ​

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

e.g.


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

火车车厢重排问题 ​

问题描述

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

解决方案

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

排队系统模拟 ​

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

表达式树 ​

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

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

哈夫曼编码 ​

问题描述

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

一棵树
mermaid
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 的点可以放入队列中进行搜索。