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