数据结构绪论
基本概念
- 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单元。
- 数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
- 抽象数据类型（ADT）是指一个数学模型及定义在该模型上的一组操作。
- 数据的逻辑结构：线性结构（线性表、栈、队列）、非线性结构（图、树）。
- 数据的存储结构：
- 顺序存储：可以实现随机存取，只能使用相邻存储单元
- 链式存储：不要求在物理上相邻，指针占用额外空间
- 索引存储：检索速度快，索引表占用额外空间，修改时还需要修改索引表，花费较多时间
- 散列存储：检索存储都很快，但如果散列函数不好，可能出现冲突，解决冲突需要额外时间和空间
- 算法的五个特征：有穷性、确定性、可行性、输入、输出。
- 算法要实现的目标：正确性、可读性、健壮性、效率与低存储量需求。
- 一般总是考虑最坏情况下的事件复杂度，以保证算法的运行事件不会比它更长。
- 常见的渐进时间复杂度：O(1)<(\log_2 n)<O(n)<O(n\log_2 n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
- 原地工作算法指算法所需的辅助空间为常量，即O(1)
- 非递归算法的执行效率通常高于递归算法。
线性表
顺序表示
顺序存储方式并非只能用于存储线性结构还能用于图和树的存储，如满二叉树的顺序存储。
链式表示
链式存储可以方便地表示各种逻辑结构，因为链式存储用指针表示逻辑结构，而指针的位置是任意的。顺序存储只能用物理上的邻接关系来表示逻辑结构。
单链表
头结点可以不设任何信息，也可以记录表长等相关信息，头结点指针域指向线性表的第一个元素结点。
单向循环链表，只有表尾的比只有表头的强。
双链表
单链表的插入、删除算法的主要时间耗费在前驱结点的查找上，而双链表可以很方便的找到其前驱结点。
双链表插入、删除结点算法的时间复杂度为O(1)
静态链表
需要分配较大的存储空间，因为静态链表用数组表示。
比较
对于按值查找，顺序表无序时，顺序表和链表的时间复杂度都是O(n)，顺序表有序时，可采用折半查找，顺序表的时间复杂度时O(log_2 n)
对于按序号查找，顺序表的事件复杂度是O(1)，链表的时间复杂度是O(n)
链表在空间分配上比线性表灵活。
栈和队列
栈
只允许在一端进行插入或删除操作的线性表。
将递归算法转换为非递归算法。通常需要借助栈来实现。
顺序存储
共享栈
对效率没有影响。
两个栈的空间相互调节。
链式存储
称为栈链。
不会出现栈满的情况
队列
顺序存储
循环队列
在不出现循环的情况下，队尾比队首大。
入队：队尾指针加1取模
出队：队首指针加1取模
队空状态（初始化）
先考虑存放一个元素的情况，再进行入队的逆运算。
队满状态
先考虑缺少一个元素的情况，再将一个元素入栈，建立队头队尾指针的关系。
链式存储
用链表形式存储时，删除元素从队头删除，一般情况下不需要求改队尾，但是如果队列中只有一个元素，删除队头后rear指针就没有了指向的元素，这时需要求改队尾指针为rear=front。
双端队列
输出受限
先写出选项给出的输出序列，再判断输入是否能满足该输出序列。
输入受限
先写出唯一的输入序列，在判断题目给出的输出序列是否能出现。
应用
栈的应用
括号匹配
表达式求值
递归算法
迷宫求解
进制转换
队列的应用
页面替换算法
树的层次遍历
图的广度优先搜索
解决速度不匹配、资源竞争问题（缓冲区）
特殊矩阵
对称矩阵
三角矩阵
三对角矩阵
稀疏矩阵
树
树的概念
树是边数比顶点数少1的连通图。
树的路径长度：树根到每个节点的路径长度的总和。
树的度数：树中节点的最大度数。
总节点数=总分支数+1，在许多计算中要利用此等式构造方程。
二叉树的概念
子树有左右之分。
二叉树可以为空，可以只有一个根节点，这两种树不是度数为2的树。
n_0=n_2+1
二叉树的最小高度为h=\log_2(n+1)
特殊二叉树
满二叉树
除最后一行外，所有的节点的度数都是2。
完全二叉树
除最后两行外，所有节点的度数都是2，倒数第二行靠前的节点度数都是2，靠后的节点度数都是1。
二叉排序树
左子树上所有节点的关键字均小于根节点上的关键字，右子树上所有关键字均大于根节点上的关键字。左子树和右子树又各是一棵二叉排序树。
平衡二叉树
任一节点左右子树深度之差不超过1。
存储
顺序存储
适用于满二叉树和完全二叉树，如果存放的不是这两种树，会浪费较多的存储空间。
链式存储
有数据域和左、右孩子指针
二叉树的遍历
先序、中序、后序
由先序遍历和中序遍历、中序遍历和后序遍历可以唯一地确定一棵树，先序遍历和后序遍历不能。
非递归
借助栈
层次遍历
借助队列
由遍历构造二叉树
线索二叉树
线索二叉树是一种物理结构。
引入线索二叉树是为了加快查找节点前驱和后继的速度。
中序线索化二叉树后，遍历不再需要借助栈，因为它的节点中隐藏了线索二叉树的前驱和后继信息。
n个节点的线索二叉树有n+1个线索。
标志域
0表示指针域指向左/右孩子
1表示指针指向前前驱/后继
不能解决的问题
因为没有指向根节点方向的指针，所以先序线索二叉树不能解决求先驱的问题，后续线索二叉树不能解决求后继的问题。
也正因如此，后序线索树的遍历仍需要栈的支持。
中序线索二叉树不存在这样的问题，因为先驱和后继都在下方。
森林
一棵树也可以称为森林。
存储
双亲表示法
孩子的指针指向双亲。
孩子表示法
将孩子用单链表连接起来。
孩子兄弟表示法
左指针指向第一个孩子，右指针指向兄弟。
森林、树、二叉树的转换
森林、树转换为二叉树：左指针指向第一个孩子，右指针指向相邻兄弟节点。
二叉树转换为树、森林同理。
树转换为二叉树，二叉树的根结点一定无右孩子。
应用
二叉排序树
若左子树非空，则左子树上所有结点关键字值均小于根节点的关键字的值。
若右子树非空，则右子树上所有结点关键字值均大于根节点的关键字的值。
左、右子树本身也分别是一棵二叉排序树。
删除
右子树空，用左子女填补。
左子树空，用又子女填补。
左右子树均不空，找中序第一个子女填补。
查找
对于高度为h 的二叉排序树，其插入和删除操作的运行时间都是O(h)，如果二叉排序树是一个只有左、右孩子的单支树，运行时间是O(n)，如果是平衡二叉树，运行时间是O(\log_2 n)
平衡二叉树
结点左右子树高度差为该结点的平衡因子。
构造
构造n层平衡二叉树所需的最小结点数为h_n=1+h_{n-1}+h_{n-2}, n_0=0, n_1=1
给的层数条件下，如果节点数最小，所有的非叶节点度都是1。
插入
在左孩子的左子树上插入新的结点，需要一次向右的旋转操作。
在右孩子的右子树上插入新的结点，需要一次向左的旋转操作。
在左孩子的右子树上插入新的结点，需要一次向左一次向右的旋转操作。
在右孩子的左子树上插入新的结点，需要一次向右一次向左的旋转操作。
插入的结点不一定是叶结点，因为可能会有平衡调整。
查找
含有n个结点的平衡二叉树深度为log_2 n，所有平衡二叉树的平均查找长度为O(log_2 n)
哈夫曼树
哈夫曼树是所有结点度为均0或m的树，m不一定为2。
用哈夫曼树可以设计出长度最短的二进制前缀编码。
任何编码都不是其他编码的前缀，这种编码称为前缀码。
对一组权值构造出来的哈夫曼树并不是唯一的。
不能仅依照长度来判断哈夫曼编码是否正确。
父节点的权值等于左右孩子的权值之和。
图
概念
- 线性表可以为空表，树可以为空树，但图不可以是空图。图的顶点集V一定非空，但边集G可以为空。
- 如果图G不存在重复边，不存在顶点到自身的边，则称图G为简单图。
- 多重图是跟简单图相对的概念。
- 完全图（也称简单完全图），是指任意两个顶点之间都有边的无向图，或任意两个顶点之间都有两个方向相反的两条弧的图。完全图属于简单图。
- 连通：两点之间路径存在。
- 如果无向图G中任何一对顶点都是连通的，则称图G为连通图。
- 无向图中的极大连通子图称为连通分量。
- 如果有向图G中任何一对顶点都是强连通（双向连通）的，则称图G为强连通图。
- 有向图中的极大连通子图称为强连通分量。
- 生成树是包含图中全部顶点的一个极小连通子图。非连通图可以生成森林。
- 无向图边的数量等于个顶点的度数之和。
- 边最少的无向图是树，边最少的有向图是环。
- 简单路径：顶点不重复出现。
存储
邻接矩阵
用一个一维数组存储顶点的信息，用一个二维数组存储边的信息。
稠密图适合用邻接矩阵表示。
表示带权有向图时，0和 \infty都不是有向边。
在一行中出现的次数表示出度，在一列中出现的次数表示入度。
邻接表
为图中每一个点建立一个单链表，结点表示依附于该顶点的边。
对有向图而言，结点表示以该边为尾的弧。
稀疏图适合用邻接表表示。
边表不包括顶点表。
顶点在边表中出现的次数之和表示该点的入度。
十字链表
用于存储有向图。
有顶点结点和弧结点，顶点结点的指针指向以该顶点为弧头、弧尾的第一个结点。
弧结点存储弧头、弧尾结点，指针指向与该弧弧头相同的下一条弧、与该弧弧尾相同的下一条弧。
邻接多重表
与十字链表类似，用来存储无向图。
遍历
基于邻接矩阵的遍历所得到的BFS序列和DFS序列是唯一的。
基于邻接表的遍历所得到的BFS序列和DFS序列不是唯一的。
广度优先
需要借助队列。
解决单源最短路径问题。
深度优先
类似树的先序遍历。
利用递归。
深度优先遍历可以判断图中是否存在回路。
图的连通性
如果图是连通的，从任意结点出发，一次遍历就可以访问途中所有顶点。如果图不是连通的，一次遍历只能访问到该顶点所在的连通分量。
应用
最小生成树
生成树是图的极小连通子图。
边的权值之和最小的生成树是最小生成树。
各边权值互不相等时，最小生成树是唯一的。 （这是充分不必要条件）
树的最小生成树是它本身。
prim算法
每次选一个顶点，加入到已构造的最小生成树中。
Kruskal算法
每次找权值最小且不形成环的边，时间复杂度为O(e\log_2e)，其中O(\log_2e)是并查集的时间复杂度。
最短路径
Dijkstr算法
每次得到一个点的最短路径。时间复杂度为O(n^2)
Floyd算法
每次尝试在原路径中加入中间点，用更短的路径代替原路径。时间复杂度为O(n^3)
拓扑排序
从没有前驱的顶点开始。
若一个顶点有多个直接后继（出度>1），则拓扑排序的结果通常不唯一。
连通图的一个顶点出度为0，其他所有顶点出度为1的，则这个图的拓扑序列唯一。（这是充分不必要条件，参考P222第19题）
关键路径
以下概念中，最迟\geq最早。
最早发生时间
起点到此点的最长路径。
最迟发生时间
起点到终点的最长减此点到终点的最长。
最早开始时间
起点到事件的最长。
最迟开始时间
起点到终点的最长减此事件到终点的最长。
关键路径
最迟开始时间=最早开始时间的活动所在的路径为关键路径。
如果关键路径有多条，减短所有关键路径，才能达到缩短工期的目的。
查找
顺序查找
平均查找长度的计算：概率*当前长度
在一般线性表的顺序查找中，如果查找成功，平均查找长度为$\text{ASL}{成功}=\frac{n+1}2；如果查找失败，查找长度为\text{ASL}{失败}=n+1在有序表的顺序查找中，无论查找成功还是失败，平均查找长度都是\text{ASL}=\frac{n+1}2顺序查找的缺点是当n$较大时，平均查找长度较大，效率低；优点是对存储没有要求，顺序存储或链式存储皆可。
折半查找（二分查找）
适用于有序表。要求顺序存储。
查找过程对应的判定树是一棵二叉排序树。
判定树也是一棵平衡二叉树。
查找过程对应的判定树中所有的左右子树结点数相差1或相等，同一判定树中取整规则需固定（只能左子树多结点多1或只能右子树结点数多1）。
折半查找成功时，平均查找长度为\text{ASL}=\log_2(n+1)-1，效率高于顺序查找。
时间复杂度为O(\log_2 n)
分块查找
将查找表分成若干子块，块内元素可以无序，块之间要求有序。每个块的最大关键字小于下一个块中的所有关键字。再建立一个索引表，索引表中每个元素含有各块的最大关键字和第一个元素地址。
分块查找先在索引表中确定待查记录所在的块，再在块中使用顺序查找。
当块的数量s=\sqrt n时，平均查询长度取最小值\sqrt n+1
B树
定义
符合以下条件的多叉树称为m阶B树：
- 除根结点外，每个节点至少\lceil{m/2}\rceil-1个关键字，至少\lceil{m/2}\rceil个分叉
- 任何结点的所有字数高度相同
- 关键字有序
查找
略。
插入
如果插入后关键字个数等于m，必须对结点进行分裂。
分裂方法：将中间位置（⌈m/2⌉）的元素插入到原结点的父结点中，父结点关键字也超过上限，继续分裂，直至分裂过程传到根结点导致B树高度增1。
删除
- 删除非根结点关键字，用直接前驱或后继根结点的关键字填补删除的关键字，转换成删除根结点关键字的问题
- 删除根结点关键字，如果删除后所在结点的关键字少于⌈m/2⌉ – 1
- 如果左兄弟或右兄弟关键字多于⌈m/2⌉ – 1个，找兄弟结点借一个关键字，即可完成删除过程
- 如果左兄弟和右兄弟都只有⌈m/2⌉ – 1个关键字，就把删除关键字后的结点、兄弟结点、父结点两者之间的关键字进行合并，如果合并后父结点关键字少于⌈m/2⌉ – 1个，就继续合并父结点、叔结点、爷结点
B+树
定义
符合以下条件的多叉树称为m阶B+树：
- 每个分支结点最多有m棵子树，除根结点外最少有\lceil{m/2}\rceil棵子树
- 结点分支数等于关键字数，结点的值是分支结点的最大值
- 叶节点包含全部关键字
- 任何结点的所有子树高度相同
- 关键字有序
B+树与B树的不同之处
结点的子树与关键字数量相等。
结点关键字数量限制与B数不同。
非叶结点仅起索引作用，叶结点包含全部关键字，。
B+树支持顺序查找，而B树不能。
B+树根结点可以链接起来，支持顺序查找。
应用
数据库索引。
散列表
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数。
任何设计出来的散列函数都不可能绝对地避免冲突。
理想情况下，对散列表查找的时间复杂度为O(1)
构造
散列函数的构造方法不用记。
处理冲突
发生聚集的原因是解决冲突的方法选择不当。
开放地址法
对于冲突，查找下一个空闲单元。
同义词在散列表中不一定相邻，中间可能有非同义词。
拉链法（链地址法、链接法）
把同义词存储在一个线性链表中。
性能
散列表的填充因子\alpha表示一个表的装满程度，即：
\alpha=\frac{\text{表中记录数}n}{\text{散列表长度}m}
串
模式匹配
求字串在主串中的位置
KMP算法
i指针不需要回溯，仅将字串向后滑动，滑动长度为最长相等前后缀长度。
next数组
next[0]=0，next[1]=1
next[n]=字符串前n字符号的最长相等前后缀长度+1。
失配后下次匹配时，j=next[j]
并查集
逻辑结构：集合
表示方式：森林
每个集合用一颗树表示，用一个长度为n的一维数组记录
元素值为父结点下标，根结点用负值表示
并(Union)
把一棵树作为另一棵树的根结点的子结点
不论是否优化时间复杂度都是：O(1)
并的优化
树很高时查找效率低，所以合并操作需要优化
用根结点的绝对值表示该集合元素的总个数
每次把小树作为大树的子结点
查(Find)
查找一个结点在哪个即可，可以找对应的树的根结点
判断两个结点书否属于是否属于同一个集合，可以根据是否属于同一个根结点来判断
Union优化前最坏的情况时间复杂度：O(n)
Union优化后最坏的情况时间复杂度：O(\log_2n)
应用
判断图的连通分量：构造并查集数组，查找有几个小于0的数
判断图是否有环：构造并查集，如果属于同一个集合的两个结点之间有边，就一定有环
Kruskal算法：用并查集避免出现环
三个应用本质上都是用并查集来判断顶点之间是否连通
红黑树
定义
红黑树是相对平衡的二叉搜索树
红黑树的特点：
- 结点是红色或黑色
- 根结点是黑色
- 叶结点是黑色，是失败结点
- 红色结点的孩子是黑色
- 从任何结点出发到所有空叶子的路径中黑色结点数量相等
助记：左根右，根叶黑，不红红，黑路同
性质
只有结点的路径最短，红黑交替的路径最长
红黑树可以保证最长路径不超过最短路径的两倍，所以说红黑树是相对平衡的二叉搜索树
优点：相对平衡；插入结点比较简单
插入
插入的新结点都是红色，如果不违法“不红红”的特征，就不用调整
如果违法“不红红”的特征，就要调整，看叔叔脸色行事
- 叔叔是黑色：旋转 + 染色
- LL：右单旋，父换爷 + 染色（原本的父和爷染色）
- RR：左单旋，父换爷 + 染色（原本的父和爷染色）
- RL：左右双旋，儿换爷 + 染色（原本的儿和爷染色）
- LR：右左双旋，儿换爷 + 染色（原本的儿和爷染色）
- 叔叔是红色：染色 + 变新（染色后爷结点视为新结点）
- 叔父爷染色，爷变新结点，再判断新结点是否违反红黑树特性；如果红色传递到根结点，直接涂黑即可
排序
概念
稳定性：如果相等的关键字在排序后次序不变，则称排序算法是稳定的。稳定性并不能衡量算法的优劣。
内部排序：在排序期间元素是全部放在内存中。内部排序算法在执行过程中通常要进行两部操作：比较和移动。
外部排序：排序期间元素无法全部同时存放在内存中，不许再内、外存中移动。
插入排序
在基本有序时速度较快 。
直接插入排序
每次处理未排序的第一个元素，将其向左移动到已排序元素的适当位置，重复此过程直到整体有序。
序列基本有序的情况下适合用直接插入排序。
最好情况是序列已经有序，时间复杂度为O(n)
平均和最坏情况的时间复杂为是O(n^2)
空间复杂度为O(1)
折半插入排序
将比较和移动分离。
比较次数比直接插入排序少。
时间复杂度：O(n^2)
希尔排序
每次循环选取一个步长(例如数组长度的一半)，将距离等于步长的元素作为一组，各组组内进行直接插入排序。下次循环步长-1，重复此过程直到步长为1，即可完成排序。
最好情况与直接插入排序相同，即序列已经有序，时间复杂度为O(n)
平均情况下时间复杂度约为O(n^{1.3})
最坏情况为逆序，时间复杂度为O(n^2)
空间复杂度为O(1)
不稳定。
交换排序
冒泡排序
从右往左比较相邻的两个元素，如果右边的元素小于左边，则交换位置，每次循环会把未排序的最小元素换到最左边，重复此过程直到整体有序。
有一种优化方式，是用flag记录此轮循环中是否发生过交换，如果一次都没交换，则说明排序已经完成，可以直接结束。考研408默认采用这种方式。
优化后的冒泡排序最好情况为序列已经有序，时间复杂度为O(n)
平均和最坏情况时间复杂度为O(n^2)
空间复杂度为O(1)
快速排序
每次选取一个元素作为枢轴pivot(例如最左边的元素)，将比枢轴小的元素换到左边，比枢轴大的元素换到右边，得到左右两个子序列，对两个子序列分别递归调用此方法，直到每个序列只有一个元素。
快速排序的辅助空间用于记录递归树，因此空间复杂度等于递归深度。
最好和平均情况时间复杂度为O(n\log_2n)，递归深度为\log_2n，空间复杂度为O(\log_2n)
最坏情况为序列已经按顺序或逆序排列，时间复杂度为O(n^2)，因为此时的枢轴不能将序列分为两个子序列，递归深度为n，空间复杂度为空间复杂度为O(n)
有一种优化的方式是取随机位置的元素作为枢轴，而不是第一个元素，这样可以避免最坏情况时间和空间复杂度过大的问题。考研408默认不采用这种方式。
每经过一趟排序，会有一个元素（枢轴）处于最终位置。
选择排序
简单选择排序
每次循环找到未排序的最小的元素，与未排序的第一个元素交换，重复此过程直到整体有序。
时间复杂度：O(n^2)
比较次数始终为n(n-1)/2
不稳定。
堆排序
堆的定义：根节点大于等于或小于等于孩子结点。
调整：从右到左，从下到上
建堆时间：O(n)
最好、最坏、平均时间复杂度：O(n\log_2 n)
不稳定。
归并排序
归并排序的思想是“分而治之”。
“分”的过程是如果元素数量大于1，则将序列分为尽可能等长的两个子序列。
“治”的过程是将子序列两两合并，合并后的序列内部是有序的，重复合并过程直到全部完成。
所有情况的时间复杂度均为O(n\log_2n)，空间复杂度为O(n)，辅助空间用于记录子序列。
归并排序可用于外部排序，数据占用的存储空间大于内存也能使用，因为子序列合并的过程不需要把全部数据读取到内存中。
基数排序
空间复杂度：O(r)
时间复杂度：O(d(n+r))，与初始状态无关。
只能对整数排序。
稳定。
内部排序比较
| 排序法 | 最好情况 | 平均情况 | 最坏情况 | 是否稳定 | 额外空间 | 备注 |
|---|---|---|---|---|---|---|
| 插入 | O(n) | O(n^2) | O(n^2) | 是 | O(1) | 大部分已排好序时较好 |
| 冒泡 | O(n) | O(n^2) | O(n^2) | 是 | O(1) | n较小时好 |
| 选择 | O(n^2) | O(n^2) | O(n^2) | 否 | O(1) | n较小时好 |
| 希尔 | O(n) | 约O(n^{1.3}) | O(n^2) | 否 | O(1) | 复杂度依赖于增长序列的函数，此数学问题尚未解决 |
| 快速 | O(n\log_2n) | O(n\log_2n) | O(n^2) | 否 | O(\log_2n)\sim O(n) | n较大时好 |
| 堆 | O(n\log_2n) | O(n\log_2n) | O(n\log_2n) | 否 | O(1) | n较大时好 |
| 二路归并 | O(n\log_2n) | O(n\log_2n) | O(n\log_2n) | 是 | O(n) | n较大时好 |
| 基数 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | 是 | O(r) | B是真数（0~9），R是基数（个十百） |
绝大多数内部排序只适用于顺序存储结构。
外部排序
外部排序通常采用归并排序方法。
增加归并路数可以减少归并次数，从而减少磁盘的I/O次数。
败者树
如果不用败者树，从m个元素中选择关键字最小的记录需要比较m-1次，每趟n个递归元素需要做(n-1)(m-1)次比较。
如果用败者树，比较次数就是这棵完全二叉树的深度\lceil\log_2 n\rceil，每趟n个递归元素需要做\lceil\log_2 n\rceil\cdot m次比较。
置换-选择排序
生成外部排序初始归并段。
在外部排序中，输入/输出缓冲区就是排序的内存工作区，做m路平衡归并排序需要m个输入缓冲区和1个输出缓冲区。
做m路平衡归并排序，为实现输出/内部归并/输出的并行处理，需要设置2m个输入缓冲区和2个输出缓冲区。
最佳归并树
设计m路归并的优化方案。
是将哈夫曼树推广到m叉树的情形，记录数最多的最晚归并，缺额的归并段留到最后。
回复 匿名 取消回复