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

第五章树与二叉树

树

基本概念

树的定义

树是n(n≥0)个结点的有限集。当n=0时，称为空树

特点

有且仅有一个特定的称为根的结点

没有后继的结点称为“叶子结点”（或终端结点）

有后继的结点称为“分支结点”（或非终端结点）

除根节点外的所有结点有且仅有一个前驱

每个结点可以有零个或多个后继

基本术语

结点的度

结点的分支数

树的度

树中结点的最大度数称为树的度

分支结点（非终端结点）

度大于0的结点

叶子结点（终端结点）

度为0（没有子女结点）的结点

结点的深度

从根结点开始自顶向下逐层累加

结点的高度

从根结点开始自底向上逐层累加

有序树和无序树

树种结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树

路径和路径长度

树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数（树中的路径是从上向下的）

森林

由m(m≥0)棵互不相交的树的集合

性质

结点数=总度数+1

度为m的树、m叉树的区别

高度为h的m叉树至少有h个结点； 高度为h、度为m的树至少有h+m-1个结点

二叉树

概念

定义

二叉树是n(n≥0)个结点的有限集合： ①或者为空二叉树，即n=0； ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树

特点

每个结点至多只有两颗子树

左右子树不能颠倒（二叉树是有序树）

特殊二叉树

满二叉树

定义

特点

只有最后一层有叶子结点

不存在度为1的结点

完全二叉树

定义

当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

特点

只有最后两层可能有叶子结点

最多只有一个度为1的结点

二叉排序树

左子树上所有结点的关键字均小于根结点的关键字； 右子树上所有结点的关键字均大于根结点的关键字； 左子树和右子树又各是一颗二叉排序树

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1

二叉树的性质

树的结点数=总度数+1

完全二叉树的性质

存储结构

顺序存储

一定要把二叉树的结点编号与完全二叉树对应起来

链式存储

n个结点的二叉链表共有n+1个空链域

二叉树的遍历和线索二叉树

二叉树的遍历

概念

按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次

先序遍历

根左右(NLR)

中序遍历

左根右(LNR)

后序遍历

左右根(LRN)

层次遍历

利用队列进行实现

由二叉树的遍历序列构造二叉树

前序+中序遍历序列

后序+中序遍历序列

层序+中序遍历序列

线索二叉树

线索二叉树的作用

是为了加快查找结点前驱和后继的速度

线索二叉树的存储结构

标志含义

ltag

1

表示lchild指向前驱

0

表示lchild指向左孩子

rtag

1

表示rchild指向后继

0

表示rchild指向右孩子

三种线索二叉树

先序线索二叉树

以先序遍历序列为依据进行“线索化”

中序线索二叉树

以中序遍历序列为依据进行“线索化”

后序线索二叉树

以后序遍历序列为依据进行“线索化”

找前驱/后继

树与森林

树的存储结构

双亲表示法

概念

采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。根结点下标为0，其伪指针域为-1。

优点

查指定结点的双亲很方便

缺点

查指定结点的孩子只能从头遍历，遍历整个结构

孩子表示法

概念

将每个结点的孩子结点都用单链表链接起来形成一个线性结构，顺序存储各个节点，每个结点中保存孩子链表头指针

优点

查指定结点的子女结点很方便

缺点

寻找双亲操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表

孩子兄弟表示法

概念

以二叉链表作为树的存储结构（左孩子右兄弟），孩子兄弟表示法使每个结点包括三部分内容： 结点值、指向结点第一个孩子结点的指针、指向结点下一个兄弟结点的指针

优点

实现树转换为二叉树的操作很方便

缺点

从当前结点查找其双亲结点比较麻烦(若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便)

树、森林与二叉树的转换

本质：用二叉链表存储森林

左孩子右兄弟

森林中各个树的根结点之间视为兄弟关系

树和森林的遍历

树的遍历

先根遍历

若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则

其遍历序列与这棵树相应二叉树的先序序列相同

后根遍历

若树非空，先依次遍历根结点的每棵子树，再访门根结点，遍历子树时仍遵循先子树后根的规则

其遍历序列与这棵树相应二叉树的中序序列相后

森林的遍历

先序遍历

若森林非空，访问森林中第一棵树的根结点，先序遍历第一棵树中根结点的子树森林，先序遍历除去第一棵树之后剩余的树构成的森林

中序遍历

若森林非空，中序遍历森林中第一棵树的根结点的子树森林，访问第一棵树的根结点，中序遍历除去第一棵树之后剩余的树构成的森林

树与二叉树的应用

二叉树的应用

哈夫曼树

带权路径长度

