数据结构与算法
2022-07-17 14:05:03 2 举报AI智能生成
2023考研数据结构预算法完整详细思维导图
作者其他创作
大纲/内容
算法
串的模式匹配
简单模式匹配
KMP算法
next数组的求法
最大相同前后缀
计算机表达算法 P117
nextval数组的求法
查找算法
线性结构
顺序查找
有序表的顺序查找
折半查找（只适用于顺序结构）
分块查找
树形结构
二叉排序树
平衡二叉树
插入
LL平衡旋转
RR平衡旋转
LR平衡旋转
RL平衡旋转
删除
查找
红黑树
定义和性质
插入的3种情况
删除的4种情况
B树
定义和性质
查找
插入（分裂结点）
删除（合并结点）
B+树（用于数据库）
定义和性质
与B树的区别
散列表
散列函数构造方法
直接定址法
除留余数法
数字分析法
平方取中法
解决冲突的方法
开放定址法
线性探测法
平方探测法
双散列法
伪随机序列法
只能逻辑删除元素，并且需要定期维护散列表
拉链法
散列表性能分析
平均查找长度ASL
填装因子
排序算法
内部排序
插入排序
直接插入排序
折半插入排序
希尔排序
交换排序
冒泡排序
快速排序
选择排序
简单选择排序
堆排序
归并排序
基数排序
内部排序算法的比较
时间复杂度
空间复杂度
算法稳定性
算法的过程特征
算法的比较次数 与 序列初态的关系
算法的排序趟数 与 序列初态的关系
每趟结束是否有一元素可以到达最终位置
外部排序
步骤
1、生成初始归并段
2、归并归并段
归并趟数
S = h-1 = ⌈ logk(r) ⌉
败者树
减少内部排序时的比较次数
置换-选择排序
生成初始归并段
减小 r
最佳归并树
数据结构
线性结构
线性表
顺序表
链表
单链表
双链表
循环链表
循环单链表
循环双链表
静态链表
栈
顺序存储
顺序栈
共享栈
链式存储
链栈
应用
进制转换
迷宫求解
递归
表达式求值
括号匹配
队列
顺序存储
顺序队列（存在"假溢出"）
循环队列
链式存储
单链表队列
循环表队列
循环单链表队列
循环双链表队列
双端队列
输入受限的双端队列
输出受限的双端队列
应用
树的层次遍历
缓冲池SPOOLING技术
资源竞争的进程队列
页面替换算法
广度优先搜索图
特殊矩阵
对称矩阵
三角矩阵
三对角矩阵
稀疏矩阵
树
二叉树
顺序存储
链式存储
二叉树的遍历
先序遍历
递归算法
非递归算法
中序遍历
递归算法
非递归算法
后续遍历
递归算法
非递归算法
访问结点p时，栈内结点为p的所有祖先，可以用于查找根结点到p的路径
层次遍历
需要借助队列
由遍历序列构建唯一二叉树
先序序列 和 后序序列不能够唯一确定一个二叉树
线索二叉树（物理存储结构）
线索二叉树的构造
线索二叉树的遍历
二叉链表
存储结构
双亲表示法
区别 双亲表示法 和 二叉树的顺序存储
孩子表示法
孩子兄弟表示法
遍历方式
先根遍历（与二叉树的先序遍历相同）
后根遍历（与二叉树的中序遍历相同）
森林
森林与二叉树的转换
遍历方式
先序遍历（与二叉树的先序遍历相同）
中序遍历（与二叉树的中序遍历相同）
树的应用
哈夫曼树
哈夫曼树的构建
不存在度为0的结点
哈弗曼编码
并查集
图 G(V,E)
图的定义
有向图与无向图
连通图和强联通图
图的存储
邻接矩阵
适合稠密图
邻接表
十字链表（有向图）
邻接多重表（无向图）
图的遍历
广度优先 BFS
性能分析
空间复杂度O(|V|)
时间复杂度
邻接矩阵 O(|V|2)
邻接表 O(|V|+|E|)
深度优先 DFS
性能分析
空间复杂度O(|V|)
时间复杂度
邻接矩阵 O(|V|2)
邻接表 O(|V|+|E|)
图的应用
最小生成树（贪心算法）
Prim算法(适合稠密图)
时间复杂度O(|V|2)
Kruskal算法(适合稀疏图)
时间复杂度(|E|log|E|)
最短路径(有向图)
Dijkstra算法(贪心算法)
时间复杂度O(|V|2)
适用于正权值有向图
Floyd算法
时间复杂度O(|V|3)
适用于 无带负权值 的有向图
有向无环图描述表达式 DAG图
拓扑排序 AOV网
时间复杂度
邻接矩阵 O(|V|2)
邻接表 O(|V|+|E|)
深度优先也可以实现拓扑排序，栈中元素为逆拓扑排序
两个充分不必要
每个顶点有唯一的前驱后继关系，则拓扑排序唯一
若邻接矩阵是三角矩阵，则存在拓扑排序
关键路径 AOE网
关键路径不唯一
0 条评论
下一页
