第一章 绪论
- 数据结构包含三个方面的内容：
- 数据的逻辑结构：描述数据之间逻辑关系的、与数据的存储无关的数学模型。相同的逻辑结构可使用不同的存储结构存储，如线性表既可顺序存储，也可链式存储
- 线性结构：一个线性表是n个具有相同特性的数据元素的有限序列
- 一般线性表
- 受限线性表：栈、队列、串
- 线性表推广：数组
- 非线性结构
- 集合
- 树形结构：一般树、二叉树
- 图状结构：有向图、无向图
- 线性结构：一个线性表是n个具有相同特性的数据元素的有限序列
- 数据的物理结构：指数据的逻辑结构在计算机中的存储实现。如顺序表、散列表、单链表都是既描述了逻辑结构，又描述了数据运算和物理（存储）结构，但不归为逻辑结构的范畴
- 顺序存储结构：逻辑上相邻的元素在物理上也相邻。可随机存取，但只能使用相邻的一整块存储单元
- 链式存储结构
- 索引存储结构：在存储元素信息的同时，还建立附加的索引表。优点是检索速度快，缺点是附加的索引表额外占用存储空间
- 散列存储结构
- 数据的运算：指对数据实施的操作。如对数据进行增删改查、排序等
- 例如栈和队列的运算就不同，栈由同侧进出（后进先出），队列由异侧进出（先进先出）
- 数据的逻辑结构：描述数据之间逻辑关系的、与数据的存储无关的数学模型。相同的逻辑结构可使用不同的存储结构存储，如线性表既可顺序存储，也可链式存储
- 抽象数据类型：（数据对象，数据关系，基本操作集），用于描述数据的逻辑结构和抽象运算。
- 分析算法效率时的一些术语：
- 问题规模：指算法的输入量，可理解为数据量的大小。如在排序算法中，问题规模n指参与排序的数据个数；在树相关运算中，问题规模n指树中节点的个数。是与空间复杂度有关的
- 基本语句：指对算法运行时间影响最大的语句
- 算法原地工作的意思是需要常量级别的辅助空间，而不是不需要任何额外辅助空间
- 分析时间复杂度总是考虑该算法在最坏情况下的时间复杂度
- 同一个算法，实现语言的级别越高，执行效率越低
- 算法的健壮性是指：算法能考虑到各种边界异常条件，并作出相应的处理判断。即当输入非法错误时，算法也能进行适当处理
- 算法的五大特性：有穷性、确定性、可行性、输入和输出
- 定义逻辑结构时可以不考虑存储结构
第二章 线性表
第三章 栈、队列和数组
- 卡特兰数 1 n + 1 C 2 n n \frac{1}{n+1}C^n_{2n} n+11C2nn：可算出n个元素的输入序列总共有可能出现多少种合法的出栈序列。
- 栈和队列的应用
- 括号匹配问题（栈）
- 表达式求值（栈）
- 中缀表达式转后缀表达式：一个栈，用于暂存还不能确定运算顺序的运算符
- 后缀表达式的计算：一个栈，用于暂存操作数
- 中缀表达式的计算：两个栈，操作数栈和运算符栈。若扫描到操作数则直接压入操作数栈，若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（每当弹出运算符，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）
- 递归（栈）
- 树的层次遍历（队列）
- 图的广度优先遍历（队列）
- 操作系统中，FCFS策略的实现（队列）（场景为多个进程争抢有限的系统资源时，如CPU资源的分配、打印数据缓冲区）
- 队列的判空判满
- 顺序队列：
- 队尾指针Q.rear指向队尾元素的下一个位置
- 牺牲一个存储空间作为代价（还剩一个存储空间时，Q.rear指向空的这个存储空间，此时判定队满。因为若把这个存储空间占了，同时Q.rear后移一位，就会导致Q.rear和Q.front指向同一个位置，这就和队空时的判定条件重复了）
- 队空条件： Q . r e a r = = Q . f r o n t Q.rear == Q.front Q.rear==Q.front，
- 队满条件： ( Q . r e a r + 1 ) % M a x S i z e = = Q . f r o n t (Q.rear+1)\%MaxSize==Q.front (Q.rear+1)%MaxSize==Q.front
- 使用一个变量size表示队列中存放了几个数据元素
- 队空条件： Q . r e a r = = Q . f r o n t , s i z e = = 0 Q.rear==Q.front, size==0 Q.rear==Q.front,size==0
- 队满条件： Q . r e a r = = Q . f r o n t , s i z e = = M a x S i z e Q.rear==Q.front, size==MaxSize Q.rear==Q.front,size==MaxSize
- 牺牲一个存储空间作为代价（还剩一个存储空间时，Q.rear指向空的这个存储空间，此时判定队满。因为若把这个存储空间占了，同时Q.rear后移一位，就会导致Q.rear和Q.front指向同一个位置，这就和队空时的判定条件重复了）
- 队尾指针Q.rear指向队尾元素
- 队空条件：
(
Q
.
r
e
a
r
+
1
)
%
M
a
x
S
i
z
e
=
=
Q
.
f
r
o
n
t
(Q.rear+1)\%MaxSize == Q.front
(Q.rear+1)%MaxSize==Q.front（因为Q.rear指向队尾元素时，插入节点时是先Q.rear+1，再让Q.data[Q.rear]=x）
- 队满条件：和“队尾指针Q.rear指向队尾元素的下一个位置”中的情况一样，若不牺牲一个位置，队空和队满的条件一样。方法也同样有两种，要么就是牺牲一个存储单元，要么就是增加一个辅助变量
- 队空条件：
(
Q
.
r
e
a
r
+
1
)
%
M
a
x
S
i
z
e
=
=
Q
.
f
r
o
n
t
(Q.rear+1)\%MaxSize == Q.front
(Q.rear+1)%MaxSize==Q.front（因为Q.rear指向队尾元素时，插入节点时是先Q.rear+1，再让Q.data[Q.rear]=x）
- 队尾指针Q.rear指向队尾元素的下一个位置
- 链式队列：在上述的顺序队列中，用了很大篇幅解决如何判断队满队空；而在链式存储的队列中，可以不用关心这个问题，因为链式存储一般不会队满，除非内存不足。
- 特殊情况：用非循环单链表存储的队列进行删除操作时，头尾指针可能都要修改（头指针是因为要出队；修改尾指针是因为当队列仅有一个元素时，删除操作后队列为空，需要修改尾指针为rear=front，表示队空状态）
- 中缀转后缀
- 顺序队列：
- 队列元素个数公式（rear表示队尾节点的后一个位置；front表示队头节点）： ( r e a r + M a x S i z e − f r o n t ) % M a x S i z e (rear+MaxSize-front)\%MaxSize (rear+MaxSize−front)%MaxSize
- 任何递归过程都可以通过迭代或利用栈等方式转化为非递归过程，在算法中消除递归不一定使用栈
在递归过程转换为非递归过程时是否使用栈和局部变量的存在没有必然关系。
栈是实现过程和函数等子程序调用时所必需的结构
第五章 树与二叉树
- 并查集：
- 并查集的应用：
- 可用于实现Kruskal算法（找边）求最小生成树
- 可用于判断无向图的连通性
- 可用于判断无向图中是否有环
- （X）并查集不可以用于迪杰斯特拉算法求最短路径
- （X）并查集不可以用于Prim算法（找点）求最小生成树
- 并查集的存储方式
- 逻辑：双亲表示法的树
- 存储：数组
- 并查集的时间复杂度（m为并查集长度）
- find：优化前为 O ( m ) O(m) O(m)；优化后为 O ( l o g 2 n ) O(log_{2}n) O(log2n)
- union： O ( 1 ) O(1) O(1)
- 总复杂度：优化前 O ( m 2 ) O(m^2) O(m2)；优化后 O ( m ) O(m) O(m)
- 并查集的应用：
- 树、森林、二叉树遍历序列的关系
树 森林 二叉树 先根遍历 先序遍历 先序遍历 后根遍历 中序遍历 中序遍历 关于森林的中序遍历/后序遍历叫法问题：二者指森林的同一种遍历方法，都是先遍历第一棵树的子节点，然后是第一棵树的根节点，然后是第二棵树… 之所以称为中序遍历，是因为要先处理完一棵树再处理另一棵树。文章来源地址https://www.toymoban.com/news/detail-632183.html
- 前缀编码：没有任何一个编码是其他某个编码的前缀
第六章 图
- DFS与BFS算法的应用：
- DFS：
- 判断图的（强）连通性
- 无向图的连通性：若从任意一个节点出发，仅需一次DFS就可以访问图中所有节点，则该无向图就是连通的
- 有向图的强连通性：从任意一个节点v出发DFS，若可以遍历该有向图的所有节点，则此时将该有向图的所有边反向，再次从节点v出发进行DFS，若能够再次遍历该有向图的所有节点，则表示该有向图是强连通图
- 判断图中是否有环（回路）
- 欧拉回路求解：若一条路径能不重复的包含图中所有边，则称该路径为欧拉路径。若一条回路（从一个节点出发又能回到该节点的路径）是欧拉路径，则称为欧拉回路。DFS可以判断图中是否存在欧拉回路
- 迷宫
- 判断二分图
- 判断图的（强）连通性
- BFS：
- 求解单源最短路径问题（只适用于无权图）
- 迷宫
- 判断二分图
- DFS：
- 最短路径
- 有无环（回路）对Dijkstra算法并无影响，但Dijkstra算法不能求解存在负权值边的图；Floyd算法可以求带有负权值边的图，但图中不能存在负权回路（因为带有负权回路的图没有最短路径）
- Dijkstra算法是解决单源最短路径类问题，floyd算法是解决多源最短路径（指图中任意两个顶点之间的最短路径）类问题
- Dijkstra算法属于贪心算法，floyd算法属于动态规划算法
- 判断有向图是否有环（回路）的几种方法：
- 深度优先遍历：若在遍历过程中遇到要访问的节点已在栈中就是有环
- 拓扑排序：找不到拓扑序列必定有环
- 拓扑排序
- 在拓扑排序算法中，为暂存入度为零的顶点可以使用栈，也可以使用队列。（因为只要入了栈/队列，就都是入度为零的，从哪个入度为零的先开始都无所谓）
- 采用深度优先遍历也可实现拓扑排序
- 图的四种存储数据结构
- 存有向图：
- 邻接矩阵：空间复杂度太高
- 邻接表：找某一个顶点的入边很不容易，必须要遍历整个邻接表
- 十字链表：解决了上面两个数据结构的问题
- 存无向图
- 邻接矩阵：空间复杂度太高
- 邻接表：每条边会对应两个边节点（因为一条边连着两个节点，两个节点都会各自指向一个代表这条边的边节点）。这就导致若要删除某条边，就要对应删除两个节点，若要删除某个节点，除了删除本节点和该节点指出的若干边外，还要到其他节点那里删除和这些边重复表示的那些边节点。所以删除一个顶点或删除一条边时会很不方便
- 邻接多重表：解决了上面两个数据结构的问题
- 存有向图：
第七章 查找
- 红黑树插入最多两次旋转，删除最多三次旋转（记忆即可）
- 红黑树和AVL树都属于自平衡的二叉树
- 关于平衡二叉树的转化中，删除节点再还原，无论是删除非叶还是删除叶节点，都有可能导致还原后的树与原来的树相同或不同
对于普通二叉树，删除叶节点再还原，与原树一定相同；删除非叶节点再还原，与原树一定不同 - B+树支持顺序查找（因为它叶子节点存有所有数据）和随机查找；而B树只能支持随机查找。B+树的叶节点是通过指针相互链接的，导致B+树不仅可以从上往下，按照树的方式向下遍历，也可以通过叶节点那层的指针进行顺序遍历
- B树和B+树都是平衡的多叉树，二者都可以用于文件索引结构
- B+树产生的原因就是源于操作系统的文件索引和数据库索引
- 存储结构与查找方法的对应关系：
- 顺序查找法：适用于符合线性且可以按顺序访问下一个节点的存储结构。如顺序存储结构与链式存储结构
- 折半查找法：仅适合于顺序存储结构（因为折半查找需要获取一段数据的中间元素，也就是需要随机存取，链式结构的话需要从头一个个遍历到中间元素，不适合）
- 树型查找法：适用于树型存储结构
- 散列查找法：适用于散列表
- 在采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是“解决冲突的方法选择不当”。（因为这样就会导致非同义词与同义词的冲突变多，正是聚集的主要原因）
- B树中，“终端节点”指正常节点的最下面一层节点，“叶子节点”指那些查找失败的节点。所有的叶节点都出现在同一层次上，且不带信息（实际上这些叶节点并不存在，指向这些节点的指针为空）；B+树中，“叶子节点”是有值的最后一层节点，其指向自己对应的记录
- B+树中叶子节点包含信息，所有非叶节点仅起索引作用，且非叶节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址；而B树的节点中都包含了关键字对应记录的存储地址
- B+树都典型应用：关系型数据库的“索引”（如MySQL）
由于B+树的非叶节点不含有该关键字对应记录的存储地址，因此可以使一个磁盘块包含更多关键字，使得B+树的阶更大，树高更矮（一块磁盘即为一个节点），读磁盘次数更少，查找更快 - B树和B+树的对比
- 折半查找的判定树中，若 m i d = ⌊ ( l o w + h i g h ) / 2 ⌋ mid=\lfloor(low+high)/2\rfloor mid=⌊(low+high)/2⌋，则对于任何一个节点，必有：右子树节点数-左子树节点数=0或1
- 折半查找判定树一定是平衡二叉树
第七章 排序
- 排序算法的稳定性与优劣无关，没有“稳定的排序方法优于不稳定的排序方法”这一说
- 排序算法中有部分算法不能应用在链表上（如折半插入），这是因为没有了随机存取特性。但仍有部分算法是可以完美使用的，如直接插入排序
- 对任意n个关键字排序的比较次数至少为 ⌈ l o g 2 ( n ! ) ⌉ \lceil log_2(n!) \rceil ⌈log2(n!)⌉
- 快排中，递归的次数其实就是分界的次数，根本影响因素就是基准元素的左右划分情况。因此和初始排列次序有关。而每次划分后，会出现两个长度可能不同的分区，先处理长的还是先处理短的对整体递归次数都没有影响
- 由于链式存储无随机存取特性、只能正向访问，因此导致对绝大部分内部排序而言，链式存储无法实现其功能。而内部排序算法都可以使用顺序存储。
- 排序方法是“稳定的”：假设两个元素相等，若在排序后的序列中，排序前就在前面的元素仍在前面，则称所用的排序方法是稳定的；反之，若排序后两个相等元素调换相对位置，则称所用的排序方法是不稳定的
文章来源：https://www.toymoban.com/news/detail-632183.html
到了这里，关于数据结构中一些零碎且易忘的知识点的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
