数据结构
2024-06-12 15:28:36 1 举报AI智能生成
该文件主要描述计算机科学与技术考研408中对应的《数据结构》内容，包括绪论+线性表+栈、队列和数组+串+树与二叉树+图+查找+排序八个章节内容，本篇导图是作者学习考研《数据结构》过程中记录的所有内容，导图中的链接也是作者在CSDN上发布的对应文章链接，可做参考，再次说明：本导图所有内容均是作者真实记录，希望对读者有所帮助。
作者其他创作
大纲/内容
数据结构
树是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)
后序遍历
利用队列进行实现
层次遍历
前序+中序遍历序列
后序+中序遍历序列
层序+中序遍历序列
由二叉树的遍历序列构造二叉树
前序、后序、层序序列的两两组合无法唯一确定一棵二叉树
二叉树的遍历
利用栈进行实现
是为了加快查找结点前驱和后继的速度
线索二叉树的作用
表示lchild指向前驱
1
表示lchild指向左孩子
0
ltag
表示rchild指向后继
表示rchild指向右孩子
rtag
标志含义
线索二叉树的存储结构
以先序遍历序列为依据进行“线索化”
先序线索二叉树
以中序遍历序列为依据进行“线索化”
中序线索二叉树
以后序遍历序列为依据进行“线索化”
后序线索二叉树
三种线索二叉树
找前驱/后继
线索二叉树
二叉树的遍历和线索二叉树
二叉树
采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。根结点下标为0，其伪指针域为-1。
查指定结点的双亲很方便
优点
查指定结点的孩子只能从头遍历，遍历整个结构
缺点
双亲表示法
将每个结点的孩子结点都用单链表链接起来形成一个线性结构，顺序存储各个节点，每个结点中保存孩子链表头指针
查指定结点的子女结点很方便
寻找双亲操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表
孩子表示法
以二叉链表作为树的存储结构（左孩子右兄弟），孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针、指向结点下一个兄弟结点的指针
实现树转换为二叉树的操作很方便
从当前结点查找其双亲结点比较麻烦(若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便)
孩子兄弟表示法
树的存储结构
顺序+链式存储
左孩子右兄弟
本质：用二叉链表存储森林
森林中各个树的根结点之间视为兄弟关系
树、森林与二叉树的转换
若树非空，先访问根结点，再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则
其遍历序列与这棵树相应二叉树的先序序列相同
先根遍历
若树非空，先依次遍历根结点的每棵子树，再访门根结点，遍历子树时仍遵循先子树后根的规则
其遍历序列与这棵树相应二叉树的中序序列相后
后根遍历
树的遍历
若森林非空，访问森林中第一棵树的根结点，先序遍历第一棵树中根结点的子树森林，先序遍历除去第一棵树之后剩余的树构成的森林
若森林非空，中序遍历森林中第一棵树的根结点的子树森林，访问第一棵树的根结点，中序遍历除去第一棵树之后剩余的树构成的森林
森林的遍历
树和森林的遍历
树和森林的遍历与二叉树遍历对应的关系
树与森林
结点的权：有某种现实含义的数值(如：表示结点的重要性等)
结点的带权路径长度：从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积
树的带权路径长度：树中所有叶结点的带权路径长度之和(WPL)
带权路径长度
在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最有二叉树
哈夫曼树的定义
过程
①每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大；②哈夫曼树的结点总数为2n - 1；③哈夫曼树中不存在度为1的结点；④哈夫曼树并不唯一，但WPL必然相同且为最优
哈夫曼树（也称最优二叉树）的构造
在数据通信中，对每个字符用相等长度的二进制位来表示
固定长度编码
对不同字符用不等长的二进制位来表示
可变长度编码
没有一个编码是另一个编码的前缀
前缀编码
将每个出现的字符当作一个独立的结点，其权值为它出现的频度(或次数)，构造出对应的哈夫树，其中边标记为0表示\"转向左孩子\"，标记为1表示\"转向右孩子\"
构造哈夫曼编码
哈夫曼编码
哈夫曼树
二叉树的应用
是一种简单的集合表示
初始化并查集，将所有数组元素初始化为-1
Initial(S)
若结点数为n，Find最坏时间复杂度为O(n)
“查”，找到元素x所属集合
“并”，将两个集合合并为一个集合
操作
用根结点的绝对值表示一棵树(集合)的结点总数
Union操作合并两棵树时，小树并入大树
优化
最坏时间复杂度
基本操作
Union优化
Find优化（压缩路径）
代码
并查集
树的应用
树与二叉树的应用
第五章 树与二叉树
图的定义
若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为连通图，否则称为非连通图
若图中任何一对顶点都是强连通的，则称此图为强连通图
连通图、强连通图
子图
连通分量
强连通分量
生成树
在非连通图中，连通分量的生成树构成了非连通图的生成森林
生成森林
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
边的权
边上带有权值的图称为带权图，也称网
带权图/网
当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
边的权、带权图/网
无向完全图
有向完全图
集中特殊形态的图
是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵
第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 |）
邻接多重表
存储无向图
邻接矩阵：O(1)
邻接表：O(1)~O(| V |)
邻接矩阵：O(| V |)
O(1)~O(| V |)
出边
O(| E |)
入边
邻接表：O(1)
邻接表：O(1)~O(| E |)
删出边
删入边
邻接矩阵：O(1)~O(| V |)
O(1)
找出边邻接点
O(1)~O(| E |)
找入边邻接点
图的存储
邻接矩阵+邻接表+十字链表+邻接多重表
从图中某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次
类似于二叉树的层序遍历算法
借助辅助队列
最坏情况，辅助队列大小为O(| V |)
邻接矩阵存储的图
邻接表存储的图
复杂度分析
广度优先生成树由广度优先遍历过程确定
遍历非连通图可得广度优先生成森林
同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一，基于邻接矩阵的广度优先生成树唯一
同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一，基于邻接表的广度优先生成树不唯一
唯一性
广度优先生成树
可以解决最短路径问题
广度优先遍历（BFS）
类似于二叉树的先序遍历算法
借助递归工作栈
最坏情况，递归深度为O(| V |)
最好情况，O(1)
深度优先遍历确定深度优先生成树
深度优先遍历非连通图可得深度优先生成森林
同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，基于邻接矩阵的深度优先生成树唯一
同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一，基于邻接表的深度优先生成树不唯一
深度优先生成树
深度优先遍历（DFS）
若无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中的所有结点。若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点。
进行BFS/DFS遍历，调用BFS/DFS函数的次数=连通分量；对于连通图，只需调用1次BFS/DFS\
初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，只需要调用1次BFS/DFS函数
对于强连通图，从任一结点出发都只需要调用1次BFS/DFS函数
图的遍历和图的连通性
图的遍历
最小生成树可能有多个，但边的权值之和总是唯一且最小的
最小生成树的边数 = 顶点数 - 1。去掉一条则不连通，增加一条则会出现回路
若一个连通图本身就是一棵树，则其最小生成树就是它本身
只有连通图才有生成树，非连通图只有生成森林
从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止
适合用于边稠密图
Prim算法
每次选择一条权值最小的边，使这条边的两头连通（原本已连通的就不选），直到所有结点都连通
适合用于边稀疏而顶点较多的图
Kruskal算法
最小生成树
只适用于无权图，或所有边的权值都相同的图
局限性
BFS算法（无权图）
不适用于有负权值的带权图
Dijkstra算法（带权图、无权图）
单源最短路径
Floyd算法不能解决带有\"负权回路\"的图（有负权值的边组成回路），这种图可能没有最短路径
Floyd算法（带权图、无权图）
各顶点间的最短路径
最短路径
BFS+Dijkstra+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 = 查索引表的平均查找长度 + 查分块的平均查找长度
顺序查找索引表
折半查找索引表
设有n个记录，均匀分为b块，每块s个记录
ASL
注：对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在low > high，要在low所指分块中查找
分块查找
顺序查找和折半查找
二叉排序树，又称二叉查找树(BST)；一颗二叉树或者是空二叉树，或者是具有如下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一颗二叉排序树。
左子树结点值 < 根结点值 < 右子树结点值，进行中序遍历，可得到一个递增的有序序列
二叉排序树的定义
从根节点开始，目标值更小向左找，目标值更大向右找
查找操作
找到应该插入的位置(一定是叶子结点)，一定要注意修改其父结点指针
插入操作
1、被删结点是叶子结点，直接删除
2、被删结点只有左或右子树，用其子树顶替其位置
可用其后继结点顶替，再删除后继结点
也可以用前驱结点顶替，再删除前驱结点
前驱结点：左子树最右下的结点
后继结点：右子树最左下的结点
3、被删结点有左、右子树
删除操作
查找效率分析
二叉排序树（BST）
树上任一结点的左子树和右子树的高度之差不超过1
结点的平衡因子 = 左子树高 - 右子树高
与二叉排序树一样，找到合适的位置进行插入操作，新插入的结点可能导致其祖先们平衡因子改变，导致失衡
数据结构-平衡二叉树示例
数据结构-平衡二叉树示例；只需要根据平衡因子进行调整的方法
调整不平衡情况
平衡二叉树（AVL）
左子树结点值 < 根结点值 < 右子树结点值
红黑树是二叉排序树
1、每个结点或是红色，或是黑色的
2、根节点是黑色的
3、叶结点 (外部结点、NULL结点、失败结点) 均是黑色的
4、不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)
5、对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同
与普通BST相比，性质如下
数据结构-红黑树插入结点示例
红黑树插入结点示例
爷爷结点检查更新（查看爷爷结点的叔叔结点颜色后循环更新）
叔叔结点+父亲结点+爷爷结点各取反色
叔叔结点是红色
旋转+变色（后旋转的结点各取反色）
叔叔结点是黑色
当前待插入结点的父结点是红色
直接插入当前结点
当前待插入结点的父结点是黑色
红黑树插入结点规则
从根到叶结点的最长路径不大于最短路径的2倍
结论
根结点黑高为h的红黑树，内部结点数（关键字）至少有多少个？
根结点黑高为h的红黑树，内部结点数（关键字）至多有多少个？
与“黑高”相关的推论
红黑树（RBT）
树形查找
二叉排序树、平衡二叉树、红黑树对比；其中平衡二叉树适用于以查找为主、很少用于插入/删除的场景，红黑树适用于频繁插入/删除的场景，实用性更强
2、对任一结点，其所有子树高度都相同
3、关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 < ......
核心特性
最小高度
最大高度
B树高度
核心要求
若插入结点后，结点关键字个数未超过上限，则无需做其他处理
新元素一定是插入到最底层\"终端结点\"，用\"查找\"来确定插入位置
规则
B树插入
数据结构-B树删除结点示例
B树删除-示例
B树
B+树
B树和B+树
B树和B+树对比
散列表，又称哈希表。是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关。
装填因子：散列表的装填因子一般记为α，定义为一个表的装满程度
散列表表长为m，取一个不大于m但最接近或等于m的质数p
散列函数为：H(key) = key % p
除留取余法
H(key) = key 或 H(key) = a*key + b；其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
直接定址法
数字分析法
取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
平方取中法
常见散列函数
把所有“同义词”存储在一个链表中
拉链法
线性探测法
平方探测法
伪随机序列法
开放地址法
冲突的处理
注意：采用“开放定址法”时，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除
散列函数
处理冲突方法
装填因子
取决于三个因素
查找效率
散列表
第七章 查找
插入排序
希尔排序
冒泡排序
快速排序
选择排序
堆排序-大根堆
二路归并排序
基数排序（最低位优先-LSD）
第八章 排序
数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据
数据元素是数据的基本单位，通常作为一个整体进行考虑和处理；一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。
数据元素、数据项
数据对象是具有相同性质的数据元素的集合，是数据的一个子集；数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据对象、数据结构
一般线性表
栈和队列
串
受限线性表
数组
线性表推广
线性结构
集合结构
一般树
树形结构
图状结构
非线性结构
数据元素之间的逻辑关系，与存储结构无关，是独立于计算机的。
逻辑结构
检索速度快
附加的索引表额外占用存储空间
增加和删除数据时需要修改索引表，花费时间多
在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）
索引存储
不会出现碎片现象，能充分利用所有存储单元
只能实现顺序存储
每个元素因存储指针而占用额外的存储空间
逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系
检索、增加和删除结点的操作都很快
散列函数设计不好时，会出现元素存储单元的冲突，而解决冲突会增加时间和空间的开销
根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储
散列存储
可以实现随机存取，每个元素占用最少的存储空间
只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的临界关系来体现
存储结构是逻辑结构在计算机上的映射，不能独立于逻辑结构而存在
非顺序存储
物理结构（存储结构)
针对于某种逻辑结构，结合实际需求，定义基本运算
数据的运算
数据结构的三要素
数据结构的基本概念
程序=数据结构+算法
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作
什么是算法
有穷性、确定性、可行性、输入、输出
算法的五个特性
正确性、可读性、健壮性、高效率与低存储量需求
\"好\"算法的特质
算法的基本概念
口诀：“常对幂指阶”
多项相加，只保留最高阶的项，且系数变为1
加法规则
多项相乘，都保留
乘法规则
计算规则
常见渐近时间复杂度
题目来源王道考研系列-《数据结构考研复习指导》
时间复杂度示例链接
算法的时间复杂度
算法原地工作是指算法所需的辅助空间为常量，即为O(1)，而非不需任何额外辅助空间。
算法的空间复杂度
第一章 绪论
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：
线性表定义
表中每个数据元素所占空间一样大
表中元素的个数有限
表中元素有次序
线性表特点
线性表的逻辑结构
InitList(&L): 初始化表。构造一个空的线性表L，分配内存空间。
DestoryList(&L): 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
Length(L): 求表长。返回线性表L的长度，即L中数据元素的个数。
PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L): 判空操作。若L为空表，则返回true，否则返回false。
线性表基本操作
顺序表---用顺序存储的方式实现线性表。顺序存储---把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
顺序表概念
使用“静态数组”实现
大小一旦确定就无法改变
静态分配
使用“动态数组”实现
L.data = (ElemType *) malloc (sizeof(ElemType) * size)
顺序表存满时，可再用malloc动态拓展顺序表的最大容量
需要将数据元素复制到新的存储区域，并用free函数释放原区域
提示：动态分配仍然是顺序存储结构，依然是随机存取方式，只是分配空间大小可以在运行时决定
动态分配
顺序表的实现方式
随机访问，即可以在O(1)时间内找到第i个元素（因为数据元素位置是顺序存放的，只要知道第一个数据元素的地址，后面数据元素的存放地址就可以直接计算出来）
存储密度高，每个节点只存储数据元素（区别于链式存储，链式存储还需要存放指针）
拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
插入、删除操作不方便，需要移动大量元素
顺序表的特点
顺序表定义
新元素插入到表尾，不需要移动元素，时间复杂度为O(1)
最好情况
新元素插入到表头，需要将原有的n个元素全部向后移动，时间复杂度为O(n)
最坏情况
时间复杂度为O(n)
平均情况
实现情况
删除表尾元素，不需要移动其他元素，时间复杂度为O(1)
删除表头元素，需要将后续的n-1个元素全部向前移动，时间复杂度为O(n)
最好/最坏/平均时间复杂度都是O(1)
按位查找
目标元素在表头，时间复杂度为O(1)
目标元素在表尾，时间复杂度为O(n)
按值查找
基本操作的实现
顺序表（顺序存储）
用\"链式存储\"(存储结构)实现了\"线性结构\"(逻辑结构)。对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。各结点间的先后关系用一个指针表示。
不要求大片连续空间，改变容量方便
插入和删除不需要移动元素，只需要修改指针
非随机存取的存储结构，要耗费一定空间存放指针
查找某个特定的结点时，需要从表头开始遍历，依次查找
单链表特点
空表判断：L == NULL。写代码不方便
不带头结点
空表判断：L->next == NULL。写代码更方便
带头结点
两种实现
不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中第一个结点，头结点数据域可以不设任何信息，也可以记录表长等信息（单链表的长度是不包含头结点的）。
头结点和头指针的区别
由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表中的其他位置上的操作一致，无须进行特殊处理。
无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理得到了统一。
引入头结点的优点
单链表定义
如果元素插入在表头，最好时间复杂度O(1)
如果元素插入在表尾，最坏时间复杂度O(n)
平均时间复杂度O(n)
插入或删除第一个元素时，需要修改头指针L
按位序插入
时间复杂度O(1)
指定结点的后插操作
循环查找指定元素的前驱，找到后在对指定元素进行后插，时间复杂度O(n)
插入一个新的结点后交换数据域部分时间复杂度O(1)
指定结点的前插操作
插入
查找待删除元素的前驱，找到后再将删除结点删除时间复杂度O(n)
将其后继结点的值赋予其本身，然后删除后继结点，时间复杂度O(1)
删除
时间复杂度O(n)
求单链表长度
查找
尾插法
头插法
建立
单链表
为了克服单链表无法访问某个结点的前驱结点而引入的概念。双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。
双链表
空表判断：L->next == L
表尾结点的next指针指向头指针
循环单链表
空表判断：L->proir == L && L->next == L
表头结点的prior指向表尾结点；表尾结点的next指向头结点
循环双链表
循环链表
分配一整片连续的内存空间，各个结点集中安置。
增、删操作不需要移动大量元素，只需修改指针
不能随机存取，只能从头结点开始依次往后查找：容量固定不可变
静态链表
链表（链式存储）
顺序表可以顺序存取，也可以随机存取
链表只能从表头顺序存取元素
存取（读写）方式
都属于线性表，都是线性结构
采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的
离散的小空间分配方便，改变容量方便
不可随机存取，存储密度低
链表
采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻
支持随机存取、存储密度高
大片连续空间分配不方便，改变容量不方便
顺序表
物理结构/存储结构
插入/删除元素要将后续元素都后移/前移
时间复杂度O(n)，时间开销主要来自移动元素
插入/删除元素只需修改指针即可
时间复杂度O(n)，时间开销主要来自查找目标元素
增/删
查
数据的运算/基本操作
选择存储结构
顺序表和链表对比
线性表的存储/物理结构
第二章 线性表
栈是只允许在一端进行插入或者删除操作的线性表。
InitStack(&S): 初始化一个空栈S
StackEmpty(S):判断一个栈是否为空，若栈S为空则返回true，否则返回false
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
顺序栈的实现
S.data[++S.top]=x
入栈
x=S.data[S.top--]
出栈
x=S.data[S.top]
获取栈顶元素
S.top==-1
栈空条件
S.top==Maxsize-1
栈满条件
初始化时top=-1
S.data[S.top++]=x
x=S.data[--S.top]
S.top==0
S.top==Maxsize
初始化时top=0
顺序栈的基本运算
两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置再共享空间的两端，两个栈顶向共享空间的中间延伸
0号栈栈顶指针初始时top0 = -1；1号栈栈顶指针初始时top1 = MaxSize
初始化
top0 + 1 == top1
当0号栈进栈时top0先加1再赋值；当1号栈进栈时top1先减1再赋值
共享栈
栈的顺序存储结构
采用链式存储的栈称为链栈
便于多个栈共享存储空间和提高其效率
不存在栈满上溢的情况
栈的链式存储结构
栈
是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除
InitQueue(&Q): 初始化队列，构造一个空队列Q
QueueEmpty(Q): 判队列空，若队列Q为空返回true，否则返回false
先进先出(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=0时，若因删除导致Q.front==Q.rear，则为队空
tag=1时，若因插入导致Q.front==Q.rear，则为队满
类型中增设tag数据成员，以区分是队满还是队空
判断队满
循环队列
队列的顺序存储结构
队列的链式表示称为链队列，实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点，Q.front==NULL & Q.rear==NULL时，链式队伍为空
用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题
队列的链式存储结构
双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍然是线性结构
允许在一端进行插入和删除，但在另一端只允许插入的双端队列
输出受限的双端队列
允许在一端进行插入和删除，但在另一端只允许删除的双端队列
输入受限的双端队列
分类
双端队列
队列
依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配
栈在括号匹配中的应用
运算符在操作数中间
中缀表达式
运算符在操作数后面
后缀表达式（逆波兰式）
运算符在操作数前面
前缀表达式（波兰式）
三种算术表达式
中缀表达式转后缀表达式
后缀表达式求值
后缀表达式相关考点
中缀表达式转前缀表达式
前缀表达式求值
前缀表达式相关考点
栈在表达式求值中的应用
计算正整数的阶乘
求斐波那契数列
栈在递归中的应用
栈的应用
队列在树的层次遍历中的应用
队列在图的广度优先遍历中的应用
队列在操作系统中的应用
队列在计算机系统中的应用
队列的应用
栈和队列的应用
数组是由n(n≥1)个相同类型的数据元素构成的有限序列
数组是线性表的推广一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，以此类推
数组和线性表的关系
一个数组的所有元素在内存中占用一段连续的存储空间
数组的存储结构
压缩矩阵：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，其目的是节省存储空间
对称矩阵
上（下）三角矩阵
对角矩阵
常见的特殊矩阵
特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵
上三角区的所有元素均为同一常量
上三角矩阵
下三角区的所有元素均为同一常量
下三角矩阵
三角矩阵
三对角矩阵
矩阵中非零元素的个数t，相对于矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵
顺序存储：顺序存储三元组<行，列，值>
链式存储：十字链表法
只存储非零元素
稀疏矩阵
特殊矩阵的压缩存储
数组和特殊矩阵
第三章 栈、队列和数组
串，即字符串(String)是由零个或多个字符组成的有限序列
串是一种特殊的线性表，数据元素之间呈线性关系
串与线性表
StrEmpty(S)∶判空操作。若S为空串，则返回TRUE，否则返回FALSE
Strlength(S)∶求串长。返回串S的元素个数
ClearString(&S)∶清空操作。将S清为空串
DestroyString(&S)∶销毁串。将串S销毁（回收存储空间）
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列
用一个额外的变量来存放串的长度
串值后面加一个不计入串长的结束标记字符\"\\0\"，此时的串长为隐含值
串长表示方法
串的实际长度只能小于等于MAXSIZE，超过预定义长度的串值会被舍去，称为截断，只能用不限定串长的最大长度，即采用动态分配的方式来解决
定长顺序存储
堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的
堆分配存储
每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构
块链存储
串的存储结构
串的定义
子串的定位操作通常称为串的模式匹配，它求的是子串(常称为模式串)在主串中的位置
主串长度为n，模式串长度为m
将主串中所有长度为m的子串依次与模式串对比
找到第一个与模式串匹配的子串，并返回子串起始位置
若所有子串都不匹配，则返回0
最坏时间复杂度=O(mn)
算法
暴力匹配法
是指除最后一个字符以外，字符串的所有头部子串
前缀
是指除第一个字符外，字符串的所有尾部子串
后缀
是指字符串的前缀和后缀的最长相等前后缀长度
部分匹配值
暴力匹配法中，每趟匹配失败都是模式后移一位再从头开始比较，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串指针无须回溯，并可以直接从该位置继续比较
求next数组时间复杂度=O(m)
模式匹配过程最坏时间复杂度=O(n)
最坏时间复杂度=O(m+n)
优点：主串无须回溯
KMP算法
nextval数组
KMP算法进一步改进
串的模式匹配算法
第四章 串
0 条评论
回复 删除
下一页
