导图社区 数据结构
包含最新考研408数据结构全部知识点及附件中代码，包括绪论、线性表、栈、数组和队列、串、树和二叉树、图、查找等内容，图片均为手绘可通过平板修改。
根据田静老师《句句真言》总结的考研长难句和基础语法，可作为快速查询语法和断开长难句速查手册，包括简单句、长难句、长难句分析等内容。
覆盖考研会考的高等数学和初等数学大部分考点、知识点、公式证明及其知识点联系，包括函数极限连续、连接导数值与函数值、函数的微分学、连接积分与导数等内容。
覆盖考研线性代数全部考点、公式及其重要公式推导。可用于总结考研线性代数知识点间联系也可作为公式手册。
社区模板帮助中心，点此进入>>
论语孔子简单思维导图
《傅雷家书》思维导图
《童年》读书笔记
《茶馆》思维导图
《朝花夕拾》篇目思维导图
《昆虫记》思维导图
《安徒生童话》思维导图
《鲁滨逊漂流记》读书笔记
《这样读书就够了》读书笔记
妈妈必读：一张0-1岁孩子认知发展的精确时间表
数据结构
考试要求
应用题
代码题
顺序表问题
暴力解法
快速排序
枚举所有
潜在优化
折半查找
有序数组
指针后移
简单动态规划
空间换时间，空间保存中间状态
贪心算法
局部最优到全局最优
单链表
枚举
用数据保存
优化方向
利用链表性质
前后指针
前后指针的距离是一样的
找到倒数第k个
快慢指针
如果有环，快指针早晚追上慢指针
头插法
逆置
类似数组指针后移
条件：多个、线性表、有序
原理：归并排序
以空间换时间
树
考察结构
记忆模板，按题目要求修改
重点考察遍历
二叉树
先序
中序
后序
递归
层序
树和森林
先根
后根
非重点
二叉排序树
平衡二叉树
红黑树
判断是否是XX树
考试形式和试卷结构
一、试卷满分及考试时间
本试卷满分为 150 分、考试时间为 180 分钟
二、答题方式
答题方式为闭卷、笔试
三、试卷内容结构
数据结构 45 分
11道小题22分，2道大题23分
计算机组成原理 45 分
操作系统 35 分
10道小题20分，2道大题15分
计算机网络 25 分
8道小题16分，1道大题9分
四、试卷题型结构
单项选择题（共80分，40小题，每小题2分）
综合应用题（共70分）
第一章：绪论
数据结构三要素
逻辑结构
存储结构
数据的运算
算法效率的度量
时间复杂度
只关注循环/递归部分
空间复杂度
第二章：线性表
代码
顺序表
//静态分配 typedef struct{ ElemType data[MaxSize]; int length;//当前顺序表中有多少个元素 }SqList;
//动态分配 typedef struct{ ElemType *data; int capacity;//动态数组的最大容量 int length; }SeqList;
链表
typedef struct LNode{ ElemType data; struct LNode *next;//指向下一个结点 }LNode,*LinkList;
双向链表
typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode,*DLinkList;
第三章：栈、数组和队列
栈
typedef struct{ ElemType data[MaxSize]; int top; }SqStack;
队列
循环队列
typedef struct{ ElemType data[MaxSize];//存储MaxSize-1个元素 int front,rear;//队列头 队列尾 }SqQueue;
队头指针只有出队的时候改变
链式存储
typedef struct LinkNode{ ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ LinkNode *front,*rear;//链表头 链表尾 }LinkQueue;//先进先出
存储方式
斐波那契数列
中缀表达式转后缀表达式
1. 遇到操作数。直接加入后缀表达式。
2. 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符加入到后缀表达式，直到弹出“(”为止。 注意：“（”不加入后缀表达式。
3. 遇到运算符。①依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，直到碰到“（”、栈空、运算符优先级低于当前运算符。②把当前运算符入栈。
4. 按照上述方法处理完所有字符后，将剩下的运算符依次弹出，加入后缀表达式。
后缀表达式的运算
1| 从左往右扫描下一个元素，直到处理完所有元素。
2| 若扫描到操作数则压入栈，则回到①；否则执行③
3| 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
矩阵存储特殊
行优先上三角 (存放对称矩阵) a₁₂＝a₂₁
行优先三对角矩阵
第四章：串
KMP
不考大题
next数组
第1个值根据编号而改变
第五章：树和二叉树
层次建树、遍历
typedef struct BiTNode{ BiElemType data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree;
建树
前中后序遍历
时间复杂度：O(n) 空间复杂度：O(n)
层序遍历
后序遍历可以查找根节点到子孙节点的路径：通过栈回溯栈
非递归中序遍历
while(p||!StackEmpty(S)){ if(p){//当一个结点不为空，压栈，并取左孩子 Push(S,p); p=p->lchild; }else{//弹出栈中元素并打印，获取打印元素的右孩子 Pop(S,p);putchar(p->c);//当p指针为空时出栈 p=p->rchild; } }
可得知前序序列为入栈顺序，中序序列为出栈顺序
二叉排序树（二叉查找树）
大题概率低
双亲表示法 孩子表示法 孩子兄弟表示法
树、森林和二叉树
森林 树 二叉树 前 前 前 中 后 中
并查集
改进
小树合并大树
压缩路径
每次查找完以后，再将路径上的所有节点压缩到根节点上
性质
节点总数=总度数＋1
一个入度代表一个节点，加上根节点没有入度
度为m的树，m叉树的区别
度为m:真实存在
m叉树:定义但可以不存在
满二叉树
完全二叉树
完全二叉树最多只有一个度为1的节点
线索二叉树
线索二叉树找前驱和后继
前驱
✓
后继
×
线索标志
rtag＝1
无右孩子
rtag＝0
有右孩子
通过遍历序列构造二叉树(唯一确定)
前序＋中序
前序找根，中序分块
后序＋中序
后序找根，中续分块
层序＋中序
做题技巧
给定前序、后序序列判断其他性质
①前序定根节点，将序列看作根左右 ②后续定根节点，将序列看作左右根 ③将根左右和左右根对比解题
哈夫曼树
带权路径长度最短
带权路径长度：到每个叶结点的带权路径长度之和
解题技巧
将题目中抽象的树画成一个直观的树，如：上层单叉树，用最底层来符合条件
第六章：图
存储结构 (画图)
邻接表
创建
深度优先遍历
深度优先生成树
广度优先遍历
形成广度优先生成树
结构体
// 邻接表中表对应的链表的顶点 typedef struct _ENode{ int ivex; // 该边所指向的顶点的位置,是数组的下标 struct _ENode *next_edge; // 指向下一条弧的指针 }ENode, *PENode;
// 邻接表中表的顶点 typedef struct _VNode{ char data; // 顶点信息 ENode *first_edge; // 指向第一条依附该顶点的弧 }VNode;
// 邻接表 typedef struct _LGraph{ int vexnum; // 图的顶点的数目 int edgnum; // 图的边的数目 VNode vexs[MAX]; }LGraph;
邻接矩阵
有向图按照拓扑排序序列组织矩阵为1的点只在上三角
其他存储方法，考研概率几乎为0
概念
简单图
1. 不存在重复边
2. 不存在顶点到自身的边(自己和自己连接)
完全图
任意两个顶点之间都存在边
n(n-1)/2
子图
图的一部分
连通、连通图和连通分量
无向图
连通
顶点V到顶点W有路径存在
连通图
图中任意两点之间都是连通的
最少有n-1条边
非连通图最多有 C₂(n-1)条边
连通分量
无向图中的极大连通子图称为连通分量(边和点都是极大)
强连通图、强连通分量
有向图
强连通图
任意两个顶点之间都有路径
最少有n条边
强连通分量
有向图中极大连通子图，称为有向图的强连通分量
度
有向图、无向图
入度和出度之和，也就是边的二倍
无向图性质：
简单路径
点到点的路径系列中，每个点都不重复出现的路径(包括顶点)
简单回路
点到点的路径系列中，除第1个和最后一个外，其余点都不重复出现
最小生成树
Prim
Kruskal
用到并查集
最短路径
单源路径
BFS(无权图)
广度优先遍历生成树
DIjkstra(带权图、无权图)
final
标记各顶点是否找到最短路径
dist
最短路径长度
path
路径上的前驱
步骤
初始化final出发点最短路径长度为0。final全为false
1、找到final[]＝＝false的点中，dist最小的点P，将其final设为true
2、以P点为中介，T为所有P可以到达的且final[T]＝＝false的点 if( (dist[P]＋P→T)＜dist[T] ){ //P→T表示P到T的代价 dist[T]＝dist[P]＋P→T; path[T]＝P; }
各顶点的最短路径
Floyd(带权图、无权图)
有向无环图
拓扑排序
正拓扑的逆序列为逆拓扑
DFS深度优先便利出栈顺序即为逆拓扑序列
每次取出入度为零的点
邻接矩阵：O(|V|^2)
邻接表：O(|V|＋|E|)
关键路径
从源点到终点，具有最大路径长度的路径叫做关键路径
事件v_k最早发生时间ve(k)
决定所有从v_k开始的活动能够开工的最早时间
事件v_k最迟发生时间vl(k)
不推迟整个工程完成的前提下，该事件最迟必须发生的时间
活动a_i的最早开始时间e(i)
该活动弧的起点所表示的时间的最早发生时间
活动a_i最迟开始时间l(i)
该活动弧的终点所表示事件的最迟发生时间与该活动所需时间差
该活动a_i的时间余量d(i)＝l(i)-e(i)
d(i)＝0的活动为关键活动
表示在不增加完成整个工程所需总时间的情况下，活动a_l可以拖延的时间
第七章：查找
顺序查找/折半查找
顺序查找
平均查找长度
∑(查找长度×查找概率)
判定树一定是平衡二叉树
判定树(取整方向决定左右子树的节点差) mid向下取整：左子树-右子树＝0或-1 mid向上取整：左子树-右子树＝0或1
散列/哈希查找
解决冲突
拉链法
开放定址法
H_i＝(H(key)＋d_i)%m
第一次试探就是用d_0带入
线性探测法
d_i＝0，1，2，3...m-1
平方探测法
d_i＝0，1，-1，4，-4，9，-9...
伪随机序列法
d_i＝自定义
删除节点只能用逻辑上的删除，防止查找函数中断
散列函数
除留余数法H(key)＝key%p
p为质数
直接定址法(a×key＋d)
数字分析法
装填因子α＝表中记录数/散列表长度
分块查找
块内无序，块间有序
二叉排序树(删除操作)
左子树上所有节点的关键字均小于根节点的关键字
右子树上所有节点的关键字均大于根结点的关键字
判断查找路径序列是否正确
若a＞b,则a＞{S} a,b,{S} 若a＜b,则a＜{S}
只有一个孩子的直接用孩子代替
调整最小不平衡子树A
第一个左子树与右子树高度差绝对值为2的子树
CD变换： C：取决于A的儿子 D：取决于A儿子的儿子
LL
在A的左孩子的左子树插入导致不平衡
RR
在A的右孩子的右子树插入导致不平衡
LR
在A的左孩子的右子树插入导致不平衡
RL
在A的右孩子的左子树插入导致不平衡
删除操作步骤
1、删除节点(任意)
2、找到第一个不平衡子树
3、找到最小不平衡子树下，最高的儿子、孙子
4、根据孙子在LL/RR/LR/RL，进行旋转
最大高度递推公式
N_h ＝ N_(h-1) ＋ N_(h-2) ＋ 1 总结点数＝右子树节点＋左子树节点＋根节点
n_0＝0，n_1＝1，n_2＝2，n_3＝4 N_h表示高度为H的平衡二叉树的最少节点
插入
新节点是根
染成黑色
新节点非根
染成红色
插入新节点依然满足红黑数定义，则插入结束
黑叔
旋转＋染色(交换的颜色取反)
右单旋，父换爷＋染色
左单旋，父换爷＋染色
左、右双旋，儿换爷＋染色
RL
右、左双旋，儿换爷＋染色
红叔
染色＋变新
叔父爷染色，爷变为新节点
左子树节点值≤根结点值≤子树节点值
根节点和叶节点均是黑色
不存在两个相邻的红节点（红节点的父节点和孩子节点均是黑色）
对于每个节点，从该节点到任一叶节点NULL的简单路径上，黑节点数目相同
左右根，根叶黑 不红红，黑路同
从根节点到叶节点的最长路径不大于最短路径的两倍
B树
任何一个节点，所有子树高度都要相同
若根节点不是终端节点，则至少有两棵子树
所有叶子节点都出现在同一层
关键字的值：子树0＜关键字1＜子树1＜关键字2＜子树3＜...
非叶节点N个关键字的B树必有N＋1个叶子节点（ N个关键字将数域切分为N＋1个区间） 叶结点总数＝非叶节点关键字个数＋1（第n层的叶节点数＝1至(n-1)层关键字总个数＋1）
最小高度
最少关键字
根节点一个关键字+其他节点*最少关键字数
新元素一定要插入到最底层“终端节点”，用“查找”来确定插入位置
插入后导致原节点关键字超过上限，则从中间位置↑[m/2]↑将其关键字分为两部分
导致父节点超过，继续向上分裂
删除
删除终端节点
删除后关键字≥↑[m/2]↑-1
直接删除即可
删除后关键字＜↑[m/2]↑-1
2、左右兄弟都不够借时（关键字＝↑[m/2]↑-1）
“我＝兄＋父＋我”合并
1、左右兄弟其一很富裕时（关键字＞↑[m/2]↑-1）
“兄父我”进行左轮换或右轮换
删除非终端节点
用直接前驱或直接后继来替代被删除的关键字
直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
直接后继：当前关键字右侧指针所指子树中“最左下”的元素
B＋树
由分块查找进化得来
只有最下层节点才包含记录信息
分支节点都是索引，为了节省内存
分支节点中只包含各个子节点中关键字的最大值
节点的子数个数＝关键字个数
第八章：排序
交换类
冒泡排序
最坏=[n+(n-1)+……+1]=n^2
最好=O(1)
空间复杂度=O(1)
稳定
flag标记当前趟是否发生交换，若没说明已经有序，不需要再继续执行
会考大题
最好=O(n*log2n)
平均
最坏=O(n^2)
空间复杂度=O(log2n)
不稳定
插入类
插入排序
最坏=（1+2+……+n）=O(n^2)
最好=O(n)
初始默认第1个元素有序
折半查找+插入排序
考的少（性能差）
前半段有序序列采用折半查找，只是将插入排序的查找部分用折半查找换为顺序查找，并不会改变元素移动次数
希尔排序(内部为插入排序)
不考大题，最多选择题（性能不好）
选择类
选择排序
不考大题（简单）
时间复杂度=O(n^2)
每次找出最小的元素与i交换，后i＋＋
堆排序
时间复杂度=O(nlog2n)
父(↓[i/2]↓)＞左(2i)、右孩子(2i＋1)
编号≤N/2的节点依次“下坠调整”（自底向上处理各分支节点）
不上升
调整规则：小元素逐层“下坠”（与关键字更大的孩子交换）
排序
1、将堆顶元素加入有序子序列（堆顶元素与堆底未排序元素交换）
2、堆底元素换到堆顶后，从根节点开始“下坠调整”，恢复“大根堆”的特性
注：“下坠调整”有传递性，被调整的点要继续下坠至不能下坠
堆的插入和删除
堆的插入
新元素放在（堆底）
根据大/小根堆的要求，新元素不断上升，直到无法继续上升为止
堆的删除
被删除元素，用表尾（堆底）元素替代
根据大/小根堆的要求，替代元素不断“下坠”，至无法继续下坠为止
关键字对比次数
每次“上升”调整只需对比关键字一次
每次“下坠”调整分别和子节点比较(1或2次)
归并类
归并排序
不用大题 (归并思想)
空间复杂度=O(n)
基数排序
r(10)为基数
d(3)为关键字位数
权重从小到大
外部排序
对r个初始归并段，做k路归并，则归并数可以用k叉树表示，若树高为h，则归并趟数＝h-1＝↑[log_k(r)]↑
读取磁盘次数＝趟数×初始归并段
败者树
分支节点(灰色)
记录失败者来自哪个归并段
根结点(蓝色)
记录冠军来自哪个归并段
置换选择排序(构造初始归并段)
最佳归并树
