数据结构思维导图模板_ProcessOn思维导图、流程图

排序

内部排序

插入排序

直接插入

思想

有序序列L-L(i)-无序序列L
若用数组保存，插入一个元素后，插入位置之后的元素要移动，所以移动的次数可能会较多

效率

时间

最坏

O(n^2)

空间

O(1)

稳定性

是

适用场景

顺序存储

基本有序

折半插入

比较次数

与待排序表初始状态

无关

时间

O(n*log 2 n)

移动次数

时间

O（n^2)

稳定性

是

适用场景

数据量不大的排序表

顺序存储

直接插入与折半插入图解

希尔排序（shell sort

思想

增量排序

追求表中元素基本有序，再逼近全局有序

效率

时间

平均

O(n^1.3)

最坏

O(n^2)

空间

O(1)

稳定性

否

仅用于顺序表，不用于链表

图解

交换排序

冒泡排序

效率

时间

最坏

O(n^2)

空间

O(1)

稳定性

是

适用场景

顺序表、链表均可

图解

快速排序

思想

取一个pivot，采用分治思想

效率

时间

平均

O(n*log 2 n)

最坏

O(n^2)

空间

O(log 2 n)

需要调用递归工作栈

稳定性

否

递归层数

log 2 n

特性

每趟排序都可以确定一个元素的最终位置（左边的数都比它小，右边的数都比它大）

优点

内部排序算法中性能最优

图解

选择排序

简单选择

效率

时间

最坏

O(n^2)

空间

O(1)

稳定性

否

与序列初始状态

无关

适用场景

顺序表、链表均可

图解

每一趟在待排序元素中选取关键字最小地元素，加入有序子序列，（交换两个数据位置）

堆排序

效率

时间

最坏

O(n*log 2 n)

空间

O(1)

稳定性

否

最多关键字比较次数

4*n

调整根堆

上升

对比一次

下坠

对比两次或一次

构造

初始堆

先排成完全二叉树

从最后一个孩子结点的父节点开始，（n/2向下取整），依次向前处理每个结点，注意处理完之后的结点的子树是否符合根堆

插入、删除

适用场景

适合关键字较多的情况

图解

归并排序

效率（二路归并）

时间

最坏

O(n*log 2 n)

特性

归并树（倒立的二叉树

空间

O(n)

稳定性

是

与原始序列

无关

适用场景

内部排序

多用2路归并

外部排序

多用多路归并

图解

基数排序

思想

基于关键字各位的大小

分配，收集……

方法

MSD

最高位优先法

LSD

最低位优先法

排列数字，升序

效率

时间

最坏

O(d*（n+r）)

空间

O(r)

稳定性

是

与序列的初始状态

无关

适用场景

可以方便拆分为d组，且d较小

必须为整数或者小数位已知

关键字的取值范围不大，即r较小

数据元素个数n较大

图解

外部排序

关注

关注如何使读/写磁盘次数更少

概念

在排序过程中，需要进行多次内存和外存之间的交换

外部排序总时间

内部排序时间+外存读写时间+内部归并需要时间

图解

优化

败者树

思想

减少内部归并的比较次数，从而减小内部归并的时间

比较次数

未优化之前

log 2 r 向上取整*（n-1）*（k-1)/log 2 k向上取整

优化之后

log 2 r 向上取整*（n-1）

特点

内部归并比较次数与k无关

内存空间满足条件下，增大归并的路数，减少I/O次数，提高外部排序速度

图解

置换-选择排序

思想

减少归并段个数

作用

生成初始归并段

图解

最佳归并树

思想

组织长度不等的初始归并段归并顺序

哈夫曼树推广到m叉树

记录数最小的最先归并

记录数多的最晚归并

作用

减少I/O次数

归并过程中磁盘I/O次数

=归并树WPL*2

归并树WPL

=读磁盘次数=写磁盘次数

注

须构造一棵严格二叉树

若不满足

需要增加长度为0的虚段

虚段个数

n=n0+nk

k*nk=n-1

图解

查找

概念

查找长度

对比关键字的次数

ASL

平均查找长度

查找成功

查找失败

线性结构

顺序查找

一般线性表

性能

查找成功ASL：（n+1）/2

不成功ASL：n+1

有序线性表

可用二叉判定树

成功结点查找长度

自身结点所在层数

失败结点查找长度

父节点所在层数

查找长度为关键字对比次数

n个结点，对应n+1个失败结点

ASL

n/2+n/(n+1)

存储结构

顺序、链式均可

图解

折半查找

查找过程可用二叉判定树描述

折半查找的二叉判定树为平衡二叉树

但二叉判定树不限制为二叉平衡树

树高

log[(n+1)/2]向上取整【树高不包括失败结点】