结点的权：有某种现实含义的数值(如：表示结点的重要性等)

结点的带权路径长度：从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积

树的带权路径长度：树中所有叶结点的带权路径长度之和(WPL)

哈夫曼树的定义

在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最有二叉树

哈夫曼树（也称最优二叉树）的构造

过程

特点

①每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大； ②哈夫曼树的结点总数为2n - 1； ③哈夫曼树中不存在度为1的结点； ④哈夫曼树并不唯一，但WPL必然相同且为最优

哈夫曼编码

基本概念

固定长度编码

在数据通信中，对每个字符用相等长度的二进制位来表示

可变长度编码

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

前缀编码

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

构造哈夫曼编码

将每个出现的字符当作一个独立的结点，其权值为它出现的频度(或次数)，构造出对应的哈夫树， 其中边标记为0表示"转向左孩子"，标记为1表示"转向右孩子"

树的应用

并查集

概念

是一种简单的集合表示

操作

Initial(S)

初始化并查集，将所有数组元素初始化为-1

Find(S[], x)

“查”，找到元素x所属集合

若结点数为n，Find最坏时间复杂度为O(n)

Union(S[], root1, root2)

“并”，将两个集合合并为一个集合

优化

用根结点的绝对值表示一棵树(集合)的结点总数

Union操作合并两棵树时，小树并入大树

代码

基本操作

最坏时间 复杂度

Union优化

最坏时间 复杂度

Find优化（压缩路径）

最坏时间 复杂度

第六章图

基本概念

图的定义

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)集合； 注：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

基本术语

有向图

若E是有向边（也称弧）的有限集合时，则图G为有向图

无向图

若E是无向边（简称边）的有限集合时，则图G为无向图

简单图

简单图G满足：①不存在重复边；②不存在顶点到自身的边

多重图

多重图中某两个顶点之间的边数大于1条，又允许顶点通过一条边和自身关联

完全图（简单完全图）

对于无向图，|E|的取值范围为0到n(n-1)/2； 有n(n-1)/2条边的无向图称为完全图； 在完全图中任意两个顶点之间都存在边

对于有向图，|E|的取值范围为0到n(n-1)； 有n(n-1)条弧的有向图称为有向完全图； 在有向完全图中任意两个顶点之间都存在方向相反的两条弧

顶点的度、入度、出度

顶点-顶点关系描述

路径

回路

第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径

在路径序列中，顶点不重复出现的路径称为简单路径

简单回路

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路

路径长度

路径上边的数目

点到点的距离

从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离； 若从u到v根本不存在路径，则记该距离为无穷(∞)

无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的

有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图

若图中任何一对顶点都是强连通的，则称此图为强连通图

子图

设有两个图G=(V, E)和G'=(V,E')，若V是V的子集，且E是E的子集，则称G'是G的子图。 若有满足V(G) = V(G)的子图G'，则称其为G的生成子图

连通分量

强连通分量

生成树

生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林

边的权、带权图/网

边的权

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值

带权图/网

边上带有权值的图称为带权图，也称网

带权路径长度

当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

集中特殊形态的图

无向完全图

有向完全图

图的存储

邻接矩阵

概念

是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系）， 存储顶点之间邻接关系的二维数组称为邻接矩阵

特点

对于无向图

第i个结点的度 = 第i行（或第j列）的非零元素个数

对于有向图

第i个结点的出度 = 第i行的非零元素个数； 第i个结点的入度 = 第i列的非零元素个数； 第i个结点的度 = 第i行、第i列的非零元素个数之和

适合用于存储稠密图

只要确定了顶点编号，图的邻接矩阵表示方式唯一

无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

复杂度

时间复杂度

空间复杂度

邻接表

概念

特点

图的邻接表表示方式不唯一

适合用于存储稀疏图

复杂度

空间复杂度

无向图

边结点的数量是2| E |； 整体空间复杂度为O（| V | + 2| E |）

有向图

边结点的数量是| E |； 整体空间复杂度为O（| V | + | E |）

十字链表

实例

性能分析

空间复杂度

十字链表表示法的空间复杂度为O（| V | + | E |）

图的十字链表表示是不唯一的，但一个十字链表表示确定一个图

查找指定顶点的所有出边

顺着上图绿色线路找

查找指定顶点的所有入边

顺着上图橙色线路找

邻接多重表

实例

空间复杂度

邻接多重表表示法的空间复杂度为O（| V | + | E |） 

基本操作

Adjacent(G,x,y): 判断图G是否存在边<x,y>或(x, y)

无向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

有向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

Neighbors(G,x): 列出图G中与结点x邻接的边

无向图

邻接矩阵：O(| V |)

