数据结构强化

第一章

时间复杂度和空间复杂度的计算

时间复杂度：一个语句在算法中被重复执行的次数

常见形式：

1️⃣ 阶乘n!：12...*n ，时间复杂度O(n)

2️⃣ 单个循环++：O(n)

3️⃣ 单个循环i*2: O(logn)

4️⃣ 双循环i与j无关联：O(n^2)

5️⃣ 双循环i与j关联：计算总次数

无论哪种形式 穷举各层的执行次数即可

阶乘和递归的时间复杂度？

阶乘和递归的时间复杂度都为O(n)

第二章 线性表

大题算法题的重点！首选暴力解

线性表（顺序表示）

线性表的数据结构定义

#define MaxSize 50

// 动态分配
typeof struct{
  ElemType *data;
  int MaxSize, length;
}SqList;

// 静态分配
typeof struct{
  ElemType data[MaxSize];
  int length;
}Sqlist

插入：插入i位置 i之后的元素依次后移一个位置，从后表尾开始遍历直到i的位置

删除：删除第i个位置元素，后续元素前移一个位置 和查找

位序和数组下标的区别：位序从1开始，数组下标从0开始

带头节点和不带头节点的区别：带头节点方便操作

链式表示

单链表的定义

typeof struct LNode{
  ElemType data;
  struct LNode *next;
}LNode,*LinkList

双链表的定义

typeof struct DLNode{
  ELemType data;
  struct DLNode *next,*prior;
}DLNode,*DLinkList

循环单链表：单链表的最后一个元素的指针值指向首元素

带头节点循环单链表如何判空？head->next = head

循环双链表：尾节点的next指针指向首节点 首节点的prior指向尾节点

静态链表：数组的下标作为指针

基本操作：插入、删除和查找

第三章 栈和队列

选择题和应用题

栈

栈的基本概念 LIFO

栈的顺序存储数据结构

#define Maxsize 30;

typeof struct{
  Elemtype data[Maxsize];
  int top;
}SqStack

栈的基本操作：

入栈先++ 再入栈(因为top指向栈顶元素，故需先将top++再使用top)

出栈先弹出栈顶元素，后--

栈满和栈空判断

共享栈（判断栈满）：栈底在两端，栈顶往中间靠

栈的链式存储数据结构：栈顶元素在表头，所有操作都在表头进行

队列

基本概念（FIFO）

队列的顺序存储数据结构

入队：先送值到队尾元素，再将队尾指针加1 rear++

出队：先取队尾元素，再将队头指针++

判断队空和队满（什么是假溢出）

循环队列（解决假溢出）

循环队列判断队空：Q.front == Q.rear

循环队列判断队满的三种方式 (Q.rear+1)% MaxSize == Q.front

循环队列入队：Q.rear = (Q.rear + 1)% MaxSize

循环队列出队：Q.front == (Q.front + 1)% MaxSize

队列的链式存储（带头节点和不带头节点）

双端队列

栈和队列的应用

栈在括号匹配中的应用

栈在表达式求值中的应用（计算栈的深度和栈中元素）区分操作符和操作数

中缀转后缀：

(A+B)*C-D/E 转换为后缀表达式：

初始化：栈为空，结果列表为空。

扫描过程：

