Think like A Computer

数据结构强化课资料索引 （王道团队官方发布）

2021 王道考研 数据结构+习题讲解

王道考研数据结构代码总结

24考研计算机王道408数据结构考点精讲含课件（完整版）

北京邮电大学人工智能学院北邮809数据结构考研真题答案详解网学天地考研

🔺做题 tips：
代码题：
写完代码一定读一遍，看看有无语法错误等
复习代码题时，要熟知代码逻辑，以及临界点 / 判断条件，一定要记住条件是什么，灵活应对
做代码题时，先自己写一个例子放在旁边，手动实现一遍，然后结合储存的数据结构，对照着还原代码

基本代码题汇总

线性表
KMP

树
二叉树创建递归非递归
二叉树前序中序后序，递归非递归
二叉树层序
二叉树结点总数、深度、叶子结点总数
（哈夫曼树构造、编解码）
算数表达式二叉树
二叉树的复制
二叉树路径显示
交换二叉树所有结点的左右子树

图
DFS、BFS
Prim、克鲁斯卡尔
dijkstra、Floyd

查找
二叉排序树插入、构建、删除

排序所有

肖波 PPT

ch1
p18 带哨兵的顺序查找，从后往前遍历，遍历到第一个哨兵跳出循环

绪论

数据结构：按照某种逻辑关系组织在一起的数据，按一定储存方式储存在计算机存储器中，并在这些数据上定义了一组运算的集合
数据结构包括：
逻辑结构（集合、线性结构、树结构、图结构）
物理结构、存储结构（顺序存储、链式存储）
对数的操作和运算

算法：解题方法。从计算机角度看：若干条指令组成的有穷序列
算法特性：
输入、输出、有穷性、可行性、确定性

好的算法还应具备：
健壮性/鲁棒性、高效性、可读性

注意，写代码一定要考虑健壮性，考虑到不成立的情况

时间复杂度计算
本质思想：代码执行趟数之和
计算思路：

1. 看被迭代的语句的表达式，等差/等比/递增
2. 用 k 代表一次迭代，用 k 列出等差等比求和表达式/第 k 次变量的值
3. k 等于边界条件，比如 n/二分之n 等
4. 解出用 n 表示 k 的表达式，即为复杂度

对于多层循环，列出每一次外层循环，内层循环的执行次数，直至第 k 次，然后进行计算

详解时间复杂度计算公式(附例题细致讲解过程)

空间复杂度的四种计算情况，超级简单好懂

真题分析：
书上画的，课后题填空背会即可
基本复杂度计算，没有偏难怪

线性表

顺序表
表长为 n 的顺序表插入时移动元素的个数（可操作范围：1~n+1） p27
在最后一个位置（n+1）：0
在第一个位置（1）：n
在中间第 i 个位置：n-i+1

平均移动的元素个数：n/2

表长为 n 的顺序表删除时移动元素的个数（可操作范围：1~n）
最后一个位置（n）：0
第一个位置（1）：n-1
中间第 i 个位置：n-i

平均移动的元素个数：(n-1)/2

平均删除、插入长度记忆：可操作范围删除比插入少1，所以分母-1

查找
从 1 开始到 n，对查找次数求和，共 (n×(1+n))/2
除以总共 n 个元素，得到平均查找长度 (1+n)/2

分析平均移动次数/平均查找长度时，先求对第 i 个元素操作时的执行次数（可以带几个值验证），然后看操作的范围，是 1~n 还是 1~n+1。然后进行求和，再除以元素个数，得到平均值

真题分析：

1. 插入删除的复杂度分析过程，平均移动次数、概率
2. 插入删除的逻辑，代码

