数据结构思维导图
数据结构相关内容讲解
树图思维导图提供 数据结构 在线思维导图免费制作，点击“编辑”按钮，可对 数据结构 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：fa03df23eacf92340315ff3179ec9add
思维导图大纲
数据结构思维导图模板大纲
1 树与二叉树
二叉树
概念
度为2的树和二叉树的区别
度为2的树至少有3个结点，而二叉树为空
度为2的有序树若只有一个孩子就无须确定左右次序。二叉树无论孩子是否为2都要确定次序
树的性质
树中的节点数等于所有结点的度数加1（结点数等于边数加1
度为m的树中第i层上至多有m^(i-1)个结点
高度为h的m叉树至多有(m^-1)/(m-1)个结点
具有n 个结点的m叉树的最小高度为┎log m (n (m - 1)+1)┒
操作
遍历
线索化二叉树
应用
排序二叉树
平衡二叉树
插入
找离插入点最近的平衡因子＞1的结点
四种旋转
查找
比较次数最多是树的深度
深度为h 的平衡二叉树含有的最少结点: nʰ=n⁽ʰ⁻¹⁾+nʰ⁻²+1 ，n0=0, n1=1, n2=2
非叶子结点的平衡因子均为1
哈夫曼树
从结点中选取最小的两个结点构造树，轮流...
n 个结点能构造出n-1 个结点，所以哈夫曼树结点总数为2n-1
哈夫曼编码
没有一个编码是另一个编码的前缀
树和森林
概念
操作
与二叉树的互换
遍历
应用：并查集
2 图
概念
简单图
完全图
连通图
任意两个顶点都是连通的，即有路径存在即可，不一定是直接相连的边
边数小于n-1必是非连通图
连通分量
无向图中的极大连通子图称为连通分量
强连通图
对于有向图，两顶点之间互相有路径到彼此
图的结构的存储
邻接矩阵
邻接表
邻接矩阵
十字链表
多重链表
图的遍历
深度优先遍历
先序遍历
广度优先遍历
深层遍历
图的应用
最小生成树
Prim
选择距离最近的顶点连起来
时间复杂度O(V²)
Kruskal
按权值递增的顺序选择合适的边
最短路径
Dijkstra
单源最短路径
每一轮加入一个路径最短的结点
Floyd
从原始邻接矩阵改
时间复杂度O(V³)
拓扑排序
AOV网
关键路径
AOE网
ve()事件(顶点)最早发生时间
Max
vl()事件最晚发生时间
Min
e(i)活动(边)最早开始时间
等于该狐起点的ve
v()最晚开始时间
终点的vl-持续时间
3 查找
概念
静态查找
动态查找
线性结构
顺序查找
无序线性表
查找成功，平均查找长度: (n+1)/2
不成功，n+1
有序线性表
成功，(n+1)/2
不成功，n/2+n/(n+1)
折半查找
适用于有序的顺序表
结合判定树（查找过程的二叉树）
比较次数不会超过树的高度
n个非叶子结点，n+1个叶子结点（失败结点）
查找成功平均查找长度：（1x1+2x2+3x2²+…+hx2⁽ʰ⁻¹⁾）/n =log（n+1）-1
分块查找
树形结构
二叉排序树
二叉平衡树
B树(不支持顺序查找)
m阶树至多有m-1个关键词，至少有「m/2 」-1个关键词
插入
删除
兄弟够借，父子换位
兄弟不够，父子合并(若父结点只有一个关键词，合并后无父结点，要重新调整)
B+树
m阶树至多有m-1个关键词，至少有「m/2 」个关键词
散列结构
散列表
处理冲突的方法
开放定址法
线性探测法
平方探测
避免出现堆积
再散列法
拉链法（不会聚集）
散列函数
除留余数法
H（key）=key%p p取不大于表长m最接近m的质数
平均查找长度
成功
分母是元素个数
失败
待查找数字肯定不在表中
长度为关键字距离第一个空地址的距离，分母是散列函数的除数
效率指标
散列函数
装填因子
处理冲突的的方法
查找
查找
线性查找
定义：顺序查找
适用数据量较小的数据集
二分查找
定义：折半查找
适用数据已排序的数据集
斐波那契查找
mid=low+F[k-1]-1
哈希查找
定义：通过哈希函数将关键字映射到索引位置进行查找
适用数据量大、频繁查找且已分布有序的数据集
哈希表处理冲突
开放地址
线性探测
二次探测
算法：H(key)=a*key+b
除留余数法
H(key)=key%p
查找算法比较
时间复杂度：线性查找最低，二分查找最优
适用场景：根据数据特点选择合适的查找算法
查找优化方法
建立索引：对关键字段建立哈希索引等
数据预处理：对数据进行清洗、排序等操作
使用高级语言特性：如Python中的dict等数据结构，提高查找效率
4 排序
概念
稳定性
衡量标准：时间、空间复杂度
内部排序
插入排序
直接插入排序
最坏比较次数n（n-1）/2
折半插入排序
希尔排序
步长d=n/2,
交换排序
冒泡排序
最坏比较次数n（n-1）/2，移动次数3n（n-1）/2
快速排序
选择排序
简单选择排序
比较次数与初始状态无关，始终是（n-1）n/2次
堆排序
定义：大根堆：L（i）≥L(2i)且L(i)≥L(2i+1)
①建堆：从┗n/2┛~1为根的子树进行筛选 ②输出堆顶元素，将堆的最后一个元素放在堆顶，向下筛选
基数排序
从个十百千…依次分配、收集
外部排序
败者树
归并排序
归并排序和基数排序
归并排序
思想
归并
把两个或多个有序子序列合并为1个
k路归并
k合一
每选出一个元素需要对比关键字k - 1次
n个元素下归并趟数⌈logn⌉（以k为底），这里同样是树高，却是向上取整，因为这里的n是叶子数不是树的总结点数！
实现过程
其实是一棵倒立的二叉树
代码
也要会背，尤其会归并
算法思想
low < high，将序列从中间mid = （low + high）/ 2分开
对左半部分[low,mid]递归归并排序，右半部分[mid+1，high]递归，将左右两个子表Merge成一个
性能
空间复杂度
O(n)，来自辅助数组
时间复杂度
O(nlogn)，每趟归并O(n)，归并趟数O(logn)
算法排序码比较次数和元素移动次数为right - left + 1
稳定
常常用于文件排序
归并问题
两个有序序列各有M、N个元素，比较次数为
最少：min（M,N）次
其中一个序列全小于另一个序列
最多：M+N-1次
两个表的指针交替动
时间复杂度O(m + n)，也可为O(max(m,n))，因为2max(m,n)≥m + n
二路归并排序递归算法采取策略：分治
归并排序适合并行处理
基数排序
思想
将整个关键字分为d位，作d次“排序码”的比较
按关键字位“权重递增”（也称LSD，如“个十百”）次序，做d趟“分配”与“收集”
若当前处理关键字位可能取r个值，需建立r个队列
分配：顺序扫描根元素，根据当前处理的关键字位，拆相应队列，一趟O(n)
收集：各队列中结点一次出队并链接，一趟O(r)
举例说明
第一趟，基于个位“分配”；最终收集结果：438->888->168->007->666->996->985->233->211->111->520
性能
空间复杂度
O(r)，r个辅助队列
时间复杂度
O(d(n+r))，一趟分配O(n)，一趟收集O(r)，总共d趟分配收集
稳定
最大最重要特点：
不基于比较和移动进行排序
擅长处理
关键字可以拆分为d组，且d较小
每组关键字取值范围不大，即r较小
元素个数n较大
类基数排序
LSD：权重递减；MSD：权重递增
如果要求有两个数据项m和n，先看m，m小的元素在前，大的在后；在m相同的情况下，再看n，n小的在前，大的在后
可以类比LSD，此时m的权重 ＞ n的权重
因此：先排n，后排m，并且为了不破坏“m相同看n”，后排m的算法要稳定！
置换-选择排序
在工作区中所有记录中选取比MINIMAX记录的关键字大的记录中选取最小的关键字替换MINIMAX，直到选不出时，结束作为一个归并段，再重新开始…
最佳归并树
哈夫曼树的思想
当初始归并段不足以构成一个严格k叉树时，需添加长度为0的“虚段”
（n0-1）%（k-1）=0时，可以构成k叉树
（n0-1）%（k-1）=u时，说明有u个多余，要加上k-u-1个虚段
补充
排序算法的补充
算法复杂度与初始状态无关
简单选择排序
堆排序
归并排序
基数排序
元素总比较次数与初始状态无关
简单选择排序
基数排序
折半插入排序
元素总移动次数与初始状态无关
归并排序
基数排序
排序趟数与初始状态有关
冒泡排序
快速排序
精检排序
一堆数字不进行两次及以上的比较
直接插入排序
折半插入排序
归并排序
不稳定排序的反例
无论是快排、简单选择、堆、希尔，都可以用
【2，2，1】
各算法比较
希尔排序时间复杂度无视
计数排序
思想
计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。
计数排序要求输入的数据必须是有确定范围的整数。
用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），然后进行分配、收集处理
实现逻辑
① 找出待排序的数组中最大和最小的元素 ② 统计数组中每个值为i的元素出现的次数，存入数组C的第i项 ③ 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） ④ 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
例如
性能
n是0~k的整数
空间复杂度
O(k)
时间复杂度
O(n + k)
稳定
不基于比较的排序
桶排序
思想
将数组分到有限数量的桶里。每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。
例如
看看得了
性能
空间复杂度
O(n+k)
时间复杂度
最好O(n + k)
最坏O(n ^ 2)
平均O(n + k)
稳定
不基于比较
补充
初态反序，直插、冒泡、简选哪个更好？
简选，rmn最小
n个不同元素集合，同时找最大最小元素至少比较多少次？
第一次先取2个元素，大放max，小放min
第2次及以后，取元素先比max再比min，至少n-1次比较
分配排序
最低位优先更简单
最高位优先每轮额外一个数组或递归，继承高位排序结果
归并排序和快速排序用分治法
相关思维导图模板
树图思维导图提供 title: kafka数据推送 v1.0.0language 在线思维导图免费制作，点击“编辑”按钮，可对 title: kafka数据推送 v1.0.0language 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：e227e2455f4e33e3156c12d50fd1169a
树图思维导图提供 数据结构思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 数据结构思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：0598dd6b08bb23f28d61260daf7d4fee
沪公网安备 31011502019485号
上海工商