邻接表：O(1)~O(| V |)

有向图

邻接矩阵：O(| V |)

邻接表

出边

O(1)~O(| V |)

入边

O(| E |)

InsertVertex(G,x): 在图G中插入顶点x

无向图

邻接矩阵：O(1)

邻接表：O(1)

有向图

邻接矩阵：O(1)

邻接表：O(1)

DeleteVertex(G,x): 从图G中删除顶点x

无向图

邻接矩阵：O(| V |)

邻接表：O(1)~O(| E |)

有向图

邻接矩阵：O(| V |)

邻接表

删出边

O(1)~O(| V |)

删入边

O(| E |)

AddEdge(G,x,y): 若无向边(x, y)或有向边<x,y>不存在，则向图G中添加该边

无向图

邻接矩阵：O(1)

邻接表：O(1)

有向图

邻接矩阵：O(1)

邻接表：O(1)

RemoveEdge(G,x,y): 若无向边(x,y)或有向边<x, y>存在，则从图G中删除该边

无向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

有向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

FirstNeighbor(G,x): 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1

无向图

邻接矩阵：O(1)~O(| V |)

邻接表：O(1)

有向图

邻接矩阵：O(1)~O(| V |)

邻接表

找出边邻接点

O(1)

找入边邻接点

O(1)~O(| E |)

NextNeighbor(G,x,y): 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

无向图

邻接矩阵：O(1)~O(| V |)

邻接表：O(1)

有向图

邻接矩阵：O(1)~O(| V |)

邻接表：O(1)

Get_edge_value(G,x,y): 获取图G中边(x,y)或<x, y>对应的权值

无向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

有向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

Set_edge_value(G,x,y,v): 设置图G中边(x,y)或<x,y>对应的权值为v

无向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

有向图

邻接矩阵：O(1)

邻接表：O(1)~O(| V |)

图的遍历

概念

从图中某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次

广度优先遍历（BFS）

概念

类似于二叉树的层序遍历算法

复杂度分析

空间复杂度

借助辅助队列

最坏情况，辅助队列大小为O(| V |)

时间复杂度

邻接矩阵存储的图

邻接表存储的图

广度优先生成树

广度优先生成树由广度优先遍历过程确定

遍历非连通图可得广度优先生成森林

唯一性

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一，基于邻接矩阵的广度优先生成树唯一

同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一，基于邻接表的广度优先生成树不唯一

可以解决最短路径问题

深度优先遍历（DFS）

概念

类似于二叉树的先序遍历算法

复杂度分析

空间复杂度

借助递归工作栈

最坏情况，递归深度为O(| V |)

最好情况，O(1)

时间复杂度

邻接矩阵存储的图

邻接表存储的图

深度优先生成树

深度优先遍历确定深度优先生成树

深度优先遍历非连通图可得深度优先生成森林

唯一性

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，基于邻接矩阵的深度优先生成树唯一

同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一，基于邻接表的深度优先生成树不唯一

图的遍历和图的连通性

对于无向图

若无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中的所有结点。 若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点。

进行BFS/DFS遍历，调用BFS/DFS函数的次数=连通分量； 对于连通图，只需调用1次BFS/DFS\n

对于有向图

初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，只需要调用1次BFS/DFS函数

对于强连通图，从任一结点出发都只需要调用1次BFS/DFS函数

图的应用

最小生成树

概念

定义

