导图社区 数据结构思维导图
数据结构思维导图，包括算法性能分析、线性结构复习、二叉树基础、二叉树的链式存储、二叉树的遍历等等。
全国大学英语六级笔试每年开考两次，分别于6月和12月举行，具体考试时间全国大学英语四、六级考试中心将会在每年年初另行通知。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
数据结构
绪论
什么是数据？
字符
声音
图像
.......
主要关注内容
存储方式
关系描述方式
操作方式的集合
数据结构的类型
数据逻辑结构
线性结构
顺序表
链表
队列
栈
非线性结构
二叉树
堆
树
图
散列表
数据物理结构
顺序存储结构
链式存储结构
其他复杂结构
什么是算法？
能够使计算机编程实现
相同的输入对应相同的输出
能够在有限步内结束
算法性能分析
衡量算法性能
基本运算次数
算法性能比较
空间复杂度
固定部分
变动部分
线性结构复习
二叉树基础
二叉树的定义
二叉树的基本术语
二叉树的五种基本形态
二叉树的性质
二叉树的分类
满二叉树
完美二叉树
时间复杂度
顺序存储的二叉树、堆
二叉树的顺序存储结构
小根堆
小根堆是一种按照层次顺序存储的完全二叉树，其每一个节点的键值都不大于其左右孩子的键值。
大根堆
大根堆是一种按照层次顺序存储的完全二叉树，其每一个节点的键值都不小于其左右孩子的键值。
堆的主要操作
查询堆顶元素
插入一个元素
删除堆顶元素
堆排序
对于小根堆，堆顶元素一定为最小元素 若先将待排序序列建立小根堆 再依次将元素从堆中取出，得到的新序列一定是从小到大有序的。 此方案需要开辟两片内存空间，一片存储小根堆，另一片存储结果序列。
将数列元素组成大根堆。 将数组首元素与尾元素调换，同时将数组元素个数减1。 将缩小的数组重新调整为大根堆。 重复步骤2、3，直到数组中数据元素为0。
二叉树的链式存储
二叉树的链式存储结构
使用结构体存储每个节点，使用两个指针域分别指向两个孩子。
二叉树节点结构定义
二叉树层次遍历输出
算法1:出队列后访问 建立队列，将根节点指针加入队列。 若队列不为空，则从队列中删除一个节点指针。然后访问该节点，并将该节点的左右孩子依次存入队列。 重复步骤2直至队列为空。
算法2:入队列前访问 建立队列，访问根节点，将根节点指针加入队列。 若队列不为空，则从队列中删除一个节点指针。若该节点有左孩子，则访问其左孩子节点并将该左孩子节点入队列；若该节点有右孩子，则访问其右孩子节点，并将该右孩子节点加入队列。 重复步骤2直至队列为空。
顺序存储转链式存储代码
垂直输出二叉树
垂直打印二叉树示例
二叉树的遍历
层次遍历
前序遍历
访问根节点 前序遍历左子树 前序遍历右子树
中序遍历
中序遍历左子树 访问根节点 中序遍历右子树
后序遍历
后序遍历左子树 后序遍历右子树 访问根节点
二叉树的遍历的应用
前序遍历的应用
快速排序
求幂集
中序遍历的应用
汉诺塔
后序遍历的应用
求二叉树的深度
算法：
求左子树的深度
求右子树的深度
该二叉树的深度为左右子树深度较大者加1
哈夫曼编码
树的基本概念与存储
树的定义
树是一个含有(≥0个)节点的集合。
若=0，其为空树。
若>0，则有一个节点称为根节点（root）。其余节点分为多个互不相交的子集合。
这些子集本身也是树，称为根的子树。
树的遍历
树的广度优先遍历
将根节点入队列 当队列不为空时 出队列，并访问该节点 依次将该节点的孩子节点入队列
深度优先遍历算法思想
将根节点入栈 当队列不为空时 出栈，并访问该节点 依次将该节点的孩子节点入栈
树的后根遍历
依次以后根遍历方式访问该节点的各个子树。 访问根节点。
八皇后
图的基本概念
图的定义
图（graph）是一个n个顶点（vertex）的集合，每个顶点可以有多个前驱和后继。
无向图
如果一个图中顶点的前驱和后继关系没有区别，这个图就称为无向图
有向图
如果一个图中顶点的前驱和后继关系有区别，这个图就称为有向图 有向图中的一对顶点构成的前驱后继关系称为有序对、有向边（edge）或弧（arc
顶点与边的关系
若两个顶点构成边，则称这两个顶点互为邻接，称这条边与这两个顶点相关联。 构成有向边的前驱和后继顶点分别称为这条有向边的起点与终点。
权
若给每一条边赋上一个有意义的数值，这个数值称为权（weight），这样的图称为加权图（weighted graph）
度
在无向图中，与一顶点相关联的边的个数称为该顶点的度。 在有向图中，以一顶点为终点的边的数量称为该顶点的入度；以一顶点为起点的边的数量称为该顶点的出度。
路径
图中的某个顶点序列，在序列中前后相邻的两个顶点是边的起点和终点，则称该序列为一条路径（path）。 序列的首尾顶点称为路径的起点与终点。 序列包含的边数称为路径的长度。 不少于三个顶点的路径，若起点终点相同，称为回路（cycle）或环 路径中除起点终点外，没有相同的顶点，称为简单路径。 起点终点相同的简单路径称为简单回路。
连通性
若两个顶点之间存在路径，则称这两个顶点是连通的（connected） 若任意两个顶点都是连通的，则称此图是连通图（connected graph）
强连通性与弱连通性
有向图中 若任意两点之间，至少存在以一个顶点为起点的路径，称此图为弱连通图（week connected digraph） 若任意两点之间，以每一个顶点为起点都存在路径，称此图为强连通图（strong connected digraph）
图的存储
邻接矩阵
能够快速查询两顶点是否邻接。 查询某顶点的所有邻接点相对较慢。 当图较为稀疏时，占用空间较大。
邻接表
当图为稀疏图时，空间占用小。 查询某顶点的所有邻接点速度快。 当图为稠密图时，查询两点是否为邻接点速度慢。
图的遍历
广度优先遍历
初始化访问标志数组，全部为0
把起点插入到队列，标记“已访问”
如果队列不为空：
从队列中取出一个顶点访问
如果邻接点没有“被访问”，插入队列，并标记“已访问”
深度优先遍历
访问节点
依次以未访问节点为起点，进行深度优先遍历
最短路径
单源最短路径
给定一个有向网络和一个称为源点的顶点，源点到其他各个顶点的最短路径，称为单源最短路径。
迪杰斯特拉算法
目前为止最为有效的最短路径求解算法
可以针对带权无向图或有向图进行求解
限制：不能有负权边
最小生成树
生成树
对于一个无向图G，其生成树T为G的一个连通子图，且T包含G中所有顶点，有n-1条边。（n为顶点个数）
普里姆算法Prim
在候选边集中选择一条权值最小的边，把它加入到入选子图
更新候选边集
重复步骤2直到入选子图包含原图所有顶点
克鲁斯卡尔算法
拓扑序列
顶点活动网 AOV
用顶点表示活动，用有向边表示活动的先后顺序。这样的有向图称为顶点活动网（AOV网 activity on vertex network）。
将AOV网中的顶点排成一个序列，使得对其中任意两个顶点 vi 和 vj ，若 vi 是 vj 的前驱，则 vi 在序列中一定处于 vj 的前面。我们称这样的序列为拓扑序列
寻找拓扑序列的算法
建立一个整数数组，记录每一个顶点的入度。建立队列，把入度为0的顶点入队列。
若队列不为空，从中取出一个顶点作为拓扑序列中的顶点。
将以该顶点为起点的边的终点入度减1。若减1后入度为0，则将该点插入到队列。
重复步骤2、3直至队列为空。
若结果序列中顶点个数等于图中顶点的个数，则算法成功。
关键路径
边活动网 AOE
对于一个带权有向图，它的边表示某活动，权表示该活动持续的时间，顶点表示其入边活动均已完成和出边活动可以开始的事件。这个带权有向图称为边活动网（AOE网）
从源点到汇点的最长带权路径称为关键路径
关键路径上的活动称为关键活动
不在关键路径上的活动称为非关键活动
事件最早发生时间
对于某事件，其最早发生时间是以其顶点为起点的活动最早开始的时间。
是从源点到该顶点的最长带权路径长度。
事件最迟发生时间
对于某事件，其最迟发生时间是以其顶点为终点的所有活动的最晚结束时间。
是汇点最早发生时间减去从该顶点到汇点的最长带权路径长度。
活动时延
对于任意一个活动（边），其终点事件的最迟发生时间减去其起点的最早发生时间是这个活动最长可以持续的时间。
某活动最长可持续时间减去这个活动边的权，就是这个活动允许的时延。
源点事件的最早和最迟发生时间一样，都是0
汇点事件的最早和最迟发生时间也一样，都是关键路径的长度
迷宫求解
二叉搜索树
查找的相关概念
查找
设数据集合之中有n个数据元素，ki为数据元素Ri的关键字，现给定关键字k, 将寻找相应数据元素R的过程称为查找。
查找表
以查找操作为主的数据对象。一般是线性表。
关键字
能够唯一标识数据元素的数据项。
查找的分类
静态查找和动态查找
根据查找的过程中是否修改查找表，将查找分为静态查找和动态查找。
内查找和外查找
根据查找的过程中是否有内外存的交互，将查找分为内查找和外查找。
查找的结果
查找成功
给出整个数据元素，或给出该数据元素的位置
查找失败
返回空指针或其他预定的值
主要查找方法
平衡二叉搜索树
如果某个二叉树的每一个节点都处于平衡状态，那么称这个二叉树是平衡二叉树。
B树
B树 B-tree
B树是一种能够自我调整平衡状态的树状数据结构
支持快速查找、遍历、插入和删除操作
B树更适合于存储系统的大规模数据读写操作。
常用于数据库和文件系统
几个重要概念
数据对象或数据元素：数据表中的一条记录
关键码：用于区分对象的属性
索引项：一个对象的关键码和该对象在数据表中的地址组成的数据对象称为索引项
索引表：由索引项组成的数据表称为索引表
散列
开放地址法
线性探测法
平方探测法
双散列函数探测法
SetMap
集合与字典
集合 std::set，std::unordered_set
set容器中元素始终以自身为依据保持一个恒定的顺序，用户不能改变这个顺序
set容器中不能同时存在多个值相同的元素
set容器自行管理内存占用，无需用户干预
set容器中只能存放const元素
set容器通常用二叉搜索树实现
字典 std::map, std::unordered_map
unordered_map容器与unordered_ set容器类似，存储关键词与其对应的值。即其内部元素为（关键词，值）的二元组
只能通过关键码，而非存储位置访问容器中的元素
map容器中元素根据其关键码的散列函数值确定存储位置
元素的值可以与它的关键码不同
容器中不能同时存在多个关键码相同的元素
容器自行管理内存占用，无需用户干预
容器中只能存放const关键码
容器通常用散列表实现
与unordered_set相同，使用自定义类型关键码时需要制定该自定义类型的散列函数和等价判定函数