线性表 p17 第三题
第五题和第三题思路一样，就是限定不同。
第四题注意是有序的顺序表
第六题，学会双指针如何移动，在同一个列表上操作。
第七题，在函数外部定义新表，一起传入函数。综合6、7题，学会使用 data[i++] 这种表述控制指针是否在本次循环移动。
第九题：顺序表最快查找算法为二分查找（折半查找）
【二分查找】详细图解
第十一题，每次循环次数减少的算法复杂度为 O(log2n)，比 O(n) 强，优先考虑。
十二题，学会计数器的使用。有时候计数器并不实际代表某个数值，单纯为了计数用。

线性表常考操作：
顺序逆转
前后调换

链表
头插法：注意从列表的尾部遍历到头部，保持有序性
尾插法：比头插法多一个尾指针 rear，一直指向链表尾部
方便插入和删除数据，使用双链表
删除一个单链表中的结点至少需要两个指针

C++实现单链表

p51 综合应用题

1. 递归步骤：找出重复的步骤，将其归纳到一个函数操作中；找到第一种情况，单独列出来；描述后续步骤，用上面的函数代替期中的几步；注意判断不同情况时，函数输入的不同值。
2. 解释了递归的本质，递归和栈的关系，先入后出，逆序输出

数据结构与算法基础--第05周11--3.4栈和递归

调用原函数可看做函数进栈；当满足跳出递归条件时，开始输出结果，从最后进栈的函数开始向下执行；输出结果的过程为出栈。

4. 第四题，用指针代替了传统的寻找最小值的方式，只不过删除一个结点需要两个指针。两个指针共同控制过一个最小值。

链表常考操作：
用指针找到最大最小值；删除结点；去重；链表归并

顺序表和链表比较
表长可以预估、查询（搜索）操作较多 ——使用顺序表
表长难以预估，经常需要增加/删除元素 ——使用链表
插入删除主要发生在表头表尾——使用循环链表

线性表顺序存储：随机存取；链式存储：顺序存取

存储密度：结点中数据所占空间 / 结点结构所占储存空间

栈和队列

栈的主观感受：后进先出，LIFO；用于暂存一些数据，等待某一符合条件的时刻弹出；

栈一般都是处理栈顶 / 出栈的元素

串

KMP算法
子串匹配算法

next数组：
长度和串的长度一样，从0到n，next[0] 不存数据；每一个位置 i 代表，当第 i 位未匹配成功时，子串指针 j 要重新指向串的位置。

手动求 next数组：next[1] = 0，next[2] = 1 无脑写

nextval数组：
nextval[1]无脑写0

树

数据结构-满k叉树例题

二叉树的前序遍历、中序遍历、后序遍历、层序遍历的时间复杂度和空间复杂度

手动求线索二叉树的方法：

1. 写出遍历序列
2. 找到不满的结点（带有空指针的）
3. 在序列中找到其前后结点，分别连接
4. 如果结点在序列头/尾，且有一侧为空，则指向 NULL

树的存储
树和二叉树的相互转化：
二叉树转化为树：
“左孩子右兄弟”
在结点左侧的为孩子结点，右侧的为兄弟结点，依次展开即可

树转化为二叉树：
本质是用二叉链表存储树。从根节点出发，把结点的孩子写在左孩子，结点的兄弟写在右孩子

二叉树和森林的相互转化：
森林转化为二叉树：
把每棵树先转化为二叉树，然后用右孩子连接每棵树的根节点

二叉树转化为森林：
从根节点出发，把所有右孩子拿下来，作为拆分出来的树的根节点；按照二叉树转化为树的方法分别转化。

树和森林的遍历
树的先根遍历 <=> 对二叉树的先序遍历
树的后根遍历 <=> 对二叉树的中序遍历

森林的先序遍历 <=> 对二叉树的先序遍历 <=> 依次对各个树先根遍历
森林的中序遍历 <=> 对二叉树的中序遍历 <=> 依次对各个树后根遍历

哈夫曼树
哈夫曼树不唯一
哈夫曼树是二叉树，但不是完全二叉树和满二叉树
哈夫曼树的叶子结点是数据结点，非叶子结点都是权值结点
哈夫曼树的总结点数是2n-1（n是叶子节点数）
哈夫曼树只有度为0和2的结点，没有度为1的结点