对于一个带权连通无向图G =(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。 设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（MST）

特点

最小生成树可能有多个，但边的权值之和总是唯一且最小的

最小生成树的边数 = 顶点数 -  1。 去掉一条则不连通，增加一条则会出现回路

若一个连通图本身就是一棵树，则其最小生成树就是它本身

只有连通图才有生成树，非连通图只有生成森林

Prim算法

概念

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止

时间复杂度

适合用于边稠密图

Kruskal算法

概念

每次选择一条权值最小的边，使这条边的两头连通（原本已连通的就不选），直到所有结点都连通

时间复杂度

适合用于边稀疏而顶点较多的图

最短路径

单源最短路径

BFS算法（无权图）

局限性

只适用于无权图，或所有边的权值都相同的图

Dijkstra算法（带权图、无权图）

时间复杂度

局限性

不适用于有负权值的带权图

各顶点间的最短路径

Floyd算法（带权图、无权图）

复杂度

局限性

Floyd算法不能解决带有"负权回路"的图（有负权值 的边组成回路），这种图可能没有最短路径

有向无环图

概念

若一个有向图中不存在环，则称为有向无环图，简称DAG图

作用

是描述含有公共子式的表达式的有效工具

拓扑排序

AOV网

操作步骤

①从AOV网中选择一个没有前驱 (入度为0) 的顶点并输出

②从网中删除该顶点和所有以它为起点的有向边

③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止

时间复杂度

逆拓扑排序

实现算法

DFS算法

操作过程

①从AOV网中选择一个没有后继（出度为0）的顶点并输出

②从网中删除该顶点和所有以它为终点的有向边

③重复①和②直到当前的AOV网为空

性质

拓扑排序、逆拓扑排序序列可能不唯一

若图中有环、则不存在拓扑排序序列/逆拓扑排序序列

关键路径

概念

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销 (如完成活动所需的时间)， 称之为用边表示活动的网络，简称AOE网

AOE和AOV

相同点

AOE网和AOV网都是有向无环图

不同点

AOE网中的边有权值，而AOV网中的边无权值

相关概念

在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始

关键路径：从源点到汇点的所有路径中，具有最大路径长度的路径

关键活动：关键路径上的活动

求解步骤

①求所有事件的最早发生时间ve()

②求所有事件的最迟发生时间vl()

③求所有活动的最早发生时间e()

④求所有活动的最迟发生时间l()

⑤求所有活动的时间余量d()

特性

若关键活动耗时增加，则整个工程的工期将增长

缩短关键活动的时间，可以缩短整个工程的工期，但是当缩短到一定程度时，关键活动可能会变成非关键活动

可能有多条关键路径，只提高一条关键路径上的关键活动并不能缩短整个工程的工期， 只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的

第七章查找

顺序查找和折半查找

顺序查找

概念

又称线性查找，主要用于在线性表中进行查找，顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找

算法实现

平均查找长度

成功

失败

ASL = n + 1

优点

适合于顺序表、链表，表中元素有序无序都可以

缺点

当n较大时，平均查找长度较大，效率低

算法优化

若表中元素有序

当前关键字大于(或小于)目标关键字时，查找失败

平均查找长度

成功

失败

查找判定树

成功结点的关键字对比次数 = 结点所在层数

失败结点的关键字对比次数 = 其父结点所在层数

各个关键字被查概率不同

可按被查概率降序排列

时间复杂度

O(n)

折半查找

适用范围

折半查找又称二分查找，它仅适用于有序的顺序表

算法思想

查找判定树

构造

由mid所指元素将原有元素分割到左右子树中

Key：右子树结点数 - 左子树结点数 = 0或1

特性

折半查找的判定树是平衡的二叉排序树（左<中<右）

折半查找判定树，只有最下面一层是不满的

若查找表有n个关键字，则失败结点有n+1个

时间复杂度

注：折半查找仅适合于顺序存储结构，不适合链式存储结构，且要求元素按关键字有序排列

分块查找

概念

又称索引顺序查找，数据分块存储，块内无序，块间有序（吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找）

算法思想

索引表中记录每个分块的最大关键字、分块的区间

先查索引表（顺序或折半），再对分块内进行顺序查找

ASL

ASL = 查索引表的平均查找长度 + 查分块的平均查找长度

设有n个记录，均匀分为b块，每块s个记录

顺序查找索引表

折半查找索引表

注：对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在low > high，要在low所指分块中查找

树形查找

二叉排序树（BST）

二叉排序树的定义

二叉排序树，又称二叉查找树(BST)； 一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树： 左子树上所有结点的关键字均小于根结点的关键字； 右子树上所有结点的关键字均大于根结点的关键字； 左子树和右子树又各是一颗二叉排序树。

左子树结点值 < 根结点值 < 右子树结点值， 进行中序遍历，可得到一个递增的有序序列

查找操作

从根节点开始，目标值更小向左找，目标值更大向右找

插入操作

找到应该插入的位置(一定是叶子结点)，一定要注意修改其父结点指针

删除操作

1、被删结点是叶子结点，直接删除

2、被删结点只有左或右子树，用其子树顶替其位置

3、被删结点有左、右子树

可用其后继结点顶替，再删除后继结点

也可以用前驱结点顶替，再删除前驱结点

前驱结点：左子树最右下的结点

后继结点：右子树最左下的结点

查找效率分析

平衡二叉树（AVL）

定义

树上任一结点的左子树和右子树的高度之差不超过1

结点的平衡因子 = 左子树高 - 右子树高

插入操作

与二叉排序树一样，找到合适的位置进行插入操作，新插入的结点可能导致其祖先们平衡因子改变，导致失衡

调整不平衡情况

数据结构-平衡二叉树示例； 只需要根据平衡因子进行调整的方法

查找效率分析

红黑树（RBT）

定义

红黑树是二叉排序树

左子树结点值 < 根结点值 < 右子树结点值

与普通BST相比，性质如下

1、每个结点或是红色，或是黑色的

2、根节点是黑色的

3、叶结点 (外部结点、NULL结点、失败结点) 均是黑色的

4、不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)

