图
图基本概念
注意：
线性表可以是空表，树可以是空树，但图不可以是空，即v一定是非空集
无向图、有向图
简单图、多重图
简单图
多重图
顶点的度、入度、出度
无向图：顶点v的度是指依附于改顶点的边的条数，极左TD(v)
有向图：
入读是以顶点v为终点的有向边的数目，记为ID(v)
出度是以顶点v为起点的有向边的数目，记为OD(v)
顶点的度等于入度和出度之和，TD(v)=ID(v)+OD(v)
顶点-顶点的关系描述
路径：顶点v1到顶点v2之间的一条路径
回路：第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路:除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度:路径上边的数目
点到点的距离:从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的
几 ...
排序
第八章 排序基本概念和排序方法排序的基本概念
排序：从大到小或从小到大排序
排序的稳定性：
稳定的：关键字相同的元素在排序之后相对位置不变
不稳定：相反
排序算法的分类：
内部排序：待排序记录全部放在计算机内存中*(关注算法时间、空间复杂度)*
外部排序：数据过大，以至于内存中不能容纳全部的数据，在排序过程中，尚需对外存进行访问排序*(还要关注读取/写磁盘的次数更少)*
插入排序算法思想︰每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。
直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入已经排好序的表，从而得到一条新的、记录数量增1的有序表
算法描述：
算法分析：
时间复杂度：
最好的情况：比较次数n-1次
最坏的情况：$$O(n^2)$$
平均时间复杂度：$$O(n^2)$$
空间复杂度：$$O(1)$$
折半插入排序
时间复杂度依然是$O(n^2)$
注意：一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将 ...
线性表
线性表线性表的顺序表示和实现
初始化
步骤：
为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址
将表的当前长度设为0
代码：
1234567891011//初始化const int MAXSIZE = 100;bool InitList(SqList L){ L.elem = new ElemType[MAXSIZE]; if(!L.elem){ return 0; } L.length = 0; return true;}
取值
步骤:
判断指定的位置序号i的值是否合理$$（1<=i<=L.length）$$，若不合理，返回false
若值合理，则将第i个数据元素L.elem[i-1]赋值参数e，通过e返回第i个数据元素的传值
123456789//取值int GetElem(SqList L,int i,ElemType e){ if(i<1 || i>L.length){ return -1; } e=L.elem[i-1]; ...
树
树二叉树
节点的内部结构
平衡二叉树
规则：任意节点左右子树不超过一
平衡二叉树的旋转机制
左旋
右旋
红黑树
红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构。
1972年出现，当时被称之为平衡二叉B树。后来，1978年被修改为如今的"红黑树"。
它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，
每一个节点可以是红或者黑;红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的
红黑规则
每一个节点或是红色的，或者是黑色的
根节点必须是黑色
如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的
如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点;
红黑树添加节点的规则：
添加节点默认是红色(效率高)
更多内容请见 :point_right:链接