数据结构学习笔记

以下 H2 标题均为 B站视频标记使用的片段。B站视频链接

第一讲基本概念：1.1.1 至 1.3.3#

主要介绍了数据组织、空间使用、算法效率和抽象数据类型。由此引入，提出了算法复杂度的概念。以最大子序列和的问题从O(N^3)到O(N^2)、再到O(NlogN)以及O(N)表示算法的重要性。

第二讲线性结构：2.1.1 至小白专场：多项式乘法与加法运算③#

顺序存储结构：线性表#

顺序存储结构直接表示：x^2000如何表示？——空间占用大。
顺序存储结构表示非零项：(ai, i)二元组的集合，结构数组表示。——相加：从头开始，比较两个多项式当前对应项的指数（双指针）。
链表结构存储非零项：每个结点存储非零项。

线性表是由同类型数据元素构成有序序列的线性结构：建表、插入元素、删除元素

链式存储实现：不要求逻辑上相邻的元素物理上也相邻。插入、删除不需要移动数据元素

主要操作：求表长、查找（按序号查找、按值查找）、插入、删除

广义表：线性表的推广，元素不仅可以是单元素，也可以是另一个广义表
多重链表：结点的指针域会有多个。

堆栈#

特点：先入后出。是具有一定操作约束的线性表，只在栈顶做插入（push）、删除（pop）。

组成：一个一维数组、一个记录栈顶元素位置的变量

链表堆栈实现 - 往前插入/弹出。

中缀表达式转化为后缀表达式

数字优先输出，运算符号则等待而看后面运算符号的优先级。同优先级先进的先抛出计算。
有括号的情况：左括号优先级高，但左括号已经在栈内时降低其优先级，直到碰到右括号时将栈内括号范围内全部抛出。

alt text

队列#

特点：先入先出。只能在一端插入，而在另一端删除。

组成：一个一维数组、记录队列头位置的front、记录队列尾位置的rear

循环队列 - 如何判定是否满？

队列留出一个空余位置
使用额外标记（size/tag）

链式存储实现：使用单链表，插入和删除分别在链表两头（末尾位置不能做插入front指针）。front为null时队列为空。

多项式加法运算#

主要思路：相同指数的项系数相加，其余部分进行拷贝。

实现：采用不带头结点的单向链表，按照指数递减的顺序排列各项。双指针比较指数大小相加。

第三讲树(上)：3.1.1 至小白专场：树的同构②#

树：n个结点构成的有限集合。n=0时，称为空树。（树是最小连通图）

对于任一非空树，具备性质：

有根结点r
其余结点可分为m个互不相交的有限集，其中每个集合本身又是原来树的子树

另有性质

子树是不相交的
除了根结点外，每个结点有且仅有一个父结点
一棵N个结点的树有N-1条边

树的表示#

一般表示法（结构一致，但是一定会造成空间浪费）
儿子-兄弟表示法（两个指针域，左儿子右兄弟）顺时针旋转45°后成为二叉树。

二叉树#

可以看作一个有穷的结点集合，集合可以为空。若不为空，则由根结点、左子树、右子树构成。

特殊二叉树#

斜二叉树（只有左子树或只有右子树）
完美二叉树（满二叉树）
完全二叉树（满二叉树，但在编号完整的情况下允许缺叶结点即叶结点层允许从右往左缺失结点）

二叉树的性质#

一个二叉树第i层的最大结点数为2^(i-1)，i>=1
深度为k的二叉树有最大结点总数为2^(k-1)，k>=1
对任何非空二叉树，若n0表示叶结点的个数，n2是度为2的非叶结点的个数，那么n0=n2+1。

二叉树的遍历#

先序遍历：根、左子树、右子树
中序遍历：左子树、根、右子树
后序遍历：左子树、右子树、根
层次遍历：从上到下、从左到右

二叉树的存储结构#