时间复杂度

log2n

失败结点

n+1个=成功结点的空链域个数

局限性

仅适合顺序存储结构

不适合链表存储结构

要求元素有序

图解

树高即关键字比较最多的次数

分块查找（顺序索引查找）

特点

块内无序，块间有序

综合顺序、折半查找优点，既有动态结构，又快速查找

索引表每个元素含各块最大关键字、各块第一个元素地址

查找效率

长度n，均匀的分为b块，s个记录/块

ASL

顺序查找

（b+1）/2+（s+1)/2

=(s^2+2*s+n)/2*s

对索引表折半

log2（b+1）向上取整+（s+1）/2

若s=n^(1/2)，ASL有最小值n^(1/2)+1

图解

树形结构

二叉排序（查找）树（BST，Binary Search Tree）

插入

一定是从叶节点插入

删除（三种情况）

叶结点

左（右）子树为空

两颗子树均不空

查找效率

取决于

树高

若为

二叉排序树

log2n

单支树

n

注

二分查找判定树唯一

二叉排序树查找不唯一（受关键字插入顺序影响

若为静态查找，宜选用顺序存储结构，二分查找实现查找；若为动态查找，宜选用二叉排序树作为逻辑结构

图解

二叉平衡树（AVL

查找效率分析

查为主
也是一棵二叉排序树，左<根<右

插入

平衡旋转

LL

RL

RR

LR

插入、删除，树高、查找

log2n

删除

图解

找到最小的不平衡树开始调整

2012

红黑树（RBT，Red-Black Tree）【非重点】

适用频繁插入、删除

特性

左根右，根叶黑，不红红，黑路同

左右高度差<=2倍

n个内部结点，h<=2*log2（n+1）

树黑高最少2^（h/2） -1

插入、删除，树高、查找

log2n

B树、B+树

B树（多路平衡查找树）

特点

方便查找

平衡因子为0的多路平衡查找树

每个结点至多有m颗子树，即m-1个关键字

除根节点，非叶结点至少有m/2向上取整，颗子树，即m/2向上取整-1个关键字

左根右依次增大

所有叶结点（失败结点）均出现在同一层

总叶结点=总关键字数+1

高度（磁盘存取次数）

插入、删除

插入

分裂位置

m/2向上取整

删除

不在终端结点

前驱后继替代

在终端结点

直接删除关键字

兄弟够借

兄弟不够借

合并

图解

注

名词

终端结点，最底层非叶结点

叶节点（外部结点）

图解

B+树

应用

数据库

特点

支持顺序查找

B树、B+树区分

散列结构

散列表（哈希表，Hash Table）

概念

散列函数

表中关键字映射到对应地址的函数

装填因子

实际数据数/可放数据数

构造

构造思想

尽量减少冲突，分布均匀

构造方法

直接定址法

除留余数法

H(key)=key%p

p为<=m的最大质数（m为散列表长）

数字分析法

思想

选择数码分布均匀的若干位数作为散列地址

平方取中法

处理冲突

开放定址法

Hi=（H（key）+di）%m

线性探测法

平方探测法

散列表长度m为可以表示为4*j+3的素数

伪随机序列法

双散列法

拉链法（链接法，chaining,链地址法）

适用

经常插入删除

查找、性能分析

注

开放定址法的空位置也算作一次比较

拉链法，有的学校空指针算作一次判定比较

图解

408-2010-线性探测再散列

图

基本概念

G（V，E），顶点集V，边集E

图解

注

线性表可以是空表，树可以是空树，但图不可以是空图（至少有一个顶点，可以没有边）

图

有向图

所有顶点入度之和=出度之和=E

入度，ID（v）；出度，OD（v）

无向图

所有顶点度之和：2*E

一条边连接两个顶点

完全图

完全图（无向图）

边数

n*(n-1)/2

有向完全图

边数

n*(n-1)

子图

生成子图

条件

包含原图的所有顶点

连通

连通、连通图、连通分量

连通图

任意两个顶点相连

n个顶点，最少有

n-1条边

非连通图

n个顶点，最多有

C（上标2，下标n-1）条边

图在任何情况下都是连通的C（上标2，下标n-1）+1条边

连通分量

无向图的极大连通子图

极大连通子图

子图连通，同时尽可能保留多的边

例

中国公路网（图）

大陆公路网（极大连通子图）

海南公路网（极大连通子图）

台湾公路网（极大连通子图）

强连通图、强连通分量

针对有向图

强连通图

图中任何一对顶点均是强连通的

最少需要n条边，形成回路

821-2020

强连通分量

极大强连通子图

图解

生成树、生成森林

生成树

包含图中所有顶点的极小连通子图