图

《数据结构》-第六章 图(习题)
无向图边集为圆括号：{(v1,v2),(v3,v4)}
有向图边集为尖括号：{<v1,v2>,<v3,v4>}

一个无向图有 n 个顶点和 n-1 个边，可以使它连通，即生成树（生成树一定有且仅有 n-1 条边）；
若再加一条边即 n 条边，则必形成环（回路）

强连通图是有向图，指有向图中任意一对顶点都存在路径
n 个顶点的强连通图，至少有 n 条弧（有向边），即连通之后还得形成环

n 个顶点的完全无向图，有 n(n-1)/2 条边 ①
n 个顶点的完全有向图，有 n(n-1) 条弧 ②

①：对于一个顶点，和其它 n-1 个顶点分别有一条边，n 个顶点，则为 n(n-1) 条，又因为每个点的边互相重复，所以除以二；
②：有向图允许两个顶点有两条边，所以为 二倍的 ①

度 = 入度 + 出度

无向图全部顶点度的和等于边数的二倍

连通分量是极大连通子图，包含所有点和边
生成树是极小连通子图，包含所有点和相连的 n-1 条边

回路起始点和终止点一样，路径所有点都不一样；
简单路径：所有点都不重复；简单回路：除了起始点和终止点其余点都不重复

邻接矩阵
数据结构之图(二)——邻接矩阵
无向图

1. 无向图的邻接矩阵是对称的（边数 = 1 的个数 / 2），且主对角线元素全为0（无回路）
2. 顶点 i 的度 = 第 i 行（列）中 1 的个数。
3. 完全图的邻接矩阵中，主对角元素为 0，其余全为 1
4. 带权有向图中 0 和 ∞ 表示的都不是有向边

有向图
边数 = 1 的个数
第i行的含义：以结点 vi 为尾的弧(出度边)；
第i列的含义：以结点 vi 为头的弧(入度边)；
顶点的出度=第i行元素之和；
顶点的入度=第i列元素之和；
顶点的度=第i行元素之和+第i列元素之和。

邻接表
数据结构之图(三)——邻接表
无向图

1. 边数 = 边结点的个数 / 2
2. 邻接表不唯一
3. 若无向图中有 n 个顶点、e 条边，则其邻接表需要 n 个头结点和 2e 个表结点。适宜存储稀疏图
4. 无向图中顶点 vi 的度等于第 i 个单链表中的结点数

​有向图

1. 边数 = 边结点的个数
2. 顶点 vi 的出度为第 i 个单链表中的结点个数
3. 顶点 vi 的入度为整个单链表中邻接点域值是 i-1 的结点个数
4. 找出度易，找入度难

邻接矩阵多用于稠密图；而邻接表多用于稀疏图

数据结构|十字链表|简单粗暴零失误画出十字链表

1. 先画出邻接表（邻接表表示尾指向头）
2. 再分割出弧结点的指针域
3. 最后自己指向自己

邻接多重表进阶版画法 三步秒杀 数据结构

DFS
结合北邮书 180 页，c 代码学习
🔺基本思想：沿着一个节点一直走到不能走为止，再出栈找到可以继续走的地方，重复上述
🔺掌握：

1. 在图上直观描述
2. 使用栈描述的递归方式
3. 使用邻接表的代码实现（顶点节点、弧结点、边和弧的构成、实现逻辑）
4. 使用邻接矩阵的代码实现

🔺注意：

1. 进栈即输出节点值，输出节点值即进栈；即第一层递归时就输出结点值
2. 使用邻接表表示图时，用一个邻接数组 adjlist 代表图
3. 只有在输出的时候用到结点名称，其余时间都用从 0 开始的下标表示结点，便于输入数组
4. 无论是顶点节点还是弧结点，都只有指向弧结点的指针