顺序存储结构：左儿子下标是父下标的两倍（前提是2i <= n），右儿子下标是左儿子下标+1（前提是2i+1 <= n）。但一般二叉树采用这种结构会造成空间浪费。
链表存储：同上儿子兄弟表示法

二叉树的遍历访问流程#

先序遍历：访问根结点、先序遍历其左子树、先序遍历其右子树
中序遍历：中序遍历其左子树、访问根结点、中序遍历其右子树
后序遍历：后序遍历其左子树、后序遍历其右子树、访问根结点

遍历过程中经过结点的路线一样，只是访问各结点的时机不同。

中序遍历非递归遍历算法：使用堆栈。

遇到一个结点，压栈，遍历其左子树
左子树遍历结束后，弹出这个结点并访问
按右指针继续中序遍历该结点的右子树

改为先序遍历 -> 第一次遇到它时即访问。

层序遍历：核心问题 - 二维结构的线性化需要一个存储结构保存暂时不访问的结点

队列实现：遍历从根结点开始，首先将根结点入队，然后执行循环：结点出队、访问该结点、其左右儿子入队

由两种遍历序列（必须有中序遍历）可以确定一个二叉树。

建树#

判定根：在子结点中没出现的结点即为根结点。
判定两个树是否同构：都是空即同构、一边空一边不空即不同构、元素值不一样即不同构、后续左右子树递归继续判定。

第四讲树(中)：4.1.1 至小白专场：是否同一棵二叉搜索树③#

二叉搜索树#

一棵二叉树，可以为空，如果不空，则：

左子树所有键值小于根结点的键值
右子树所有键值大于根结点的键值
左、右子树都是二叉搜索树

特点：

最大元素一定在最右边
最小元素一定在最左边

删除结点时左右都有子树 = 取右子树最小值替代或取左子树最大值替代

平衡二叉树#

搜索树结点不同的插入次序，将导致不同的深度和平均查找长度ASL。

平衡因子BF(T) = hL-hR，分别为左、右子树的高度。

平衡二叉树（AVL树）：空树，或任意结点的平衡因子的绝对值不超过1。

高度为h的平衡二叉树的最小节点数：nh=F(h+2)-1。节点数为n的AVL树的最大高度为O(log2n)。

平衡二叉树的调整#

麻烦结点在发现者右子树的右边，因而叫RR插入，需要RR旋转（右单旋）。
麻烦结点在发现者左子树的左边，因而叫LL插入，需要LL旋转（左单旋）。
多个平衡处被破坏，考虑最下方的调整即可

麻烦结点在发现者左子树的右边，因而叫LR插入，需要LR旋转。新的中间结点应该为三个结点中的中间值。
麻烦结点在发现者右子树的左边，因而叫RL插入，需要RL旋转。新的中间结点应该为三个结点中的中间值。

有时候插入时树结构不动，但平衡因子依然需要改变。

判断二叉搜索树是否相同#

根据两个序列分别建树，再判别树是否一样
不建树判别：递归分堆判断
建一棵树，再判别其他序列是否与该树一致

3 关键问题：搜索树表示、建搜索树、判别序列是否与搜索树一致 -> 在树中按顺序搜索序列中的每一个数，若某次搜索中遇到前面未出现的结点则不一致

第五讲树(下)：5.1.1 至小白专场：File Transfer④#

优先队列：特殊的队列，取出元素的顺序是依照元素的优先权大小

堆#

使用完全二叉树进行存储。
根结点是最大/小值。

堆的两个特性：结构性、有序性

最大堆#

插入：将新增结点插入到其父结点到根结点的有序序列中。
删除：取出根节点（最大值）元素，同时删除堆的一个结点。用最大堆中的最后一个元素从根节点开始向上过滤下层结点。
建立：将N个元素按输入顺序存入，满足完全二叉树的结构特性；然后调整各结点位置，满足最大堆的有序特性。

哈夫曼树#