5、对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同

插入操作

红黑树插入结点示例

数据结构-红黑树插入结点示例

红黑树插入结点规则

当前待插入结点的父结点是红色

叔叔结点是红色

叔叔结点+父亲结点+爷爷结点各取反色

爷爷结点检查更新（查看爷爷结点的叔叔结点颜色后循环更新）

叔叔结点是黑色

旋转+变色（后旋转的结点各取反色）

当前待插入结点的父结点是黑色

直接插入当前结点

时间复杂度

结论

从根到叶结点的最长路径不大于最短路径的2倍

与“黑高”相关的推论

根结点黑高为h的红黑树，内部结点数（关键字）至少有多少个？

根结点黑高为h的红黑树，内部结点数（关键字）至多有多少个？

B树和B+树

B树

概念

核心特性

2、对任一结点，其所有子树高度都相同

3、关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < ......

B树高度

最小高度

最大高度

B树插入

规则

核心要求

新元素一定是插入到最底层"终端结点"，用"查找"来确定插入位置

若插入结点后，结点关键字个数未超过上限，则无需做其他处理

B树删除-示例

数据结构-B树删除结点示例

B+树

概念

散列表

概念

散列表，又称哈希表。是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关。

装填因子：散列表的装填因子一般记为α，定义为一个表的装满程度

常见散列函数

除留取余法

散列表表长为m，取一个不大于m但最接近或等于m的质数p

散列函数为：H(key) = key % p

直接定址法

H(key) = key 或 H(key) = a*key + b； 其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况， 若关键字分布不连续，空位较多，则会造成存储空间的浪费。

数字分析法

选取数码分布较为均匀的若干位作为散列地址； 设关键字是r进制数 (如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些， 每种数码出现的机会均等;而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀 的若干位作为散列地址。这种方法适合于已知的关键字集合,若更换了关键字，则需要重新构造新的散列函数。

平方取中法

取关键字的平方值的中间几位作为散列地址。 具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址 分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

冲突的处理

拉链法

把所有“同义词”存储在一个链表中

开放地址法

线性探测法

平方探测法

伪随机序列法

查找效率

取决于三个因素

散列函数

处理冲突方法

装填因子

第八章排序

插入排序

希尔排序

冒泡排序

快速排序

选择排序

堆排序-大根堆

二路归并排序

基数排序（最低位优先-LSD）

第一章绪论

数据结构的基本概念

数据

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素、数据项

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理；一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据对象、数据结构

数据对象是具有相同性质的数据元素的集合，是数据的一个子集；数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构的三要素

逻辑结构

数据元素之间的逻辑关系，与存储结构无关，是独立于计算机的。

线性结构

一般线性表

受限线性表

栈和队列

串

线性表推广

数组

非线性结构

集合结构

树形结构

一般树

二叉树

图状结构

有向图

无向图

物理结构（存储结构)

存储结构是逻辑结构在计算机上的映射，不能独立于逻辑结构而存在

索引存储

在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）

优点

检索速度快

缺点

附加的索引表额外占用存储空间

增加和删除数据时需要修改索引表，花费时间多

链式存储

逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系

优点

不会出现碎片现象，能充分利用所有存储单元

缺点

只能实现顺序存储

每个元素因存储指针而占用额外的存储空间

散列存储

根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储

优点

检索、增加和删除结点的操作都很快

缺点

散列函数设计不好时，会出现元素存储单元的冲突，而解决冲突会增加时间和空间的开销

顺序存储

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的临界关系来体现

优点

可以实现随机存取，每个元素占用最少的存储空间

缺点

只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片

数据的运算

针对于某种逻辑结构，结合实际需求，定义基本运算

算法的基本概念

程序=数据结构+算法

什么是算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

算法的五个特性

有穷性、确定性、可行性、输入、输出

"好"算法的特质

正确性、可读性、健壮性、高效率与低存储量需求

算法的时间复杂度

常见渐近时间复杂度

口诀：“常对幂指阶”

计算规则

加法规则

多项相加，只保留最高阶的项，且系数变为1

乘法规则

多项相乘，都保留

时间复杂度示例链接

题目来源王道考研系列-《数据结构考研复习指导》

算法的空间复杂度

算法原地工作是指算法所需的辅助空间为常量，即为O(1)，而非不需任何额外辅助空间。

第二章线性表

线性表的逻辑结构