🔺代码实现的 tips：
· 邻接表
先深刻理解邻接表的结构：数据结构之图(三)——邻接表
点节点的 data 域（北邮代码中叫 vertex）保存节点的名称信息，firstarc / firstedge 指向弧节点类型的数据，指向该节点的第一条弧结点；弧结点保存邻接点的序号，还有指向下一个弧结点的指针

· 邻接矩阵
从第 i 个节点开始遍历，打印编号对应的节点值，并记录已访问，找到邻接矩阵第 i 行，邻接矩阵的第 i 行表示和第 i 个节点相邻的元素。
遍历到第一个 1 为止，若未访问，则打印节点，递归遍历对应序号的行，直到行结束

BFS
🔺基本思想：访问一个节点的所有未被访问的相邻节点，然后再从相邻节点中拿出一个重复上述
🔺掌握：

1. 在图上直观描述
2. 使用队列描述
3. 使用邻接表的代码实现（顶点节点、弧结点、边和弧的构成、实现逻辑）
4. 使用邻接矩阵的代码实现

🔺注意：

1. 第一个顶点先处理，单独入队
2. 入队即输出顶点值
3. 出队后对该顶点进行操作
4. 队列空则遍历结束
5. queue[++r] / queue[++f] 先自增一位再输入/输出，下标从 1 开始

最小生成树
🔺生成树的性质

1. 对于包含 n 个顶点的无向完全图最多包含 n^(n-2) 颗生成树。
2. 一个 n 个顶点的连通图的所有生成树都包含 n 个顶点和 n-1 条边
3. 移除生成树中的任意一条边都会导致图的不连通， 生成树的边最少特性
4. 生成树中不存在环；在生成树中添加一条边会构成环

边的权值之和最小的生成树——最小生成树

最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示

Prim(普里姆)
北邮书 186 页，以邻接矩阵为例
集合 U：已落在生成树上的点，用数组 adjvex[MAXSIZE] 表示
集合 V-U：未落在树上的点，不用表示
lowcost[] 数组：保存 U 到 V-U 最小权值的边

🔺注意

1. 分析此算法时需要将 图（看邻接点）数组 结合着一起看
2. lowcost[i]=0 表示该顶点已经选择（和自己的距离为 0）；lowcost[j]=-1 表示从 i 到 j 没有直接连接的边
3. adjvex 的本质保存的是生成树中边的信息。理解：结合北邮书 188 页，adjvex 数组的序号和元素值分别代表两个顶点，一个数组位代表两个顶点间的一条边

🔺步骤：

1. 写出三行的列表，第一行是顶点名称，第二行是 adjvex，第三行是 lowcost
2. 初始化数组， adjvex 行全填 0，lowcost 行全填 -1
3. 第一次初始化，选定一个节点 i，更新该节点的 lowcost[i]=0，更新该点到其邻接点的 lowcost，非邻接点不用管，还是 -1
4. 找到 lowcost 中的最小值，将该位置 lowcost 改为 0，代表已被选
5. 同时将与该点邻接的点的 adjvex 数组值都改为当前节点下标，代表和该点相连的边，并更新其 lowcost 中的权值
6. 重复步骤 4，若其邻接点满足：（1. 未被选择 2. 到当前节点的权值比已有权值小）则执行步骤 5

Kruskal(克鲁斯卡尔)
很全：克鲁斯卡尔算法(Kruskal算法)求最小生成树
使用边集数组存储边
边集数组的结构：

struct VEdge{
    int fromV;  // 起始顶点
    int endV;  // 终止顶点
    int weight;  // 边的权值
}
VEdge EdgeList[MAX_EDGE];

🔺步骤

1. 准备一个辅助数组，下标代表不同点，用于判断是否产生回路。原理是记录是否在同一集合（有相同标记），初始化为不同标记
2. 准备一个新的空边集数组储存结果
3. 对边按权值进行排序（起泡排序等）得到一个排好序的 EdgeList
4. 遍历 EdgeList，判断其两个顶点标记是否相同。若相同，则会产生回路，不选择此边；若不同，则选择此边，并将顶点标记改成相同的
5. 当新边集数组中有 n-1 条边时，结束遍历