定义：

带权路径长度（WPL）：设二叉树有n个叶结点，每个叶结点带有权值w，从根结点到每个叶结点的长度为l，则每个叶结点的带权路径长度和为wl的总和。
哈夫曼树/最优二叉树：WPL值最小的二叉树。

构造：

每次把权值最小的两棵二叉树合并。

特点：

没有度为1的结点。
n个叶节点的哈夫曼树共有2n-1个结点。
哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树。
对同一组权值，会有不同构的两棵哈夫曼树。

进行不等长编码#

避免二义性 - 前缀码：任何字符的编码都不是另一字符编码的前缀。即应当字符只在叶结点上。

一直找频数最小的合并形成新结点，最终形成的即是哈夫曼树（最优编码）。

集合#

查找集合：一路寻找元素的根结点。
并运算：分别找到两个元素根结点，若不同根则将一个根结点的父结点指针设置成另一个根结点的数组下标。尽量把小的集合并入大的集合内。

堆创建#

堆插入：从叶结点不断向上，寻找应当插入的位置。

按秩归并对于union的改进：比树高/比规模
路径压缩对于find的改进：先找到根，把根变成X的父结点，再返回根

第六讲图(上)：6.1 至小白专场：如何建立图⑥#

图#

图所表示的是“多对多”的关系。包含一组顶点（用Vertex表示其集合）和一组边（用Edge表示其集合）

在程序中表示图：使用邻接矩阵：

使用邻接矩阵G[N][N]，该矩阵对称（将一条边存了两次）
用一个长度为N(N+1)/2的一维数组存储，则G(ij)在A中对应的下标为(i*(i+1)/2 + j)，一条边只需要存一次。对于网络，只需要把G[i][j]的值定义为边对应的权重即可。

优点：直观简单好理解，方便检查是否存在边，方便查找任一顶点的所有邻接点，方便计算任一顶点的度（从该点发出的边个数叫出度，指向该点的叫入度）对于有向图，对应行非零元素个数为出度，对应列非零元素个数为入度。

缺点：浪费空间 - 存稀疏图有大量无效元素；浪费时间

使用邻接表：

G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。一条边必定会被存储两遍。

优点：方便找任一顶点的所有邻接点；节约稀疏图的空间；方便计算任一顶点的度（仅无向图），对有向图则只能计算出度
缺点：不好检查任一顶点之间是否存在边

图的遍历#

深度优先搜索（DFS）#

类似于树的先序遍历。若有N个顶点、E条边，用邻接表存储图的时间复杂度是O(N+E)，用邻接矩阵存储图的时间复杂度是O(N^2)。

广度优先搜索（BFS）#

弹出时将与其直接相连的点压到队列中，以此类推，将所有点都遍历一次。若有N个顶点、E条边，用邻接表存储图的时间复杂度是O(N+E)，用邻接矩阵存储图的时间复杂度是O(N^2)。

图不连通时#

连通：从V到W存在一条无向路径，称为连通
回路：起点等于终点的路径
连通图：任意两个节点均连通
连通分量：无向图的极大连通子图
（有向图）强连通：有向图中顶点V和W之间存在双向路径，则称V和W强连通
（有向图）强连通图：有向图中任意俩顶点均强连通
（有向图）弱连通图：有向图中任意俩顶点均连通

对每个顶点遍历，若未访问过则调用BFS/DFS方法。

第七讲图(中)：7.1.1 至小白专场：哈利?波特的考试④#

最短路径问题#

在网络中，求任意两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。此即为最短路径，第一个顶点为源点，最后一个顶点为终点。

单源最短路径问题：从某固定源点触发，求其到所有其它源点的最短路径
多源最短路径问题：求任意两个顶点间的最短路径

无权图的单源最短路算法#

按照递增的顺序找出到各个顶点的最短路。

有权图的单源最短路径算法#

Dijkstra 算法

