-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path讲义(12).txt
288 lines (267 loc) · 14.4 KB
/
讲义(12).txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
AcWing《考研算法辅导课》讲义
考纲：
一、线性表
（一）线性表的定义和基本操作
（二）线性表的实现
1. 顺序存储
2. 链式存储
3. 线性表的应用
二、栈、队列和数组
（一）栈和队列的基本概念
（二）栈和队列的顺序存储结构
（三）栈和队列的链式存储结构
（四）栈和队列的应用
（五）特殊矩阵的存储和压缩
三、树与二叉树
（一）树的基本概念
（二）二叉树
1. 二叉树的定义及其主要特征
2. 二叉树的顺序存储结构和链式存储结构
3. 二叉树的遍历
4. 线索二叉树的基本概念和构造
（三）树、森林
1. 树的存储结构
2. 森林与二叉树的转换
3. 树和森林的遍历
（四）树与二叉树的应用
1. 二叉排序树
2. 平衡二叉树
3. 哈夫曼（Huffman）树的哈弗曼编码
四、图
（一）图的基本概念
（二）图的存储及基本操作
1. 邻接矩阵法
2. 邻接表法
3. 邻接多重表、十字链表
（三）图的遍历
1. 深度优先搜索
2. 广度优先搜索
（四）图的基本应用
1. 最小（代价）生成树
2. 最短路径
3. 拓扑排序
4. 关键路径
五、查找
（一）查找的基本概念
（二）顺序查找法
（三）分块查找法
（四）折半查找法
（五）B树及其基本操作、B+树及其基本概念
（六）散列（Hash）表
（七）字符串模式匹配（KMP）
（八）查找算法的分析及应用
六、排序
（一）排序的基本概念
（二）插入排序
1. 直接插入排序
2. 折半插入排序
（三）起泡排序（bubble sort）
（四）简单选择排序
（五）希尔排序（shell sort）
（六）快速排序
（七）堆排序
（八）二路归并排序（merge sort）
（九）基数排序
（十）外部排序
（十一）各种内部排序算法的比较
（十二）排序算法的应用
-------------------------------------------------------------------------------------
第1讲 时间复杂度、矩阵展开
一、时间、空间复杂度
只考虑次数，不考虑常数。常见复杂度有：O(1)、O(n)、O(sqrt(n))、O(n^k)、O(logn)、O(nlogn)
考题：2011-1、2012-1、2013-1、2014-1、2017-1、2019-1
二、矩阵展开
矩阵的按行展开、按列展开，展开后下标从0开始。
考题：2016-4、2018-3、2020-1
-------------------------------------------------------------------------------------
第2讲 线性表
1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。
2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。
3. 线性表的分类
(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；
例如：数组
(2) 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。
例如：单链表、双链表、循环单（双）链表
4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）
(1) 数组：随机索引O(1)、插入O(n)、删除O(n)
(2) 单链表：查找某一元素O(n)、插入O(1)、删除O(n)
(3) 双链表：查找某一元素O(n)、插入O(1)、删除O(1)
5. 考题：2016-1、2016-2、2012-42、2015-41、2019-41
6. 押题：AcWing 34、AcWing 1451
-------------------------------------------------------------------------------------
第3讲 栈与队列
1. 栈和队列的基本概念
2. 栈和队列的顺序存储结构
(1) 栈：栈顶元素位置：指向最后一个元素、指向最后一个元素的下一个位置
(2) 队列：一般采用循环队列。
(a) 队头元素位置：指向第一个元素、指向第一个元素的前一个位置。
(b) 队尾元素位置：指向队尾元素、指向队尾元素的下一个位置。
3. 栈和队列的链式存储结构
4. 栈和队列的应用
(1) 栈的应用：表达式求值（中缀表达式转后缀表达式、括号匹配）、DFS
(2) 队列的应用：BFS
5. 考题：2011-2、2011-3、2012-2、2013-2、2014-2、2014-3、2015-1、2016-3、2017-2、2018-1、2018-2、2019-42、2020-2
6. 押题：AcWing 3302
-------------------------------------------------------------------------------------
第4讲 树的基本概念、二叉树、树和森林
1. 树的基本概念
(1) 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。
(2) 空集合也是树，称为空树。空树中没有节点；
(3) 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
(4) 节点的度：一个节点含有的子节点的个数称为该节点的度；
(5) 叶节点或终端节点：度为0的节点称为叶节点；
(6) 非终端节点或分支节点：度不为0的节点；
(7) 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
(8) 兄弟节点：具有相同父节点的节点互称为兄弟节点；
(9) 树的度：一棵树中，最大的节点的度称为树的度；
(10) 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
(11) 树的高度或深度：树中节点的最大层次；
(12) 节点的祖先：从根到该节点所经分支上的所有节点；
(13) 子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
(14) 森林：由棵互不相交的树的集合称为森林。
2. 二叉树
(1) 二叉树的定义及其主要特征
a. 二叉树的基本形态：空二叉树、单节点二叉树、左子树、右子树
b. 性质：
[1] 在非空二叉树中，第i层上至多有2^(i-1) 个结点。
[2] 深度为k的二叉树至多有2^k - 1个结点
[3] 对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
[4] n个结点的完全二叉树深度为：log2(n)向下取整 + 1
[5] 二叉树的堆式存储: 节点p的左儿子：2x，右儿子：2x+1
c. 两种特殊的二叉树
[1] 满二叉树：一颗深度为k且有2^k-1个结点的二叉树
[2] 如果深度为k,有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树
(2) 二叉树的顺序存储结构和链式存储结构
(3) 二叉树的遍历
a. 前序遍历
b. 中序遍历
c. 后序遍历
d. 根据前序 + 中序重建二叉树（AcWing 18)
(4) 线索二叉树的基本概念和构造
对二叉树节点的指针域做如下规定：
a. 若节点有左孩子，则Lchild指向左孩子，否则指向直接前驱；右孩子同理；
b. 增加两个标志域，Ltag表示指向的是子节点还是前驱；Rtag同理
c. 指向前驱和后继的指针叫做线索。按照某种次序遍历，加上线索的二叉树称之为线索二叉树
3. 树、森林
(1) 树的存储结构
a. 只存父节点
b. 邻接表存储所有子节点
c. 左儿子右兄弟
(2) 森林F与二叉树T的转换
a. 原树中叶子节点数 = 转换后的树中有右儿子的节点数 + 1
b. F的前序遍历就是T的前序遍历
c. F的后序遍历就是T的中序遍历
(3) 树和森林的遍历
a. 前序遍历
b. 后序遍历
4. 考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4
5. 押题：AcWing 18、AcWing 19
-------------------------------------------------------------------------------------
第5讲 二叉排序树、表达式树
1. 二叉排序树
2. 平衡树——AVL
(1) 定义：满足如下条件的树：
a. 是二叉查找树
b. 每个节点的左子树和右子树的高度差最多为1
(2) 平衡因子：一个结点的左子树的高度减去右子树的高度，可取-1、0、1三种值
(3) 平衡操作
3. 表达式树
4. 考题：2011-7、2012-4、2013-3(PDF中的分析有误，以上课讲解为准)、2013-6、2015-4、2018-6、2019-4、2019-6、2020-5、2017-41
-------------------------------------------------------------------------------------
第6讲 Huffman编码和Huffman树
1. Huffman编码和Huffman树
(1) Huffman编码
a. 前缀编码: 是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。
b. 树的带权路径长度(WPL)
c. 构造过程
(2) Huffman树
(3) 应用
2. 考题：2012-41、2013-4、2014-6、2015-3、2017-6、2018-5、2019-3、2020-42
-------------------------------------------------------------------------------------
第7讲 图的基本概念、存储、遍历、拓扑排序
1. 图的基本概念
(1) 有向图、无向图
(2) 度数（出度、入度）
(3) 简单图：不存在顶点到其自身的边，且同一条边不重复出现
(4) 路径、环、简单路径
(5) 无向完全图：任意两个顶点之间都存在边，有n个顶点的无向完全图有 n × (n - 1) / 2条边
(6) 有向完全图：任意两个顶点之间都存在方向护卫相反的两条弧，有n个顶点的无向完全图有 n × (n - 1) 条弧
(7) 稀疏图&稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，相对的概念。
2. 图的存储及基本操作
(1) 邻接矩阵：适用于稠密图，可存有向图、无向图。常用。空间复杂度：O(n^2)。无法存重边。
(2) 邻接表：适用于稀疏图，可存有向图、无向图。常用。空间复杂度：O(n + m)。可存重边。
(3) 邻接多重表，适用于稀疏图，可存无向图。不常用。空间复杂度：O(n + m)。可存重边。
(4) 十字链表，适用于稀疏图，可存有向图、无向图。不常用。空间复杂度：O(n + m)。无法存重边
(5) 三元组表，适用于稀疏图，可存有向图，无向图。常用于Bellman-Ford算法、Kruskal算法。空间复杂度：O(m)。可存重边。
3. 图的遍历
(1) 深度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)
(2) 广度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)
4. 拓扑排序
5. 考题：2011-8、2012-5、2012-6、2013-7、2013-8、2014-7、2015-5、2016-6、2016-7、2017-3、2017-7、2018-7、2020-6
-------------------------------------------------------------------------------------
第8讲 最小生成树、最短路、关键路径
1. 最小生成树
(1) Prim
(2) Kruskal
2. 最短路
(1) 单源最短路 Dijkstra
(2) 多源汇最短路 Floyd
3. 关键路径
4. 考题：2011-41、2012-7、2012-8、2013-9、2015-6、2015-42、2016-8、2017-42、2018-42、2019-5、2020-7、2020-8
-------------------------------------------------------------------------------------
第9讲 查找（一）
1. 查找的基本概念
(1) 平均查找长度 ASL = 每个元素 查找概率 * 找到第i个元素需要进行的比较次数 的和。
(2) 决策树(判定树)
2. 顺序查找法
(1) 一般线性表的顺序查找
a. 若每个元素查找概率相同，则 ASL(成功) = (1 + 2 + ... + n) / n = (n + 1) / 2
b. ASL(失败) = n或n+1，取决于代码写法。
(2) 有序表的顺序查找
a. 若每个元素查找概率相同，则 ASL(成功) = (1 + 2 + ... + n) / n = (n + 1) / 2
b. ASL(失败) = (1 + 2 + ... + n + n) / (n + 1) = n / 2 + n / (n + 1)
3. 折半查找法
(1) ASL = log(n + 1) - 1
4. 分块查找法
设共n个元素，每块s个元素，共b = n / s块。块内无序，块间有序。
(1) 顺序查找确定块：ASL(成功) = (s^2 + 2s + n) / (2s)，s = sqrt(n)时取最小值
(2) 二分查找确定块：log(n/s + 1) + (s - 1)/2
5. B树及其基本操作、B+树及其基本概念
(1) B树
[1] m阶B树，每个节点最多有m个孩子。
[2] 每个节点最多有m-1个关键字（可以存有的键值对）。
[3] 根节点最少可以只有1个关键字。
[4] 非根节点至少有m/2个关键字。
[5] 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
[6] 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
[7] 每个节点都存有索引和数据，也就是对应的key和value。
[8] 所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。
(2) B+树
[1] B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
[2] B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
[3] B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
(3) 参考链接：https://blog.csdn.net/Fmuma/article/details/80287924
6. 考题：2011-42、2012-9、2013-10、2013-42、2014-9、2015-7、2016-9、2016-10、2017-8、2017-9、2018-8、2020-10
-------------------------------------------------------------------------------------
第10讲 查找（二）
1. 散列（Hash）表
(1) 负载因子
(2) 哈希函数
[1] 除余法 h(x) = x % M
[2] 乘余取整法 h(x) = floor(A * x的小数部分)
[3] 平方取中法 先平方，然后取中间几位
[4] 基数转换法 换成其他进制，然后取其中几位
[5] ELFhash字符串
(3) 聚集和二级聚集
(4) 解决冲突的方式
[1] 开散列方法（拉链法）
[2] 闭散列方法（开放寻址法）
a. 线性探查法 d(i) = (d(0) + i * c) % M。易产生聚集问题。
b. 二次探查法。易产生二级聚集问题。
d(2i - 1) = (d(0) + i^2) % M
d(2i) = (d(0) - d ^2) % M
c. 随机探查法。易产生二级聚集问题。
d. 双散列探查法
2. 字符串模式匹配（KMP）
3. 查找算法的分析及应用
4. 考题：2011-9、2014-8、2015-8、2018-9、2018-41、2019-8、2019-9、