数据结构思维导图
数据结构知识总结
树图思维导图提供 数据结构 在线思维导图免费制作，点击“编辑”按钮，可对 数据结构 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：1b7b151819ba98030681e15967ca6810
思维导图大纲
数据结构思维导图模板大纲
1 绪论
数据结构（三要素）
逻辑结构
线性结构
线性表、队列、栈
非线性结构
集合、树、图
物理结构（存储结构）
顺序存储、索引存储、散列存储
数据的运算
2 线性表
顺序表示
顺序表
链式表示
单链表
双链表
循环链表
静态链表
数组
3 栈和队列
栈
顺序栈
链栈
共享栈
队列
循环队列
删除元素，队首指针+1
Q·front=（Q·front+1）%MaxSize
插入元素，队尾指针+1
出队入队都按顺时针进1
（rear-front+MaxSize）%MaxSize
链式队列
双端队列
矩阵的压缩存储
压缩存储
指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间
特殊矩阵
对称矩阵
三角矩阵
三对角矩阵
各矩阵的下标
稀疏矩阵
4 串
概念
主串
字串
串长
存储结构
模式匹配算法
暴力
O(nm)
KMP算法
O(n +m)
掌握KMP算法的滑动
前缀匹配，next数组
KMP算了进一步优化
5 树与二叉树
二叉树
概念
度为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
哈夫曼编码
没有一个编码是另一个编码的前缀
树和森林
概念
操作
与二叉树的互换
遍历
应用：并查集
6 图
概念
简单图
完全图
连通图
任意两个顶点都是连通的，即有路径存在即可，不一定是直接相连的边
边数小于n-1必是非连通图
连通分量
无向图中的极大连通子图称为连通分量
强连通图
对于有向图，两顶点之间互相有路径到彼此
图的结构的存储
邻接矩阵
邻接表
十字链表
多重链表
图的遍历
深度优先遍历
先序遍历
广度优先遍历
深层遍历
图的应用
最小生成树
Prim
选择距离最近的顶点连起来
时间复杂度O(V²)
Kruskal
按权值递增的顺序选择合适的边
最短路径
Dijkstra
单源最短路径
每一轮加入一个路径最短的结点
Floyd
从原始邻接矩阵改
时间复杂度O(V³)
拓扑排序
AOV网
关键路径
AOE网
ve()事件(顶点)最早发生时间
Max
vl()事件最晚发生时间
Min
e(i)活动(边)最早开始时间
等于该狐起点的ve
v()最晚开始时间
终点的vl-持续时间
7 查找
概念
静态查找
动态查找
线性结构
顺序查找
无序线性表
查找成功，平均查找长度: (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的质数
平均查找长度
成功
分母是元素个数
失败
待查找数字肯定不在表中
长度为关键字距离第一个空地址的距离，分母是散列函数的除数
效率指标
散列函数
装填因子
处理冲突的的方法
8 排序
概念
稳定性
衡量标准：时间、空间复杂度
内部排序
插入排序
直接插入排序
最坏比较次数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为根的子树进行筛选 ②输出堆顶元素，将堆的最后一个元素放在堆顶，向下筛选
归并排序
基数排序
从个十百千…依次分配、收集
外部排序
归并排序
外部排序经常采用
败者树
置换-选择排序
在工作区中所有记录中选取比MINIMAX记录的关键字大的记录中选取最小的关键字替换MINIMAX，直到选不出时，结束作为一个归并段，再重新开始…
最佳归并树
哈夫曼树的思想
当初始归并段不足以构成一个严格k叉树时，需添加长度为0的“虚段”
（n0-1）%（k-1）=0时，可以构成k叉树
（n0-1）%（k-1）=u时，说明有u个多余，要加上k-u-1个虚段
沪公网安备 31011502019485号
上海工商