令S={源点s+已经确定了最短路径的顶点vi}
对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过s中的顶点，即路径s-v的最小长度。（前提是路径是按照递增的顺序生成）

方法：

直接扫描所有未收录顶点（对稠密图效果好）
将dist存在最小堆中（对稀疏图效果好）

多源最短路算法#

直接将单源最短路算法调用V遍
Floyd算法

第八讲图(下)：8.1.1 至图之习题选讲-旅游规划②#

最小生成树#

是一棵树，无回路，V个顶点有V-1条边
是生成树，包含全部顶点，V-1条边都在图里（生成树中任加一条边都一定构成回路）
边的权重和最小

贪心#

每一步都要最好的
权重最小的边
需要约束：只能用图里有的边；只能正好用掉V-1条边；不能有回路

Kruskal算法 - 将森林合并成树#

拓扑排序#

拓扑序：如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序
获得一个拓扑序的过程就是拓扑排序
AOV如果有合理的拓扑序，则必定是有向无环图

关键路径问题#

AOE网络

一般用于安排项目的工序
关键路径：由绝对不允许延误的活动组成的路径

第九讲排序(上)：9.1.1 至 9.4.3#

简单排序#

前提：N是正整数、只讨论基于比较的排序、只讨论内部排序、稳定性（任意两个相等的数据，排序前后的相对位置不发生改变）
没有一种排序是任何情况下都表现最好的。

冒泡排序#

反复对比相邻元素大小，交换位置。优势：稳定，适用于单向链表等结构

冒泡排序

添加flag标记，初始值为0，当有一趟排序时flag=1。结束后若flag==0则已经有序，直接跳出排序流程。

最好情况：顺序 T=O(N)，最坏情况：逆序 T=O(N^2)

插入排序#

摸牌 - 寻找空位 - 落位

最好情况：顺序 T=O(N)，最坏情况：逆序 T=O(N^2)

时间复杂度下界#

对于下标i<j，若Ai>Aj，则称(i,j)是一对逆序对。交换两个相邻元素正好消去一个逆序对。

插入排序：T(N,I)=O(N+I)。如果序列基本有序，则插入排序简单而高效

定理：任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对。
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为O(N^2)。 - 要提高算法效率，必须每次消去不止一个逆序对、每次交换相隔较远的两个元素。

希尔排序（Shell sort）#

使用5间隔的序列进行排序，然后使用3间隔的序列进行排序，再做1间隔的序列的排序。

即定义增量序列 Dm -> D(m-1) -> … -> 1

最坏情况下，T=O(N^2)。增量元素不互质，小的增量可能不起作用。

Hibbard 增量序列：Dk = 2^k-1，相邻元素互质。最坏情况T=O(N^(3/2))
Sedgewick 增量序列：{1,5,19,41,109}… 9*(4^i)-9*(2^i)+1 或 4^i-3*(2^i)+1

堆排序#

实质上是对选择排序的改进。

算法1#

建最小堆
遍历数组，从堆中删除最小值并赋到temp中
将temp转移到result

时间复杂度为O(nlogn)，但需要额外O(n)的空间，且复制元素也要时间。

算法2#

建最大堆
循环，把根节点放到当前堆的最后一个元素，然后把剩下的元素继续调整为最大堆
定理：堆排序处理N个不同元素的随机排列的平均比较次数是2NlogN-O(NloglogN)。
实际效果可能不如用Sedgewick增量序列的希尔排序。

归并排序#

核心：有序子列的归并

递归算法：分而治之#

稳定。每次递归后需要free使用的temp空间。

非递归算法#

一趟归并，稳定，平均复杂度为O(nlogn)，但需要O(n)的额外空间。

伪代码

第十讲排序(下)：10.1.1 至排序之习题选讲Sort with Swap(0,*) ②#

快速排序#

在所有元素中选中一个作为主元，把原来的数字集合按较主元的大小分为两大块。
递归。

