考研数据结构思维导图
2024-08-23 21:41:16 18 举报AI智能生成
考研数据结构思维导图
作者其他创作
大纲/内容
第五章树与二叉树
二叉树
树的性质
结点数=总度数+1
度为m的树第i层最多有m^i-1个结点
高度为h的m叉树最多有(m^h)-1/m-1
二叉树的性质
n0=n2+1
非空二叉树第k层上最多有2^k-1个节点
特殊的二叉树
满二叉树
完全二叉树
二叉排序树
平衡二叉树
二叉树的遍历与线索二叉树
二叉树的遍历
先、中、后序遍历
递归实现
非递归实现
层次遍历
线索二叉树
先序线索二叉树
中序线索二叉树
后序线索二叉树
树和森林
树的存储结构
双亲表示法
孩子表示法
孩子兄弟表示法
树、森林与二叉树的转换
树转二叉树
二叉树还原成树
森林转二叉树
二叉树还原成森林
树与二叉树的应用
哈夫曼树和哈夫曼编码
哈夫曼树
带权路径长度（WPL）最小
初始结点都成为了叶子结点
新建了n-1个结点
不存在度1的结点
哈夫曼编码
并查集
第六章图
图的存储
邻接矩阵
邻接表
邻接多重表
十字链表
图的遍历
广度优先遍历BFS
广度优先生成树
深度优先遍历DFS
深度优先生成树
图的相关应用
最小生成树MST
普利姆(prim)算法
克鲁斯卡尔（Kruskal）算法
最短路径
迪杰斯特拉（Dijkstra)算法
弗洛伊德（Floyd）算法
拓扑排序
AOV网
关键路径
AOE网
第七章查找
线性查找
顺序查找
无序表
ASL（成功）=（n+1）/2
有序表
ASL（成功）=（n+1）/2
折半查找
仅适用有序的顺序表
折半查找判断树
ASL画出判断树再计算
分块查找
块间有序，块内无序
索引表存储各块的最大关键字和起始地址
ASL（成功）=(b+1)/2 + (s+1)/2
树形查找
二叉排序树（BST）
插入
构造
「log(n+1)⌉<=h<=n
删除
不唯一
ASL看树分析
平衡二叉树（AVL）
插入
构造
删除
调整
①找到违反平衡条件的最小子树根节点
②找到一条根路径
③调整该路径上根节点出发的三个节点成三角形
④剩余结点按BST性质摆放
高度为h的平衡二叉树最少需要n(h)=n(h-1)+n(h-2)+1个节点
ASL看树形分析
红黑树
B树、B+树
散列查找
散列函数
直接定址法
除留余数法
数字分析法
平方取中法
冲突处理
开放定址法
线性探测法
平方探测法
双散列法
伪随机法
拉链法（链接法）
性能分析
ASL
ASL（成功）分母等于表中记录数
ASL（失败）分母等于散列函数的取值个数
在计算ASL（失败）时，与数组中空的位置的比较也算一次
装填因子
α=记录数/表长度
散列表的ASL只依赖于α
第一章绪论
三要素
逻辑结构
线性结构
线性表
栈
队列
串
数组
非线性结构
树
二叉树
有向图
无向图
存储结构
顺序存储
链式存储
索引存储
散列存储
数据的运算
定义
实现
算法
5特性
有穷性
确定性
可行性
输入
输出
好的算法
正确性
健壮性
可读性
高效率、低存储
时间、空间复杂度
非递归
一层循环
两层循环
递归
迭代法
主定理
第二章线性表
顺序表
插入
删除
单链表
单链表
建立单链表
头插法
尾插法
删除结点
通过前指针销毁本结点
将后一个结点的值复制到本结点，销毁后一个结点
插入结点
循环单链表
双链表
循环双链表
静态链表
第三章栈、队列和数组
栈
顺序栈
卡特兰数 C n,2n/n+1
入栈
出栈
共享栈
链栈
队列
循环队列
判空、判满条件
求队列长度
real、front的移动
链队列
双端队列
栈和队列的应用
栈的应用
括号匹配
表达式求值
中缀转后缀
后缀表达式求值
递归栈
队列的应用
树的层次遍历
数据缓冲区
数组
一维数组
行优先
列优先
多维数组
特殊矩阵的压缩存储
对称矩阵
三角矩阵
三对角矩阵
第四章串
模式匹配算法
暴力匹配算法
KMP算法
KMP进一步优化
第八章排序
内部排序
插入排序
直接插入排序
折半插入排序稳定
希尔排序
交换排序
冒泡排序稳定
快速排序
选择排序
简单选择排序
堆排序
归并排序
基数排序
外部排序
多路归并排序
收藏
0 条评论
下一页
