导图社区 数据结构思维导图
这是一篇关于数据结构的思维导图，储存在某种介质上能够识别的物理符号，是信息的载体，这些符号可以是数字、符 或其他，
这是一篇关于货币金融复习的思维导图，包含利率结构、商业银行、货币供给、货币政策与传导机制等。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
数据结构
绪论
数据
定义
储存在某种介质上能够识别的物理符号，是信息的载体，这些符号可以是数字、符或其他
构成：
数据元素
数据项
构成数据的最小单位
数据的基本单位
逻辑结构
数据元素之间的关系
集合结构
属于同一个集合
线性结构
一对一
线性表、堆、栈
树形结构
一对多
图状结构
多对多
存储结构
顺序存储结构
链式存储结构
索引存储结构
散列存储结构
算法
为解决某一特定问题的具体步骤的描述，是指令的有限序列
五大基本性质
有穷性
必须在执行有限步骤后结束
确定性
可行性
任何计算步骤都可被分解为基本的可执行的操作步骤，每个步骤都可在有限时间内完成
输入
一个算法可以有0个或多个输入
输出
一个算法有1个或多个输出
设计的一般规则
正确性
可读性
健壮性
面对错误输入应当做出恰当反应
高效率和低存储量
复杂度
线性表
时间复杂度
顺序表按值查找
n+1/2
顺序表插入
O（n）
删除
栈
后进先出
栈顶
操作端
栈底
固定端
顺序栈
top=-1为空栈
top=MAXSIZE-1为满栈
栈的链式存储
类似单链表
队列
先进先出
队尾
允许插入
队头
允许删除
顺序队列
循环队列
留下一个空间不使用
判满
(rear+1)%MAXQUEUE==front
front==rear
判空
链表
不带头结点的单链表
涉及头结点的操作都需要特别处理
带头节点的单链表
头指针不空
循环单链表
最后一个节点的指针域存放第一个节点的地址，形成一个环
操作中的中止操作判断是否为头指针
双向链表
有前驱，有后继
数组
存储地址的计算
基地址+(i+1)*n+(j-1)
查找方法
顺序查找
遍历
平均查找长度=n+1/2
索引查找
建立索引项
关键字项
分块
指针项
平均查找长度=（n/s + s）/2 +1
n为表长，均匀分为b块，每块含有s个记录
哈希查找
哈希函数构造方法
直接哈希函数
取关键字本身或者关键字某个线性函数作为地址
地址集合大小==关键字集合大小
数字分析哈希函数
平方取中
折叠法
移位折叠
边界折叠
除留取余
H=key mod p
取素数
随机数法
哈希查找性能分析
因素
哈希函数
基本不考虑
冲突处理方法
开放地址法
线性探测再散列
1，2，3，。。后延
（1 + 1/1-α ）/2
二次探测再散列
正负数平方 后延
ln(1-α)/α
伪随机探测再散列
伪随机序列
再哈希法
链地址法
发生冲突的记录存储在同一个线性链表中
1+ α/2
公共溢出区
另设一个向量为溢出表
哈希表的装填因子
α=表中填入的记录数/哈希表长度
哈希表平均查找长度是α的函数，不是n的函数
前提：数据装填均匀
排序
稳定排序
排序前后关键字数据相对位置不变
直接插入
分成两部分，左侧有序，右侧无序，右侧第一个元素进入左侧合适位置
O（平方）
稳定
希尔排序
按照固定间隔，相隔为d的分成同一组，在同一组内使用插入或者二分排序
第一次完成，减小间隔分组，再排序
直到间隔为1
不稳定
冒泡排序
从左向右依次比较到n-i+1个
平方/2
简单选择
从无序序列取出最大添加到有序序列尾部
平方
基数排序
多关键字排序
多关键字有序
高位优先
低位优先
快速排序
将数列划分为两部分（要求保证相对大小关系）
递归到两个子序列中分别进行快速排序
不用合并，因为此时数列已经完全有序
nlogn
但是当序列本身有序时，退化为平方
归并排序
将待排序的序列分为若干个子序列，每个子序列是一个有序的序列。然后再将有序子序列合并为整体有序序列
树（Tree）是n（n>=0）个结点的有限集。当n=0时，称为空树。在任意一棵非空的树中，有且仅有一个特定的称为根（Root）的结点。当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。
树具有以下特性：
1. 子树是不相交的。
2. 除根节点外，每个节点有且仅有一个父节点。
3. 一个N个节点的树有N-1条边。
树的度是指树的所有结点中最大的度数，而叶结点是指度为0的结点。树的深度是指树中所有结点中的最大层次。在二叉树的第i层上至多有2^(i-1)个结点（i≥1），深度为k的二叉树至多有2^k-1个结点（k≥1）。
递归与分治
递归
直接或间接调用本身
使用场景
定义是递归的
n的阶乘，斐波那契数列
数据结构是递归的
分治
分而治之
规模小时，容易解决
问题可以分解为类型相同的子问题，具有最优子结构
子问题合并可以获得原问题的解
子问题之间独立
算法时间复杂度
迭代法
直接展开
递归树法
主方法
树
二叉树
概念
度
结点拥有的子树数量
叶子
度为0的结点
孩子
结点子树的根
双亲
孩子结点的上层结点
祖先
从根节点到该结点所经分支上所有结点
结点的层次
从根节点起，根为第一层
二叉树的度
最大结点度数
二叉树深度
结点的最大层数
特殊
满二叉树
所有分支结点都有左子树和右子树
所有叶子所有叶子结点都在同一层
完全二叉树
除最后一层外，每一层都被完全填充的二叉树。最后一层的结点连续集中在最左边。
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
性质
1. 在非空二叉树中，第i层的结点总数不超过i>=1。
2. 深度为h的二叉树最多有2^h - 1个结点(h>=1)，最少有h个结点。
3. 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。
4. 具有n个结点的完全二叉树的深度为 logn + 1
二叉树的遍历是指按照某种规则访问二叉树的每个结点，使得每个结点被访问且仅被访问一次。二叉树的遍历主要有三种方式：前序遍历、中序遍历和后序遍历。
1. 前序遍历（Preorder Traversal）：
* 访问根节点
* 前序遍历左子树
* 前序遍历右子树
2. 中序遍历（Inorder Traversal）：
* 中序遍历左子树
* 中序遍历右子树
3. 后序遍历（Postorder Traversal）：
* 后序遍历左子树
* 后序遍历右子树
遍历应用
由先序遍历和中序遍历序列建立二叉树
先序和后序不能建立二叉树
求二叉树深度
以下是一个使用递归方式求二叉树深度的伪代码示例：
```
function treeDepth(root):
if root is null:
return 0
else:
leftDepth = treeDepth(root.left)
rightDepth = treeDepth(root.right)
return max(leftDepth, rightDepth) + 1
在这个伪代码中，`root` 表示二叉树的根节点。如果根节点为空，返回深度为0；否则，递归计算左子树和右子树的深度，取两者中的较大值加1作为当前子树的深度，并返回最大深度作为结果。
二叉排序树
插入
平衡二叉树
每个结点左右子树深度之差不超过1
二叉排序树转化为平衡二叉树
左单旋转RR
在结点的右孩子的右子树上插入结点
右单旋转LL
在结点的左孩子的左子树上插入结点
先左后右双向旋转LR
在结点的左孩子的右子树上插入结点
先右后左双向旋转RL
在结点的右孩子的左子树上插入结点
最优二叉树（哈夫曼树）
带权路径长度最短的二叉树
哈夫曼树构造
根节点根节点中挑选权值最小组合生成一个新根
哈夫曼编码
左0右1
树到二叉树的转换
加线
兄弟结点用线相连
去线
保留双亲和最左边孩子连线，去掉其他
堆
1. 最大堆：每个节点都大于或等于其子节点的堆称为最大堆。
2. 最小堆：每个节点都小于或等于其子节点的堆称为最小堆。
堆的插入
图
完全图
对有n个顶点的有向图
边的数量n(n-1)
有向完全图
边的数量n(n-1)/2
无向完全图
基本概念
入度
出度
边数==度数之和/2
路径
简单路径
通过任意顶点不超过一次
路径长度是它包含的边的数目
环（回路）
连通图
强连通图
有向图中任意两个顶点之间都存在路径
强连通分量
顺序储存结构
邻接矩阵
关联矩阵
链式储存结构
邻接表
逆邻接表
十字链表
Tialvex
Headvex
Hlink
Tlink
邻接多重表
无向图
Ivertex
Ilink
Jvertex
Jlink
深度优先
广度优先
生成树
特点
一个有n个顶点的完全图一共存在n(n-2)种不同的生成树
最小生成树
普里姆算法
选边
为已知的连通分量选最小的新边
克鲁斯卡尔算法
按边的权值选边
某条边形成回路，就舍弃他
贪心算法
带权最短路径
迪杰斯特拉算法
分为两个点集
已经求出最短路径
未确定
拓扑排序
必定无环
关键路径
路径上的点最早开始时间==最晚开始时间
动态规划