问题：主元如何选择？独立子集怎么分？

最好情况：每次主元总是在数组中间，T=O(NlogN)

选主元#

令pivot=A[0] -> O(N^2)
随机取pivot -> rand函数不方便
三数取中法：从数组的首、尾、中各取一个元素，选择这三个元素的中间值作为基准。* 优化实践：可以将中间值换到数组的倒数第二个位置，最小值换到最小位，最大值换到倒数第一个位置。

快速排序的问题#

用递归
对小规模数据可能还不如插入排序快

子集划分#

基数排序，左右各两个下标i、j，直到都发现相反于pivot的指针就将二者交换后继续。
若有元素正好等于pivot：停下来交换√；不理它

表排序#

你的每一个待排结构都是庞大的结构。

间接排序：在排序过程中，不移动原始数据本身，而是移动一个指向原始数据的“索引”或“指针”数组。

定义一个指针数组作为“表”
应用标准算法对指针数组排序

物理排序：N个数字的排列由若干个独立的环组成。

最好情况：初始即有序、最坏情况：有[N/2]个环，每个环包含2个元素，T=O(mN)

基数排序#

LSD算法：次位优先
MSD算法：主位优先，先为主位建桶

排序算法的比较#

排序算法的比较

第十一讲散列查找：11.1.1 至散列查找之习题选讲-Hashing - Hard Version#

散列表#

查找的本质：已知对象找位置。

有序安排对象：全序、半序
直接算出对象位置：散列

散列查找法的基本工作：

计算位置：构造散列函数确定关键词存储位置
解决冲突：应用某种策略解决多个关键词位置相同的问题

时间复杂度几乎是常量O(1)。

装填因子：设散列表空间大小为m，填入表中元素个数是n，则称a=n/m为散列表的装填因子。

散列函数的设计方法#

计算简单，以便提高转换速度
关键词对应的地址空间分布均匀，以尽量减少冲突

数字关键词的散列函数设计#

直接定址法：取关键词的某个线性函数值为散列地址
除留余数法：把关键词通过求余运算进行转换
数字分析法：分析数字关键字各位上的变化情况，取比较随机的位作为散列地址
折叠法：把关键词分割成位数相同的若干部分，然后叠加
平方取中法：将大数平方，取中间几位

字符关键词的散列函数设计#

ASCII码加和法
前三个字符移位法（可能有很大的空间浪费）
移位法：二进制移位

散列查找的冲突处理#

换个位置：开放定址法，一旦产生冲突则按某规则去寻找另一空地址 - 线性探测、平方探测、双散列
同一位置的冲突对象组织在一起：链地址法

线性探测法：以增量序列循环试探下一个存储地址。
平方探测法：不一定能找到空位，但是能避免聚集问题。（如果散列表长度是4k+3形式的素数，则一定可以探查整个散列表空间）
双散列探测法：h2(key) = p-(key mod p)
再散列：当散列表元素太多时，查找效率会下降，此时加倍扩大散列表。实用最大装填因子一般取[0.5, 0.85]。
分离链接法：把所有有冲突的元素用链表串在一个单链表中

散列表的性能分析#

平均查找长度ASL用来度量散列表查找效率，又分为成功和不成功。
关键词的比较次数取决于产生冲突的多少：
- 散列函数是否均匀。
- 处理冲突的方法。
- 散列表的装填因子a。

线性探测法的查找性能#

平方探测法和双散列探测法的查找性能#

分离链接法的查找性能#

总结#

散列法是一个以空间换时间的方法，对关键字的存储是随机的、不便于顺序或范围或最大最小值查找关键字。

开放地址法：散列表是一个数组，存储效率高，随机查找；容易产生聚集。
分离链接法：链表部分的存储效率和查找效率都比较低；删除操作比较容易实现；不均衡的链表长度会使得查找效率严重下降。

学习笔记