边尽可能少，但要保持连通

n个顶点，含有n-1条边

生成树不唯一

特性

减去一条边，变成非连通图

加上一条边，形成回路

生成森林

图解

几种特殊形态的树

完全图

稠密图，稀疏图

树、森林、有向树

有向树

一个顶点入度为0，其余顶点入度为1的有向图

其他

顶点的度，入度，出度

无向图

度为依附该顶点的边数

边的权、网

路径、路径长度、回路（2011-408）

路径

顶点和相邻顶点序偶构成的边的序列

回路

第一个顶点和最后一个顶点重合

简单路径

序列中顶点不重复出现

图解

图的存储

邻接矩阵法

定义

定义（无权）

定义（带权）

是用数组实现的顺序存储、空间复杂度较高

求顶点度、入度、出度

性能

性质

图解

邻接表法

定义

邻接表示并不唯一

图解

邻接表广度优先遍历，借助队列实现

十字链表法

只针对

有向图

定义

含义

空间复杂度

O(V+E)

邻接多重表

只针对

无向图

定义

含义

空间复杂度

O(V+E)

四种方式对比

图的遍历

BFS

广度优先搜索

相当于

层次遍历

需要借助辅助队列

性能分析

邻接矩阵存储

时间

O(V)

空间

O(V^2)

邻接表存储

时间

O(V)

空间

O(V+E)

单源最短路径问题

每次选择自己邻近的最短的边

广度优先生成树

邻接矩阵

生成树唯一

邻接表

生成树不唯一

对于无向图

调用BFS函数的次数=连通分量数

图解

DFS

深度优先搜索

相当于

先根树

借助递归工作栈

性能分析

邻接矩阵存储

时间

O(V^2)

空间

O(V)

邻接表存储

时间

O(E+V)

空间

O(V)

图解

图的遍历可用来判断连通性

对于无向图

上述两个函数调用BFS和DFS的次数等于该图的连通分量数

图的应用

最小生成树

Prim算法

思想

任取顶点，再选取离顶点最近的点相连

时间复杂度

O(V^2)

适合

边稠密的图

Kruskal算法

思想

每次选取权值最小的两个顶点

时间复杂度

O(E*log E))

适合

边稀疏，顶点较多

图解

最短路径

BFS

求单源最短路径，针对无权图

图解

Dijkstra算法

求解单源最短路径问题

构造过程中使用辅助数组

final[ ]

标记各顶点是否找到最短路径

dist[ ]

最短路径长度

path[ ]

最短路径前驱

适用情况

带负权值时不适用

可以带回路，也可以任意两个顶点的最短路径

Floyd

求解各顶点最短路径问题

思想

动态规划思想

适用情况

带负权值时适用

不适用带负权值的边组成的回路

复杂度

时间

O(V^3)

空间

O(V^2)

区分

DAG图

有向无环图

2019-6

用来描述表达式

AOV，AOE网均是有向无环图

化简DAG图

拓扑排序

AOV网

功能描述

DAG图表示一个工程

顶点表事件

有向边表关系

复杂度

邻接矩阵

时间

O(V^2)

邻接表

时间

O(V+E)

逆拓扑排序

注

DFS实现拓扑排序和逆拓扑排序

理解

图解

关键路径（2011-408）

AOE网

功能描述

顶点表事件

边表活动

理解

ve(k)

vl(k)

e(i)

l(i)

图解

绪论

数据结构三要素

逻辑结构

线性结构

线性表

关系

一对一关系

非线性结构

树形结构

一对多

图状结构/网状结构

多对多

数据的运算

存储结构（物理结构）

顺序存储

非顺序存储

链式存储

索引存储

散列存储

别名

哈希存储

概念

数据对象

相同性质元素集合

数据类型

原子类型

结构类型

抽象数据类型

ADT

描述数据逻辑结构、抽象运算【用数据对象、数据关系、基本操作集来表示】

数据结构

描述数据元素之间的关系

算法

对特定问题求解步骤的一种描述

程序=数据结构+算法

特性

有穷性

确定性

可行性

输入

输出

“好”算法

正确性

可读性

健壮性

效率与低存储量需求

效率度量

时间复杂度

空间复杂度

函数递归调用带来内存开销

图解

线性表

相同数据类型的n个数据元素的有限序列

顺序存储

顺序表

基本操作

特点

随机访问

存储密度高

扩容、插入删除操作不方便

存储结构

逻辑、物理均相邻

时间复杂度

O(n)

插入，删除，查找均为

链式存储

单链表

头插法

尾插法

注

需要添加一个表尾指针，用来始终指向表尾结点

双链表

特点

节点中含两个指针prior、next，分别指向前驱结点和后继结点

