导图社区 数据结构与算法
数据结构与算法 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。
操作系统是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。
计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
算法与数据结构
线性表
链式线性表有头节点(标兵)
第一个节点是phead->next或head.next
栈
递归程序非递归实现不一定需要栈
可以用DP的思想
图
图的顶点集非空,因此没有空图
连通分量
极大连通子图
回路就是环
环一定不是简单路径
简单回路除端点外,中间节点不重复
简单路径的顶点不重复
邻接矩阵
一般主对角线上元素为0
不联通为无穷大
关键路径
最早开始时间ve()
最晚开始时间vl()
活动最早开始时间e()
源点的最早开始时间
活动最晚开始时间l()
汇点的最晚开始时间减去活动时间
活动时间余量d()
表示该活动的时间余量,余量为0的活动在关键路径上
缩短所有关键路径的公共边才能缩短工期
延长任一关键边就能延长工期
KMP
部分匹配表
子串所有前缀的公共前后缀长度组成的表
next[]
nextval[]
排序
希尔排序
一种插入排序
逐渐缩小增量,组内使用直接插入排序
外部排序
多路平衡归并
每趟处理后段数变为celing(m/k)，k是路数
查找
平均查找长度
二分查找
画出搜索树
又称二叉判定树
失败节点的父节点的平均高度
成功就是算平均深度
Hash表查找
树
B树与B+树
B树
m阶B树的定义
每个节点至多m棵子树,m-1个关键字
非空B树根节点至少2棵子树
非根节点至少ceiling(m/2)棵子树
3,4-2
5-3
叶结点是查找失败的节点(实际不存在)
终端结点指最底层的结点
又称B-树
每个元素仅出现一次
数据在B树节点内部
任意节点关键字恒有左右孩子
任意关键字的前驱/后继恒在最低层
插入时分裂
中间元素升高,递归分裂
分裂后, 左侧的节点恒是满的
4阶B树节点分裂为2,1,1
删除时合并
总能转化成从底部开始的合并
够借就从兄弟处借
不够借就父关键字下降,终端点合并
不够借就一定能合并
阶为奇,合并后有m-1个关键字
阶为偶,合并后有m-2个关键字
注意偶数阶B树合并后的节点是非满的
向根部合并
B+树
m阶B+树定义
同样最多m棵子树,最少ceiling(m/2)棵子树
但是关键字是对应孩子节点最大关键字
因此也是m个
叶结点有指向记录的指针
叶节点水平链接,以便于遍历查找
注意B+树的叶结点与B树叶结点的区别
最小生成树
当各边权重互不相同时,最小生成树唯一
从不同顶点出发使用Prim算法构造的生成树不一定相同
同一幅图的最小生成树边权值序列相同
堆
建堆
数组遍历由后往前
AVL树
删除再插入
如果删除的节点是非叶节点，重新插入后树可能相同