最短路径算法
Dijkstra 算法
【全网第二清晰】手写迪杰斯特拉-Dijkstra（考试用）
注意，迪杰斯特拉算法是找一个点到所有其他顶点的最短路径算法，是点和点之间，两点之间的算法

🔺感性把握：
从起始点开始，每一次寻找离前一个点权值最小的点，连接两点，并在后一个点上标记当前累加的权值。寻找后一个点时，把已经选择的点看作一个集合，找整体到后一个点的权值最小的路径。一次选择是一次执行过程

🔺准备以下数组：
dist[i]：源点到顶点 i 的距离（单次来看，指前一个点到该点的距离，是累加得到的结果）
path[i]：源点到顶点 i 的路径（单次来看，指前一个点到该点的路径，也就是该点的前一个结点）
s[i]：记录是否找到源点到顶点 i 的最短路径

最后得到的 dist 数组包含源点到所有点的最短路径
path 数组：设起始点为 u，要找的点为 v，找到 v 对应的 path 值 a，再找到 a 对应的 path 值 b，以此类推，最终找到 u，则 u 到 v 的路径为 u→....b→a→v

🔺步骤

1. 检查距离起点的邻接点，写入 dist 和 path
2. 选择 dist 最小的点 v，在 s 中标记已选择
3. 检查 v 的邻接点的权值，若比 dist 中的值小，则写入 dist 和 path（累加）
4. 重复 2、3，直到全选完

代码思路和直观思路有些不一样

Floyd 算法
求最短路径Floyd算法！
求图中任意两个顶点之间的最短路径，最后得到的 dist 矩阵，第 i 行 j 列表示 从 i 到 j 的最短距离

辅助数组
dist
path

查找

折半查找
终止条件：找到匹配元素 或 low>high

二分查找
求具体 ASL 时，需要画出查找树来看，第一层查找一次，第二层查找两次，第 n 层查找 n 次；求和除以待查元素个数。（注意查找树最后一层优先有右子树）
画查找树时，优先选择靠近左侧的结点（因为计算机自动向下取整）

平均成功 ASL：⌊log2n⌋ + 1

平衡二叉树
高度（深度）为 k 的平衡二叉树的结点数：习题解答 P100
平衡因子 =左子树深度-右子树深度

散列表
键值(key)的解释：哈希表的知识讲解
哈希函数根据键值计算出一个存储地址，从而将键值对应的数据存储在地址中
哈希表中的冲突指的是，不同键值的元素对应于相同的存储地址

线性探测法：没特殊规定的情况下，对谁取余，表长就是谁；对自己取余等于 0

平方探测法

#排序
算法可视化平台

今年题目预测

选择
多维数组，三维数组的存储
朴素模式匹配、KMP
图的概念

简答
线性表语句分析

稀疏矩阵，三元组表，十字链表

二叉树遍历、转化森林
手算哈夫曼
构造平衡二叉树
B-树的插入删除

图十字链表、临界多重表的构造
图着色、关键路径、拓扑排序
手算 BFS\DFS，手算最小生成树，手算dijkstra

哈希（链地址法）

一趟排序
手算大根堆

程序
（KMP）

二叉树创建递归非递归
二叉树前序（中序）后序，递归非递归
二叉树层序
二叉树结点总数、深度、叶子结点总数
（哈夫曼树构造、编解码）
（算数表达式二叉树）
二叉树的复制
（二叉树路径显示）
交换二叉树所有结点的左右子树

邻接表（矩阵）DFS
图的最小生成树算法 Prim、克鲁斯卡尔
最短路径 Floyd

二叉排序树插入、构建、删除

排序，除堆排序、计数排序、直接插入