遇到左括号“(`”：压入栈。

遇到操作数“A”：加入结果列表。

遇到操作数“B”：加入结果列表。

遇到操作符“+”：栈顶为左括号，故直接压入栈。

遇到右括号“)`”：弹出栈顶“+”加入结果列表，移除左括号。

遇到操作符“*”：栈为空，直接压入栈。

遇到操作数“C”：加入结果列表。

遇到操作符“-”：弹出栈顶“*”加入结果列表，再将“-”压入栈。

遇到操作数“D”：加入结果列表。

遇到操作符“/”：弹出栈顶“-”加入结果列表，再将“/”压入栈。

遇到操作数“E”：加入结果列表。

最终栈中只剩余操作符“/”，弹出并加入结果列表。

后缀表达式求值：操作数入栈，操作符

栈在递归中的应用

队列在层次遍历中的应用

队列在计算机系统中的应用（buffer、就绪队列、阻塞队列）

数组和特殊矩阵

特殊矩阵的压缩存储

按行或列优先存储，计算下标（不用背公式，直接穷举），注意区分下标从0还是从1开始

三角矩阵和三对角矩阵存储

稀疏矩阵的存储：三元组（行标i，列标j，值a；还需要保存稀疏矩阵的行数、列数和非零元素的个数），十字链表存储

第四章 串

简单模式匹配算法 需要后退次数 时间复杂度O(mn)

KMP算法： 先计算部分比配值，再将其右移再加1，得到next数组，时间复杂度O(m+n),主串不回退

求nextval数组（复杂）如何记忆？

写出数组下标和next数组 以位序开始

1的位置无脑填0

2的位置 比较当前位置的元素Pj与Pnext[j]是否相等 相等则P的nextval的值等于next[j]下对应nextval的值

不相等 P的nextval的值等于它的next的值

第五章 树与二叉树

考点：树的基本概念、二叉树的定义和基本特征、二叉树的顺序存储结构和链式存储结构、二叉树的遍历、线索二叉树构造、树的存储结构、森林与二叉树的转换、树和森林的遍历、树与二叉树的应用（哈夫曼树、哈夫曼编码、并查集）

树的基本概念

结点树n = 分支数 + 1 = n1 + 2n2 + ... + 1 = n0 + n1 + n2 + ...

分支数 = 树中各结点的度之和

树的最大高度（满m叉树）和最小高度（上1下m）

二叉树的概念

满二叉树的定义、结点总数、各层的结点数

完全二叉树定义、高度、叶子结点出现的情况、

二叉排序树

平衡二叉树

正则二叉树

结点总数 = n0 + n1 + n2 n0 = n2 + 1

二叉树的存储结构

顺序存储：按照层次遍历的顺序依次填入，如果该节点为空则使用0补位（注意下标位置）。

链式存储（空链域的个数n+1）

二叉树的遍历

先序遍历（根左右）

中序遍历（左根右）

后序遍历（左右根）

层次遍历（从根开始从左至右扫描，需要使用队列）

中 + 其余三种遍历中任意一种 即可唯一确定一棵树

如果无中 则无法唯一确定一棵树

递归和非递归的转换（利用栈）

线索二叉树

线索二叉树的数据结构 ltag和rtag的含义 0表示孩子 1表示前驱或者后继

使用二叉树遍历算法的到遍历序列 按照序列前后关系确定线索指针

树和森林

树的存储结构

1. 双亲表示法

数据结构定义：items：存储值的data，双亲在数组中的下标。双亲即为item[];

可以很快找到一个结点的双亲，

但是求一个结点的孩子则需要遍历整个结构 ⚠️

2. 孩子表示法

数组存放所有元素item，item：存放数据data，一个链表（表示该结点的孩子）

解决双亲表示法找孩子节点需要遍历整个结构，故使用一个链表来存储孩子节点

但是找一个结点的双亲很困难，需要遍历整个结构中的链表，寻找该结点在哪个结点的孩子链表中出现过

3. 孩子兄弟表示法（二叉树表示法）

数据data，左孩子指针，右孩子指针

实现树与二叉树的转换，便于查找结点的孩子，找双亲困难

树、森林、二叉树的转换

左孩子右兄弟

森林和树的遍历

先序和二叉树相同

树的后根和二叉树的中序遍历相同

森林中和二叉的中相同

树和二叉树的应用

哈夫曼树

1. 定义

路径、路径长度、权值、带权路径长度、WPL（哈夫曼树、最优二叉树）

2. 哈夫曼树的构造

取最小的两个节点的权值相加，将相加之后的权值加入原数据，依次重复

3. 哈夫曼树的性质

1️⃣ 每个结点在哈夫曼树中都是叶子结点。

2️⃣ 新增n-1个结点，哈夫曼树的总结点数为2n-1

3️⃣ 不存在度为1的结点

4. 哈夫曼编码、前缀编码

任何编码都不是另一个编码的前缀，前缀编码

左0右1或者左1右0

哈夫曼树并不唯一，但是WPL唯一

加权平均长度 = WPL / 权值之和

并查集

数组下标为个结点的编号，对应的值为其双亲的下标

优化：小树合并到大树

第六章 图

掌握图的基本概念、存储结构、遍历、应用

基本概念

顶点集、边集

有向图

无向图

简单图：不存在重复的边，自己到自己（仅讨论简单图）

多重图：与简单图相反

完全图：n(n-1)/2条边（无向图）、n(n-1)条变（有向图）

子图：

连通：存在路径

极大连通子图（连通分量）

强连通图、强连通分量

生成树、生成森林

顶点的度、入度和出度：无向图的度 = 边数的*2 、 有向图的度 = 入度 + 出度

A[i][j] 行遍历（出度）和A[j][i] 列遍历（入度）

边的权值和网

稠密图和稀疏图：

路径：顶点序列

路径长度：边数

回路：

图的存储及基本操作

1. 邻接矩阵法

数据结构定义：边表，顶点表

顶点的度的计算：对矩阵按行遍历非0元素的个数，得到出度，按列遍历，得到入度

优点：查看两个顶点是否相联很容易O(1)A[i][j]

缺点：确定边的个数，需要遍历矩阵中1的个数

A^n[i][j]的含义：表示顶点i到顶点j的长度为n的路径的数目

适合稠密图

2. 邻接表法

数据结构定义：数组存储顶点表（数据、指向第一个弧的的指针），边表（链表）

适用于稀疏图

找一个点相邻的边（容易 遍历该点的邻接表）

确定两个顶点间是否存在边（遍历该点的邻接表）

求某个顶点的度 只需计算该点边表结点的个数（无向图）

对于有向图 求某个点的度 出度遍历该点的边表 入度则需要遍历整个邻接表

邻接表不唯一

3. 十字链表

有向图

解决邻接表存储有向图计算出度需要遍历整个邻接表，因此十字链表很容易求得顶点的出度和入度

数据结构：弧结点包含 弧尾 弧头 弧头相同的下一结点 弧尾相同的下一结点

弧头相同的结点属于一个链表 弧尾相同的结点属于一个链表

十字链表表示唯一确定一个图

4. 邻接多重表

无向图

解决邻接表无向图求两个顶点间是否存在边和对边执行删除等操作时，需要分辨在两个顶点的边表中遍历

图的遍历

1. 广度优先遍历（BFS）

与二叉树的层序遍历一致

复杂度分析：

邻接表：空间O(V) 时间O(V+E)

邻接矩阵:空间O(V) 时间O(V^2)

广度优先生成树 唯一性的判定

2. 深度优先遍历

与二叉树的 先序遍历一致

复杂度分析：

递归栈：空间复杂度O(V)

邻接矩阵：O(V^2)

邻接表：O(V+E)

深度优先生成树和生成森领

图的应用

1. 最小生成树

针对于带权无向图

最小生成树唯一性问题

图中所有边的权重都不同，那么最小生成树是唯一的。

Prim算法：

取相邻不重复的最小权值的边加入

时间复杂度：O(V^2) 不依赖于E 适合边稠密图

Kruskal算法：

按照权值递增次序选择合适的边来构造

时间复杂度O(ElogE)，不依赖于V，适合边稀疏而顶点多的图

总的来说，不论采取何种策略，最小生成树的代价是唯一的。

2. 最短路径

Dijkstra算法求解单源最短路径：

每轮确定一个最近的点作为中转点，判断以该点到达其余点的路径是否比上一轮更小，若更小则更新。

三个辅助数组：final[]、dist[]、path[]

不适合带负权值的图

时间复杂度O(V^2)

Floyd求解各点之间的最短路径问题：

图中的各个顶点轮流称为中间结点 判断以此结点为中转到其余结点的权值是否更小 是的话就更新 否则不更新

时间复杂度O(V^3)

适合带负权值的图

3. 有向无环图描述表达式

4. 拓扑排序

AOV网（有向无环图）

是对有向无环图的一种排序，可用于判断是否存在回路

每次选择入度为0的结点，并消去与之相连的边，直到当前图中不存在无前驱的结点为止。

可利用DFS实现拓扑排序，利用结束时间从大到小排列（父结点的结束时间大于孩子结点的结束时间）

存在性和唯一性的判断：

各个点仅有唯一的前驱或后继，拓扑排序唯一，否则不唯一

邻接矩阵存储 若为三角矩阵(上三角或狭三角)，则存在拓扑排序，反之不一定

如果图中不存在两个顶点同时满足入度为 0 的条件，则拓扑排序是唯一的。

A -> B
|     |
v     v
C -> D

A -> B
     |
     v
C <- D

邻接矩阵：

  A B C D
A 0 1 1 0
B 0 0 0 1
C 0 0 0 1
D 0 0 0 0

  A B D C
A 0 1 0 0
B 0 0 1 0
D 0 0 0 1
C 0 0 0 0

拓扑排序的唯一性取决于图的结构。如果在任一步骤中存在多个入度为 0 的顶点，则拓扑排序就不是唯一的。反之，如果每一步只有一个入度为 0 的顶点，则拓扑排序是唯一的。

判断一个图中是否存在回路：

DFS、BFS、并查集、拓扑排序

1. 关键路径

AOE网（带权有向无环图）

事件的最早发生时间Vk

事件的最晚发生时间V

第七章 查找

ASL（Average Search Length），即平均查找长度，在查找运算中，由于所费时间在关键字的比较上，所以把平均需要和待查找值比较的关键字次数称为平均查找长度

求和符号n Σ Pi Ci

其中n为查找表中元素个数，Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n，Ci是找到第i个元素的比较次数。

平均查找长度 = 查找的总次数 / 查找表的长度 （默认查找概率相同 所以除以查找表的长度 ）

顺序查找和折半查找

顺序查找哨兵的作用:哨兵模式是将数组的第一个位置设为哨兵，

平均查找成功长度和平均失败查找长度分析

每个元素查找成功的总次数 / 查找表的长度

每个元素查找失败的总次数 / 查找表的长度

折半查找的代码（熟悉掌握），模拟查找过程和查找次数（成功和失败）查找树

分块查找：先分块，块内无序（顺序查找），块间有序（第一块的最大小于第二块的所有 ，记录每块的最大或者最小值为索引）

树形查找

1. 二叉排序树

左 < 根 < 右

中序遍历为递增有序序列

二叉排序树的构造、插入和删除

删除后填补，利用中序遍历序列中删除该结点的后一个结点填补

查找效率分析

二叉排序树并不唯一

2. 平衡二叉树

左右子树高度之差（平衡因子）不超过1

插入以及调整操作过程：LL、RR、LR、RL

每次调整的都是最小不平衡子树

构造平衡二叉树的过程、删除过程以及查找过程

查找过程与二叉排序树相同

平均查找效率为树的高度（log2n）

平衡二叉树平衡因子为1，结点总数的计算：

对于一棵平衡二叉树，其中所有非叶子节点的平衡因子均为1，这意味着每个非叶子节点的左子树高度比右子树高1。这种情况下，整棵树可以看作是一棵完全倾斜的AVL树，即每一层都尽可能多地向一侧扩展。

假设平衡二叉树的高度为 ( h )，那么在这种特定的情况下，我们可以通过递推公式来计算节点总数。设 ( N(h) ) 表示高度为 ( h ) 的平衡二叉树的节点总数。

由于每个非叶子节点的平衡因子都是1，所以高度为 ( h ) 的树可以分解为：

左子树的高度为 ( h-1 ) 右子树的高度为 ( h-2 ) 因此，节点总数满足以下递推关系： [ N(h) = N(h-1) + N(h-2) + 1 ]

初始条件为： [ N(0) = 0 ] [ N(1) = 1 ]

现在我们手动计算一下高度为6的情况：

[
\begin{align*}
N(0) & = 0 \
N(1) & = 1 \
N(2) & = N(1) + N(0) + 1 = 1 + 0 + 1 = 2 \
N(3) & = N(2) + N(1) + 1 = 2 + 1 + 1 = 4 \
N(4) & = N(3) + N(2) + 1 = 4 + 2 + 1 = 7 \
N(5) & = N(4) + N(3) + 1 = 7 + 4 + 1 = 12 \
N(6) & = N(5) + N(4) + 1 = 12 + 7 + 1 = 20 \
\end{align*}
]

因此，高度为6的平衡二叉树，所有非叶子节点的平衡因子均为1时，该平衡二叉树的节点总数为20。

3. B树和B+树

B树的定义和特点

关键字个数：[m/2] 向上取整 - 1 <= n <= m-1（注意区分根结点最少1）

叶子结点代表查找失败

树的高度（磁盘存取次数） 关键字最多和关键字最少树的高度推导公式

B树的插入和删除（分裂和合并策略）

B+树的定义和特点

关键字个数[m/2] <= n <=m (注意区分根结点最少2)

叶子结点包含全部关键字信息（非叶结点仅起索引作用）

B+树和B树的区别！

从关键字个数 根结点 叶子结点分析 关键字对应树的个数

4. 散列表（hash）

散列表的概念：散列函数、冲突、散列表

散列函数的构造：

直接定址法： y(x) = kx + b

除留余数法 选质数p p一般选择小于散列表长度m的最大质数 h(key) = key / p

数字分析法

平方取中法

解决冲突的方法：

开放定址法：（H(key) + di）% m

对于增量d的取值采用以下方法：

线性探测法（真题中称为线性探测再散列）：1，2，... m-1，顺序的查看表中的下一个单元（存在堆积现象）

平方探测法：1^2，2^2...k^2

双散列法：第一个散列函数得到的地址发生冲突时，则利用第二个散列函数计算该关键字的地址增量。

伪随机序列法：增量为随机序列

开放定址法的删除操作采用软删除（逻辑删除）

拉链法：将产生冲突的同义词使用一个链表存储起来（适合经常插入和删除）

散列表查找性能分析：

查找成功 = 各关键字查找次数之和 / 关键字个数 （⚠️ 不是散列表的长度）

查找失败 = （0～p-1）查找失败次数之和 / 表长（要模以的数字）

⚠️：假设质数为7 那么只有可能在0-6 依次计算0-6间各数查找失败的情况的次数 当下一个位置为空即为查找失败，下个位置为空是指在整个表长范围内

https://blog.csdn.net/cj151525/article/details/109435869

影响散列表查找效率的因素：散列函数、处理冲突的方法和装填因子

装填因子：表中记录数n / 散列表的长度m

解题步骤

1️⃣ 确定散列表表长（可由装填因子得到）

2️⃣ 确定散列函数和解决冲突的方法

3️⃣ 画出所构造的散列表

4️⃣ 计算查找成功平均查找长度 = 各关键字查找次数之和 / 关键字个数 （⚠️ 不是散列表的长度）查找失败 = 各关键字查找失败次数之和 / 表长（要模以的数字 如质数p）

第八章 排序

外部排序（王道视频课二刷）

增加归并段 从而减少归并趟数 进而减少IO次数，但增加归并段后，内部归并时间也会增加，因此引入败者树（完全二叉树）

减少初始归并段也能减少归并趟数，置换-选择排序（生成初始归并段）得到的初始归并段长度不等，

1. 插入排序

直接插入排序：

基本思想：将第i个元素插入到前面已有序的子序列中

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

每趟可确定一个元素的最终位置

理想情况是已有序，只需要比较n次 时间复杂度O(n)

最差情况逆序，比较次数1+2...+n次 时间复杂度O(n^2)

折半插入排序：

基本思想：因为前面已有有序的子序列，可利用折半查找找到当前i元素需要插入的位置，后续元素依次后移

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

每趟可确定一个元素的最终位置

直接插入排序和折半插入排序元素比较次数分析：

正常情况下，折半插入可减少元素比较次数，但不能减少元素的移动次数（与直接插入一致），

但存在一种异常情况，就是待排序元素已有序，直接插入只需要比较n次，但折半插入仍然需要比较nlogn次。

希尔排序：

基本思想：划分增量，每趟减少增量，根据增量划分子表，子表内采用直接插入排序

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

每趟不可确定一个元素的最终位置

2. 交换排序

冒泡：

顺序，从前往后依次比较两者中大的元素往后移动或者从后往前比较两者中小的元素往前移动

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：稳定

每趟可确定一个元素的最终位置

最坏情况的比较次数：n-1，n-2...

最好情况：n次

快速排序：

要求手写实现

基本思想：基于分治法，从待排序序列中选择一个元素 pivot 作为枢轴（通常取首元素），通过一趟排序将待排序序列分为前后两部分， 前面的比 pivot 小，后面的比 pivot 大，pivot 放在最终位置上，这个过程称为一次划分。然后对两个子表分别重复上述操作，直到每部分只有一个元素或为空。

空间复杂度：O(log2n)时间复杂度：O(nlog2n)稳定性： 不稳定

每趟可确定一个元素的最终位置

3. 选择排序

简单选择排序：

第 i 趟从后续的待排序元素中选择最小的元素与 L[i]交换，

空间复杂度：O(1)时间复杂度：O(n^2)稳定性： 不稳定

每趟排序可以确定一个元素的最终位置。

堆排序：

建堆、调整堆、堆插入

利用小顶堆找到大量数据中的最大m个数

空间复杂度：O(1)时间复杂度：O(nlog2n)稳定性： 不稳定

每趟可确定一个元素的最终位置

4. 归并排序

将两个或两个以上的虚表合并成一个新的有序表

注意和希尔排序区分，希尔排序是选择增量，归并排序是根据归并段进行合并，归并段是不变的，增量是改变的

每趟不可确定一个元素的最终位置

5. 基数排序

从个位到最高位 需要r个队列、头指针、尾指针

空间效率:一趟排序需要的辅助存储空间为，(r 个队列:r 个队头指针和个队尾指针)，但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为 O(r)。 时间效率:基数排序需要进行 d 趟“分配”和”收集”操作。一趟分配需要遍历所有关键字，时间复杂度为 O(n);一趟收集需要合并 7 个队列，时间复杂度为 O(r)。因此基数排序的时间复杂度为 O(d(n+r))，它与序列的初始状态无关。 稳定性:每一趟分配和收集都是从前往后进行的，不会交换相同关键字的相对位置，因此基数排序是一种稳定的排序算法。

每趟不可确定一个元素的最终位置

每趟不可确定一个元素的最终位置

希尔排序、归并排序、基数排序

遗留问题

1. 特殊矩阵下标推导

穷举法，手动推算出来

2. next数组和nextval数组

3. 并查集

4. 关键路径计算

5. 散列表

6. 红黑树

7. 外部排序