循环链表

区别于单链表

表尾结点指针不指向NULL，指向头结点

循环单链表

循环双链表

静态链表

分配一整片连续的内存空间，各个结点集中安置

数组方式实现的链表

结束标志

next==-1

栈、队列、数组

栈

卡特兰数

n个不同元素进栈，出栈元素不同的排列数为C(上标n，下标2n）/（n+1）

定义

只允许一段插入、删除的线性表

代码

栈类别

顺序栈

初始栈顶指针为-1【进栈指针先加1，再进栈；出栈，先出栈，指针再减1】
初始栈顶指针为0【……】

共享栈

链栈

定义

两种实现方式

带头结点

不带头节点

推荐使用

队列

定义

只允许在一端进行插入，在另一端进行删除的线性表

循环队列

实现思想

链式队列

定义

双端队列

两端插入，两端删除的线性表

栈、队列的应用

括号匹配

遇到左括号就入栈，遇到右括号就出栈

表达式求值

后缀表达式

中缀转后缀

”左优先“原则

计算

先弹出的是右操作数

前缀表达式

中缀转前缀

右优先原则

计算

先弹出的是左操作数

图解

递归中的应用

图解

递归工作栈

层次遍历中的应用

计算机系统中的应用

操作系统中

进程抢占，先来先服务

特殊矩阵压缩存储

数组

存储结构

行优先

列优先

一维数组

多维数组

压缩存储

对称矩阵

三角矩阵

三对角矩阵

稀疏矩阵

压缩存储

链式存储

顺序存储

图解

顺序存储：三元组；链式存储：十字链表

串

定义

图解

存储结构

图解

定长顺序存储

堆分配存储

块链存储

模式匹配算法

暴力匹配法

图解

KMP算法

next数组

值为前缀和后缀最长的共有元素的长度

图解

KMP算法优化

nextval数组

树与二叉树

树

图解

分支结点：度>0的结点

常考性质

树的性质

二叉树

是一颗有序树

存储结构

顺序存储

定义

链式存储

定义

n个结点的二叉链表共有n+1个空链域（可用于构造线索二叉树）

821-2020

性质

非空二叉树叶子结点等于度为2结点数+1，n0=n2+1

图解

特殊二叉树

满二叉树

完全二叉树

位置关系（初始结点从1开始）

二叉排序树（BST）

树中若存在相同关键字结点，则插入失败

平衡二叉树（AVL树）

联系第七章，查找

遍历

先序遍历

第一次路过访问的结点

中序遍历

第二次路过访问的结点

后序遍历

第三次路过访问的结点

层次遍历

需要借助一个辅助队列

根结点入队

若队列非空，则队头结点出队，访问该结点，然后将左右孩子插入队尾

未考虑层与层之间的关系

遍历序列构造二叉树

确定一棵二叉树

先序序列和中序序列

后序和中序

层序和中序

线索二叉树

定义

将没有左孩子，右孩子的结点线索化

存储结构

线索化

中序

后序线索树的遍历仍需要栈的支持

知识结构

找前驱、后继

顺序存储

应用

哈夫曼树（最优二叉树）

哈夫曼编码

用于数据压缩

编码

前缀编码-没有一个编码是另一个编码的前缀

固定长度编码

每个字符都用相等长度的二进制位表示

可变长度编码

允许对不同字符用不等长的二进制位表示

特点

只存在度为0和度为m的结点

n个结点新建n-1个结点

定义

所有叶结点的带权路径长度之和，最小

即树的带权路径长度WPL，最小

构造

每次选择两个最小的结点合并

哈夫曼树并不唯一

经典例题：2012-41-408

树、森林

定义，存储结构

双亲表示法

顺序存储

孩子表示法

顺序+链式存储

孩子兄弟表示法

链式存储

森林和二叉树的转换

左孩子右兄弟

本质

用二叉链表存储森林

图解

遍历

树，先根遍历【深度优先遍历】=森林先序遍历=二叉先序遍历

树，中根（后根）遍历【深度优先遍历】=森林中序遍历=二叉中序遍历

树层次遍历【广度优先遍历】（用队列实现）

应用

并查集

应用

判断连通性，判断环

kruskal算法=排序+并查集

代码实现

并，查

初始化并查集

操作

find

union

模拟操作

P185-9

存储方式

逻辑

双亲表示法的树

存储

数组

时间复杂度

find

优化前O(n)

优化后O(logn)

用根节点绝对值表示一棵树的结点总数

终极优化

find，先找到根节点，再进行压缩路径

union操作合并两棵树，小树并大树

优化图解

union

O（1）

总复杂度

优化前

o(n^2)

优化后

o（n）

kruskal时间复杂度

O(nlogn)