线性表定义

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：

线性表特点

表中每个数据元素所占空间一样大

表中元素的个数有限

表中元素有次序

线性表基本操作

InitList(&L): 初始化表。构造一个空的线性表L，分配内存空间。

DestoryList(&L): 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

ListInsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。

ListDelete(&L,i,&e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。

Length(L): 求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L): 判空操作。若L为空表，则返回true，否则返回false。

线性表的存储/物理结构

顺序表（顺序存储）

顺序表定义

顺序表概念

顺序表---用顺序存储的方式实现线性表。 顺序存储---把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

顺序表的实现方式

静态分配

使用“静态数组”实现

大小一旦确定就无法改变

动态分配

使用“动态数组”实现

L.data = (ElemType *) malloc (sizeof(ElemType) * size)

顺序表存满时，可再用malloc动态拓展顺序表的最大容量

需要将数据元素复制到新的存储区域，并用free函数释放原区域

提示：动态分配仍然是顺序存储结构，依然是随机存取方式，只是分配空间大小可以在运行时决定

顺序表的特点

随机访问，即可以在O(1)时间内找到第i个元素（因为数据元素位置是顺序存放的， 只要知道第一个数据元素的地址，后面数据元素的存放地址就可以直接计算出来）

存储密度高，每个节点只存储数据元素（区别于链式存储，链式存储还需要存放指针）

拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

插入、删除操作不方便，需要移动大量元素

基本操作的实现

插入操作

ListInsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。

实现情况

最好情况

新元素插入到表尾，不需要移动元素，时间复杂度为O(1)

最坏情况

新元素插入到表头，需要将原有的n个元素全部向后移动，时间复杂度为O(n)

平均情况

时间复杂度为O(n)

删除操作

