《数据结构》读书笔记
2021-07-21 18:56:21 0 举报AI智能生成
考研408计算机综合数据结构部分知识框架、思维导图
作者其他创作
大纲/内容
第1章 绪论
1.1 数据结构的基本概念
1.2 算法和算法评价
第2章 线性表
2.1 线性表的定义和基本操作
2.2 线性表的顺序表示
2.3 线性表的链式表示
第3章 栈和队列
3.1 栈(Stack)
特性：LIFO(Last In First Out)
入栈和出栈顺序相反
入栈和出栈顺序相反
存储结构
链式存储
链栈
所有操作都在单链表表头执行
便于多个栈共享存储空间提高效率
不存在栈满上溢的情况
顺数存储
顺序栈(top指向栈顶元素)
进栈操作：
S.data[++S.top]=x;
S.data[++S.top]=x;
出栈操作：
x=S.data[S.top--];
x=S.data[S.top--];
判断栈空条件：
S.top==-1
S.top==-1
共享栈
定义：两个顺序栈共享一个一维数组空间，将两个栈的栈底
分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸
优点：
节省存储空间，降低上溢风险
节省存储空间，降低上溢风险
判断栈满条件：
相关考点
出栈序列
判断合法的出栈顺序
n个不同元素的出栈序列个数：
卡特兰数(Catalan数)
卡特兰数(Catalan数)
穷举法
上溢：栈顶指针超出了最大范围
因为栈的增删都是在栈顶进行的
因为栈的增删都是在栈顶进行的
C语言标识符：
只能以字母、下划线开头，不能以数字开头
只能以字母、下划线开头，不能以数字开头
栈的应用
括号匹配
表达式求值
前缀表达式(波兰表达式)：+ab
中缀表达式(普通表达式)：a+b
后缀表达式(逆波兰表达式)：ab+
“左右先”原则
习题1
习题2
中缀表达式转后缀表达式(机算)
机算步骤/算法：
1.操作数，直接加入后缀表达式
2.界限符，'('直接入栈，')'则依次弹出栈元素直到弹出'('
3.运算符，依次弹出栈内优先级≥当前运算符的元素并加入后缀表达式，
直到'('或栈空。之后再入栈当前运算符
1.操作数，直接加入后缀表达式
2.界限符，'('直接入栈，')'则依次弹出栈元素直到弹出'('
3.运算符，依次弹出栈内优先级≥当前运算符的元素并加入后缀表达式，
直到'('或栈空。之后再入栈当前运算符
递归
递归工作栈
工作原理：
每进入一层递归，就将递归调用所需的信息(返回点、局部变量、传入实参)压入栈顶
每退出一层递归，就从栈顶弹出相应信息
每进入一层递归，就将递归调用所需的信息(返回点、局部变量、传入实参)压入栈顶
每退出一层递归，就从栈顶弹出相应信息
缺点：多层递归可能导致栈溢出
递归算法：斐波那契数列
进制转换、迷宫求解等
3.2 队列(Queue)
特性：FIFO(First In First Out)
入队和出队顺序一致
入队和出队顺序一致
存储结构
顺序存储(循环队列)
入队操作：(确定maxSize!!!)
rear=(rear+1)%maxSize;
A[rear]=x;
rear=(rear+1)%maxSize;
A[rear]=x;
出队操作：
队列长度(size/length)：
=(rear-front+maxSize)%maxSize
=(rear-front+maxSize)%maxSize
判断队满条件：
1.(Q.rear+1)%MaxSize==Q.front
2.size==MaxSize(size记录队列长度)
3.front==rear&&tag==1(tag记录最后一次操作类型)
1.(Q.rear+1)%MaxSize==Q.front
2.size==MaxSize(size记录队列长度)
3.front==rear&&tag==1(tag记录最后一次操作类型)
判断队空条件：
1.Q.rear==Q.front
2.size=0(size记录队列长度)
3.front==rear&&tag==0(最后执行了删除操作)
1.Q.rear==Q.front
2.size=0(size记录队列长度)
3.front==rear&&tag==0(最后执行了删除操作)
链式存储
带头结点
判断队空条件：
1.Q.front->next==null
2.Q.front==Q.rear
1.Q.front->next==null
2.Q.front==Q.rear
不带头结点
判断队空条件：
1.Q.front==null
2.Q.rear==null
1.Q.front==null
2.Q.rear==null
双端队列
定义：允许两端进行增删的队列
变种
输入受限的双端队列
输出受限的双端队列
考点：对输出序列合法性的判断
队列的应用
树的层次遍历
图的广度优先遍历
操作系统中的应用
就绪队列
解决多用户的资源竞争问题
解决多用户的资源竞争问题
缓冲区
解决主机与外部设备间速度不匹配问题
解决主机与外部设备间速度不匹配问题
3.3 栈和队列的应用
3.4 特殊矩阵的压缩存储
对称矩阵
策略：只存储主对角线+下三角区
按行优先原则，数组B[]下标从0开始
(i≥j)是第个元素
==>B[K]
(i≥j)是第个元素
==>B[K]
考虑上三角？ 列优先？数组下标从1开始？i<j?的情况
三角矩阵
下三角矩阵：除了对角线核下三角区，其余的元素都相同的矩阵
策略：行优先存储下三角区，并在最后一个位置存储常量C
三对角矩阵(带状矩阵)
定义：当|i-j|>1时，有(1≤i,j≤n)
数组长度=3n-2
数组长度=3n-2
策略：行优先\列优先原则，只存储带状部分
行优先，数组下标从0开始时：
->B[k]，k=2i+j-3，是第k+1个元素
B[k]->，，j=k-2i+3
->B[k]，k=2i+j-3，是第k+1个元素
B[k]->，，j=k-2i+3
稀疏矩阵
定义：非零元素远远少于零元素的个数
策略：
1.顺序存储——三元组<行，列，值>
2.链式存储——十字链表法
1.顺序存储——三元组<行，列，值>
2.链式存储——十字链表法
第4章 串(String)
4.1 串的定义和实现
定义：由一个或多个字符组成的有限序列
一般记为，空串用表示
一般记为，空串用表示
字符集：
英文字符——ASCII字符集
中英文 ——Unicode字符集
英文字符——ASCII字符集
中英文 ——Unicode字符集
存储结构
定长顺序存储(静态数组实现)
堆分配存储(动态数组实现)
块链存储
每个节点存多个字符，没有字符的位置用'#'或'\0'补足
每个节点存多个字符，没有字符的位置用'#'或'\0'补足
4.2 串的模式匹配
(主串n>>模式串m)
(主串n>>模式串m)
朴素模式匹配算法
思想：将主串中所有长度为m的子串与模式串比较
时间复杂度:最坏O(nm)，最好O(n)
KMP算法
由D.E.Knuth,J.H.Morris和V.R.Pratt提出
由D.E.Knuth,J.H.Morris和V.R.Pratt提出
时间复杂度：O(m+n)
求next数组时间复杂度O(m)
模式匹配过程最坏时间复杂度O(n)
求next数组时间复杂度O(m)
模式匹配过程最坏时间复杂度O(n)
第5章 树与二叉树
5.1 树的基本概念
基本术语
树的路径长度：树根到每个结点的路径长度的总和
树的性质
节点数=总度数+1
度为m的树中第i层上至多有个节点(i≥1)
高度为h的m叉树至多有个节点(等比数列求和)，至少有h个节点
高度为h，度为m的树至少有h+m-1个节点
高度为h，度为m的树至少有h+m-1个节点
具有n个节点的m叉树的最小高度为
5.2 二叉树的概念
定义：每个结点至多只有两棵子树并且有左右之分，次序不能任意颠倒
特殊的二叉树
满二叉树
定义：高度为h，且含有个节点的二叉树
特点：
1.只有最后一层有叶子结点
2.不存在度为1的结点
3.节点i的左孩子为2i，右孩子为2i+1，父节点为
1.只有最后一层有叶子结点
2.不存在度为1的结点
3.节点i的左孩子为2i，右孩子为2i+1，父节点为
※完全二叉树
定义：每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应
特点：
1.只有最后两层可能有叶子结点
2.最多只有一个度为1的结点
3.节点i的左孩子为2i，右孩子为2i+1，父节点为
4.为分支结点，为叶子结点
1.只有最后两层可能有叶子结点
2.最多只有一个度为1的结点
3.节点i的左孩子为2i，右孩子为2i+1，父节点为
4.为分支结点，为叶子结点
二叉排序树
定义：
平衡二叉树
定义：
二叉树的性质
性质1：叶子结点比二分支结点多一个
性质2：非空二叉树第k层至多有个结点
性质3：高度为h的二叉树至多有个结点
性质4：对完全二叉树
①当i>1时，结点i的双亲编号为
②当2i≤n时，结点i的左孩子编号为2i，否则无左孩子
③当2i+1≤n时，结点i的右孩子编号为2i+1，否则无右孩子
④结点i所在层次(深度)为
①当i>1时，结点i的双亲编号为
②当2i≤n时，结点i的左孩子编号为2i，否则无左孩子
③当2i+1≤n时，结点i的右孩子编号为2i+1，否则无右孩子
④结点i所在层次(深度)为
性质5：具有n个结点的完全二叉树的高度为或
存储结构
顺序存储
为满足二叉树的任意性，深度为h的二叉树要申请大小的数组
完全二叉树和满二叉树适合顺序存储
链式存储
n个结点的二叉链表有n+1个空链域
5.3 二叉树的遍历和线索二叉树
二叉树(逻辑结构)的遍历
遍历序列
先序遍历
中序遍历
后序遍历
层次遍历
由遍历序列构造二叉树
前序+中序遍历序列
后续+中序遍历序列
层次+中序遍历序列
递归算法和非递归算法的转换
线索二叉树(物理结构)
相关概念
作用：方便找到某个结点的前驱和后继，方便遍历
线索：指向前驱/后继的指针称为线索
先序前驱/先序后继；中序前驱/中序后继；后序前驱/后序后继；
分类
先序线索二叉树
中序线索二叉树
后序线索二叉树
不能有效解决后序线索二叉树中求后序后继的问题
后序线索二叉树的遍历仍需要栈的支持
存储结构：
在二叉树链式存储结构的基础上增加两个标志位 ltag 和 rtag
ltag/rtag 为 1 时表示 lchild/rchild 指向前驱/后继
ltag/rtag 为 0 时表示 lchild/rchild 指向左孩子/右孩子
在二叉树链式存储结构的基础上增加两个标志位 ltag 和 rtag
ltag/rtag 为 1 时表示 lchild/rchild 指向前驱/后继
ltag/rtag 为 0 时表示 lchild/rchild 指向左孩子/右孩子
手画线索二叉树
二叉树线索化
视频5.3.5
5.4 树、森林
√
√
树的存储结构
双亲表示法
顺序存储结点数据，节点中保存父节点在数组中的下标，根节点为-1
优点：找父节点方便；缺点：找孩子不方便
孩子表示法
顺序存储节点数据，结点中保存孩子链表头指针(顺序+链式存储)
优点：找孩子方便；缺点：找父节点不方便
※孩子兄弟表示法
用二叉链表存储树——左孩子右兄弟
从存储视角来看形态上和二叉树类似
考点：
1.树与二叉树的相互转换，本质就是用孩子兄弟表示法存储树
2.已知树、森林的非终端节点个数，求对应二叉树的右指针为空的节点个数
1.树与二叉树的相互转换，本质就是用孩子兄弟表示法存储树
2.已知树、森林的非终端节点个数，求对应二叉树的右指针为空的节点个数
树、森林与二叉树的转换
本质：用孩子兄弟表示法——二叉链表存储森林
森林中各个根结点之间视为兄弟关系
树和森林的遍历
树的遍历
先根遍历
后根遍历
层序遍历
森林的遍历
先序遍历
中序遍历
树、森林遍历和二叉树遍历的对应关系
5.5 树与二叉树的应用
√
√
二叉排序树(BST)
定义：
左子树结点值<根节点值<右子树结点值，默认不允许两个结点的关键字相同
左子树结点值<根节点值<右子树结点值，默认不允许两个结点的关键字相同
二叉排序树的查找：
从根结点开始，目标更小向左找，目标更大向右找
从根结点开始，目标更小向左找，目标更大向右找
二叉排序树的插入：
找到插入位置(一定是叶子结点)，修改其父节点的指针
找到插入位置(一定是叶子结点)，修改其父节点的指针
二叉排序树的删除：
被删为叶子节点，直接删除
被删结点只有左子树或只有右子树，其子树顶替其位置
被删结点左右子树都存在
后继结点(右子树中最左下结点)顶替并删除
前驱结点(左子树中最右下结点)顶替并删除
查找效率分析
取决于树的高度，最好O(log n)，最坏O(n)
平均查找长度的计算
查找成功的情况
查找失败的情况(需补充失败结点)
平衡二叉树(AVL)
定义：树上任一结点的左子树和右子树的高度之差不超过1
结点的平衡因子=左子树高-右子树高
结点的平衡因子=左子树高-右子树高
平衡二叉树的插入
和二叉排序树相同，找到合适的位置插入，但新插入的结点可能导致查找路径上的某个结点不再平衡
"不平衡"调整的四种规律
找到最小不平衡子树进行调整，记最小不平衡子树的根为A
LL平衡旋转(右单旋转)：
在A的左孩子的左子树插入导致A失衡，将A的左孩子右上旋
在A的左孩子的左子树插入导致A失衡，将A的左孩子右上旋
RR平衡旋转(左单旋转)：
在A的右孩子的右子树插入导致A失衡，将A的右孩子左上旋
在A的右孩子的右子树插入导致A失衡，将A的右孩子左上旋
LR平衡旋转(先左后右双旋转)：
在A的左孩子的右子树插入导致A失衡，将A的左孩子的右孩子，先左上旋再右上旋
在A的左孩子的右子树插入导致A失衡，将A的左孩子的右孩子，先左上旋再右上旋
RL平衡旋转(先右后左双旋转)：
在A的右孩子的左子树插入导致A失衡，将A的右孩子的左孩子，先右上旋再左上旋
在A的右孩子的左子树插入导致A失衡，将A的右孩子的左孩子，先右上旋再左上旋
平衡二叉树的查找
考点：高为h的平衡二叉树最少有几个节点——递推求解
平衡二叉树最大深度为O(log n)，平均查找长度/查找的时间复杂度为 O(log n)
哈夫曼树和哈夫曼编码
定义
哈夫曼树(最优二叉树)：在含有给定的n个带权叶节点的二叉树中，WPL最小的二叉树
结点的权：某种特定含义的数值
结点的带权路径长度=根到结点的路径长度*结点的权值
树的带权路径长度(WPL)=树中所有叶子结点的带权路径长度之和
哈夫曼树的构造
每次选两个根节点权值最小的树合并，并将两者权值之和作为新的根结点的权值
哈夫曼树不唯一，但WPL必然都是最小值
※哈夫曼编码
将字符频次作为字符结点权值，构造哈夫曼树即可得哈夫曼编码，可用于数据压缩
前缀编码——没有一个编码是另一个编码的前缀
固定长度编码——每个字符用相等长度的二进制位表示
可变长度编码——允许对不同字符用不等长的二进制表示
KMP求next数组例子
第6章 图
6.1 图的基本概念
√√
√√
定义：G=(V,E)，顶点集V，边集E
边的权和网(带权图)
点到点的关系
连通：在无向图中，存在顶点u到顶点v的路径，则称u和v是连通的
连通图：若图G中任意两个顶点是连通的，则称图G为连通图，否则称为非连通图
连通分量：无向图中的极大连通子图称为连通分量(若n个顶点的图边数小于n-1，那么必是非连通图)
连通图：若图G中任意两个顶点是连通的，则称图G为连通图，否则称为非连通图
连通分量：无向图中的极大连通子图称为连通分量(若n个顶点的图边数小于n-1，那么必是非连通图)
强连通：有向图中，顶点u，v之间双向均存在路径，则称u，v是强连通的
强连通图：若图中任意一对顶点都是强连通的，则称为强连通图
强连通分量：有向图中的极大强连通子图称为有向图的强连通分量
强连通图：若图中任意一对顶点都是强连通的，则称为强连通图
强连通分量：有向图中的极大强连通子图称为有向图的强连通分量
路径：顶点到顶点之间的一条路径是指顶点序列(或边序列)
路径长度：指路径上边的数目
回路(环)：第一个顶点和最后一个顶点相同的路径
路径长度：指路径上边的数目
回路(环)：第一个顶点和最后一个顶点相同的路径
简单路径：路径序列中顶点不重复出现的路径
简单回路：除第一个和最后一个顶点，其余顶点不重复出现的回路
简单回路：除第一个和最后一个顶点，其余顶点不重复出现的回路
距离：u到v的最短路径长度，若不存在记该距离为无穷
图的局部
子图：
极大连通子图：
极大强连通子图：
极大强连通子图：
生成树：连通图中包含全部顶点的极小连通子图
生成森林：非连通图中各连通分量的生成树构成了非连通图的生成森林
生成森林：非连通图中各连通分量的生成树构成了非连通图的生成森林
几种特殊形态的图
简单图：如果图G满足：①不存在重复的边；②不存在顶点到自身的边，那么成图G为简单图
多重图：
多重图：
完全图(简单完全图)
无向完全图：有n(n-1)/2条边的无向图称为无向完全图，任意两个顶点之间都存在边
有向完全图：有n(n-1)条边的有向图称为有向完全图，任意两个顶点之间都存在两条方向相反的弧
无向完全图：有n(n-1)/2条边的无向图称为无向完全图，任意两个顶点之间都存在边
有向完全图：有n(n-1)条边的有向图称为有向完全图，任意两个顶点之间都存在两条方向相反的弧
稠密图与稀疏图：边数很少的图称为稀疏图，反之称为稠密图。一般当图G满足时视为稀疏图
有向树：一个顶点入度为0，其余顶点入度为1的有向图称为有向树
6.2 图的存储及基本操作
√√
√√
图的存储
邻接矩阵法
邻接表法
十字链表
邻接多重表
图的基本操作
6.3 图的遍历
√
√
广度优先搜索
类似于树的层序遍历
BFS算法的性能分析
无论是邻接表还是邻接矩阵，都需要辅助队列Q，空间复杂度
时间复杂度：
邻接表存储图时，每个顶点需入队一次，每条边至少访问一次，时间复杂度
邻接矩阵存储图时，查找每个顶点的邻接点所需时间O(|V|)，故时间复杂度
邻接表存储图时，每个顶点需入队一次，每条边至少访问一次，时间复杂度
邻接矩阵存储图时，查找每个顶点的邻接点所需时间O(|V|)，故时间复杂度
BFS算法求解单源最短路径问题
广度优先的生成树和生成森林
由广度优先遍历确定的树
邻接表存储的图表示方式不唯一，遍历序列，生成树也不唯一
遍历非连通图可得广度优先生成森林
深度优先搜索
类似于树的先序遍历
DFS算法的性能分析
DFS算法是递归算法，需要借助递归工作栈，故空间复杂度
时间复杂度：
DFS遍历图的过程实际上是对每个顶点查找其邻接点的过程
邻接表存储图时，访问顶点所需，查找所有顶点的邻接点所需，故总时间复杂度
邻接矩阵存储图时，查找每个顶点的邻接点所需时间，故总的时间复杂度
DFS遍历图的过程实际上是对每个顶点查找其邻接点的过程
邻接表存储图时，访问顶点所需，查找所有顶点的邻接点所需，故总时间复杂度
邻接矩阵存储图时，查找每个顶点的邻接点所需时间，故总的时间复杂度
深度优先的生成树和生成森林
由深度优先遍历确定的树
邻接表存储图的表示方式不唯一，遍历序列，生成树也不唯一
遍历非连通图可得深度优先生成森林
图的遍历与图的连通性
无向图
DFS/BFS调用次数=连通分量数
有向图
若从起始顶点到其他顶点都有路径，则只需调用一次DFS/BFS函数
对于强连通图，从任意顶点出发都只需调用一次DFS/BFS函数
6.4 图的应用
最小生成树
Prim算法
Kruskal算法
最短路径
Dijkstra算法求单源最短路径问题
Floyd算法求各顶点之间的最短路径问题
有向无环图描述表达式
拓扑排序
关键路径
第7章 查找
7.1 查找的基本概念
7.2 顺序查找和折半查找
7.3 B树和B+树
7.4 散列表
第8章 排序
8.1 排序的基本概念
8.2 插入排序
8.3 交换排序
8.4 选择排序
8.5 归并排序和基数排序
8.6 各种内部排序算法的比较及应用
0 条评论
下一页