ListDelete(&L,i,&e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

实现情况

最好情况

删除表尾元素，不需要移动其他元素，时间复杂度为O(1)

最坏情况

删除表头元素，需要将后续的n-1个元素全部向前移动，时间复杂度为O(n)

平均情况

时间复杂度为O(n)

查找操作

按位查找

GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。

实现情况

最好/最坏/平均时间复杂度都是O(1)

按值查找

LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素。

实现情况

最好情况

目标元素在表头，时间复杂度为O(1)

最坏情况

目标元素在表尾，时间复杂度为O(n)

平均情况

时间复杂度为O(n)

链表（链式存储）

单链表

单链表定义

概念

用"链式存储"(存储结构)实现了"线性结构"(逻辑结构)。对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。 各结点间的先后关系用一个指针表示。

单链表特点

优点

不要求大片连续空间，改变容量方便

插入和删除不需要移动元素，只需要修改指针

缺点

非随机存取的存储结构，要耗费一定空间存放指针

查找某个特定的结点时，需要从表头开始遍历，依次查找

两种实现

不带头结点

空表判断：L == NULL。写代码不方便

带头结点

空表判断：L->next == NULL。写代码更方便

头结点和头指针的区别

不管带不带头结点， 头指针都始终指向链表的第一个结点， 而头结点是带头结点的链表中第一个结点，头结点数据域可以不设任何信息，也可以记录表长等信息（单链表的长度是不包含头结点的）。

引入头结点的优点

由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表中的其他位置上的操作一致，无须进行特殊处理。

无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理得到了统一。

基本操作的实现

插入

按位序插入

ListInsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。

实现情况

带头结点

如果元素插入在表头，最好时间复杂度O(1)

如果元素插入在表尾，最坏时间复杂度O(n)

平均时间复杂度O(n)

不带头结点

插入或删除第一个元素时，需要修改头指针L

指定结点的后插操作

时间复杂度O(1)

指定结点的前插操作

循环查找指定元素的前驱，找到后在对指定元素进行后插，时间复杂度O(n)

插入一个新的结点后交换数据域部分时间复杂度O(1)

删除

查找待删除元素的前驱，找到后再将删除结点删除时间复杂度O(n)

将其后继结点的值赋予其本身，然后删除后继结点，时间复杂度O(1)

查找

按位查找

时间复杂度O(n)

按值查找

时间复杂度O(n)

求单链表长度

时间复杂度O(n)

建立

尾插法

时间复杂度O(n)

头插法

时间复杂度O(n)

双链表

定义

为了克服单链表无法访问某个结点的前驱结点而引入的概念。双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。

基本操作的实现

插入

时间复杂度O(1)

删除

时间复杂度O(1)

循环链表

循环单链表

表尾结点的next指针指向头指针

空表判断：L->next == L

循环双链表

表头结点的prior指向表尾结点； 表尾结点的next指向头结点

空表判断：L->proir == L && L->next == L

静态链表

定义

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

特点

优点

增、删操作不需要移动大量元素，只需修改指针

缺点

不能随机存取，只能从头结点开始依次往后查找：容量固定不可变

顺序表和链表对比

存取（读写）方式

顺序表可以顺序存取，也可以随机存取

链表只能从表头顺序存取元素

逻辑结构

都属于线性表，都是线性结构

物理结构/存储结构

链表

采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的

优点

离散的小空间分配方便，改变容量方便

缺点

不可随机存取，存储密度低

顺序表

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻

优点

支持随机存取、存储密度高

缺点

大片连续空间分配不方便，改变容量不方便

数据的运算/基本操作

增/删

顺序表

插入/删除元素要将后续元素都后移/前移

时间复杂度O(n)，时间开销主要来自移动元素

链表

插入/删除元素只需修改指针即可

时间复杂度O(n)，时间开销主要来自查找目标元素

查

按位查找

顺序表

O(1)

链表

O(n)

按值查找

顺序表

链表

O(n)

选择存储结构

第三章 栈、队列和数组

栈

栈的定义

概念

栈是只允许在一端进行插入或者删除操作的线性表。

基本操作

InitStack(&S): 初始化一个空栈S

StackEmpty(S):判断一个栈是否为空，若栈S为空则返回true，否则返回false

Push(&S,x):进栈，若栈S未满，则将x加入使之成为新栈顶

Pop(&S,&x):出栈，若栈S非空，则弹出栈顶元素，并用x返回

GetTop(S,&x):读栈顶元素，若栈S非空，则用x返回栈顶元素

DestoryStack(&S):销毁栈，并释放栈S占用的存储空间

特性

后进先出(LIFO)

栈的数学性质

栈的顺序存储结构

概念

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指示当前栈顶元素的位置

顺序栈的实现

栈顶指针: S.top，初始时设置S.top=-1； 栈顶元素: S.data[S.top]

进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素

出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1

栈空条件：S.top==-1

栈满条件：S.top==Maxsize-1

栈长：S.top+1

顺序栈的基本运算

初始化时top=-1

入栈

S.data[++S.top]=x

出栈

x=S.data[S.top--]

获取栈顶元素

x=S.data[S.top]

栈空条件

S.top==-1

栈满条件

S.top==Maxsize-1

初始化时top=0

入栈

S.data[S.top++]=x

出栈

x=S.data[--S.top]

获取栈顶元素

x=S.data[S.top]

栈空条件

S.top==0

栈满条件

S.top==Maxsize

共享栈

概念

两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置再共享空间的两端，两个栈顶向共享空间的中间延伸

初始化

0号栈栈顶指针初始时top0 = -1； 1号栈栈顶指针初始时top1 = MaxSize

栈满条件

top0 + 1 == top1

当0号栈进栈时top0先加1再赋值； 当1号栈进栈时top1先减1再赋值

栈的链式存储结构

概念

采用链式存储的栈称为链栈

优点

便于多个栈共享存储空间和提高其效率

不存在栈满上溢的情况

队列

队列的定义

概念

是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除

基本操作

InitQueue(&Q): 初始化队列，构造一个空队列Q

QueueEmpty(Q): 判队列空，若队列Q为空返回true，否则返回false

EnQueue(&Q,x): 入队，若队列Q未满，将x加入，使之成为新的队尾

DeQueue(&Q,&x): 出队，若队列Q非空，删除对头元素，并用x返回

GetHead(Q,&x): 读对头元素，若队列Q非空，则将对头元素赋值给x

特性

先进先出(FIFO)

队列的顺序存储结构

队列的顺序存储

概念

分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置

基本运算

初始状态（队空条件）：Q.front==Q.rear==0

进队操作：队不满时，先送值到队尾元素，再将队尾指针加1

出队操作：队不空时，先取队头元素值，再将队头指针加1

循环队列

概念

把存储队列元素的表从逻辑上视为一个环，称为循环队列

基本运算

初始时：Q.front=Q.rear=0

队首指针进1：Q.front=(Q.front+1)%MaxSize

队尾指针进1：Q.rear=(Q.rear+1)%MaxSize

队列长度：(Q.rear+MaxSize-Q.front)%MaxSize

队空：Q.front==Q.rear

判断队满

牺牲一个单元来区分队空和队满，入队时少用一个队列单元。 这是一种较为普遍的做法，约定以“对头指针在队尾指针的下一位置作为队满的标志”

队满条件：(Q.rear+1)%MaxSize==Q.front

队空条件：Q.front==Q.rear

队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize

类型中增设表示元素个数的数据成员

队空：Q.size==0

队满：Q.size==MaxSize

类型中增设tag数据成员，以区分是队满还是队空

tag=0时，若因删除导致Q.front==Q.rear，则为队空

tag=1时，若因插入导致Q.front==Q.rear，则为队满

队列的链式存储结构

概念

队列的链式表示称为链队列，实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点， Q.front==NULL & Q.rear==NULL时，链式队伍为空

特点

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题

双端队列

概念

双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍然是线性结构

分类

输出受限的双端队列

允许在一端进行插入和删除，但在另一端只允许插入的双端队列

输入受限的双端队列

允许在一端进行插入和删除，但在另一端只允许删除的双端队列

栈和队列的应用

栈的应用

栈在括号匹配中的应用

依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配

栈在表达式求值中的应用

三种算术表达式

中缀表达式

运算符在操作数中间

后缀表达式（逆波兰式）

运算符在操作数后面

前缀表达式（波兰式）

运算符在操作数前面

后缀表达式相关考点

中缀表达式转后缀表达式

题目来源王道考研系列-《数据结构考研复习指导》

后缀表达式求值

前缀表达式相关考点

中缀表达式转前缀表达式

前缀表达式求值

栈在递归中的应用

计算正整数的阶乘

求斐波那契数列

队列的应用

队列在树的层次遍历中的应用

队列在图的广度优先遍历中的应用

队列在操作系统中的应用

队列在计算机系统中的应用

数组和特殊矩阵

数组

概念

数组是由n(n≥1)个相同类型的数据元素构成的有限序列

数组和线性表的关系

数组是线性表的推广 一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，以此类推

数组的存储结构

一个数组的所有元素在内存中占用一段连续的存储空间

特殊矩阵的压缩存储

压缩矩阵：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，其目的是节省存储空间

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵

常见的特殊矩阵

对称矩阵

上（下）三角矩阵

对角矩阵

对称矩阵

三角矩阵

上三角矩阵

上三角区的所有元素均为同一常量

下三角矩阵

下三角区的所有元素均为同一常量

三对角矩阵

稀疏矩阵

矩阵中非零元素的个数t，相对于矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵

只存储非零元素

顺序存储：顺序存储三元组<行，列，值>

链式存储：十字链表法

第四章串

串的定义

概念

串，即字符串(String)是由零个或多个字符组成的有限序列

串与线性表

串是一种特殊的线性表，数据元素之间呈线性关系

基本操作

StrAssign(&T,chars)∶赋值操作。把串T赋值为chars

StrCopy(&T,S)∶复制操作。由串S复制得到串T

StrEmpty(S)∶判空操作。若S为空串，则返回TRUE，否则返回FALSE

StrCompare(S,T)∶比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0

Strlength(S)∶求串长。返回串S的元素个数

SubString(&Sub,S,pos,len)∶求子串。用Sub返回串S的第pos个字符起长度为len的子串

Concat(&T,S1,S2)∶串联接。用T返回由S1和S2联接而成的新串

Index(S,T)∶定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0

ClearString(&S)∶清空操作。将S清为空串

DestroyString(&S)∶销毁串。将串S销毁（回收存储空间）

串的存储结构

定长顺序存储

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列

串长表示方法

用一个额外的变量来存放串的长度

串值后面加一个不计入串长的结束标记字符"\0"，此时的串长为隐含值

串的实际长度只能小于等于MAXSIZE，超过预定义长度的串值会被舍去，称为截断，只能用不限定串长的最大长度，即采用动态分配的方式来解决

堆分配存储

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的

块链存储

每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构

串的模式匹配算法

暴力匹配法

概念

子串的定位操作通常称为串的模式匹配，它求的是子串(常称为模式串)在主串中的位置

算法

算法思想

主串长度为n，模式串长度为m

将主串中所有长度为m的子串依次与模式串对比

找到第一个与模式串匹配的子串，并返回子串起始位置

若所有子串都不匹配，则返回0

代码

最坏时间复杂度=O(mn)

KMP算法

概念

前缀

是指除最后一个字符以外，字符串的所有头部子串

后缀

是指除第一个字符外，字符串的所有尾部子串

部分匹配值

是指字符串的前缀和后缀的最长相等前后缀长度

算法

算法思想

暴力匹配法中，每趟匹配失败都是模式后移一位再从头开始比较，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串指针无须回溯，并可以直接从该位置继续比较

代码

最坏时间复杂度=O(m+n)

求next数组时间复杂度=O(m)

模式匹配过程最坏时间复杂度=O(n)

优点：主串无须回溯

KMP算法进一步改进

nextval数组