考研期间做的数据结构与算法的笔记，实现了我们遇到的一些基本数据结构与算法。主要参考清华邓俊晖老师的课件以及一些上科大算法课的课件。希望能给同样需要学习这门课的同学一些参考
（线性表的顺序存储结构）
循环队列必须损失一个存储空间，用来区分队空和队满状态。一般定义队头指针指向队头元素的前一个位置，队尾指针指向队尾元素
链队的特点就是理论上不存在队列满上溢的情况。队头指向链头，队尾指向链尾
思考：栈结构适用于具有局部相关的数据
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
pop the object with the highest priority
 |
 |
容易想到的可选数据结构有向量，列表，多个列表，或者基于BBST。但是向量和列表对于有些操作的时间复杂度为O(n)，而BBST的功能远远超出优先队列的要求，并不需要维护所有元素之间的全序关系。应该有结构更为简单，维护成本更低的方法，使得插入和删除的为O(logn)，getmax为O(1)。这就是完全二叉堆！！！
这里用向量来存储完全二叉堆,会用到完全二叉树的性质来访问节点的父亲和孩子。 Implementation using arrays
Operations
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
散列表是普通数组概念的推广，当关键字的全域比较小时，直接寻址是简单而有效的，通常用数组（或者称为直接寻址表）。但是当全域很大时，实际存储的关键字集合K相对于全域U可能很小，用数组就会造成大量的空间浪费，空间利用率低。
这里先简单介绍直接寻址表和散列表:
关于下面第四项均匀性，做出如下解释:
If two objects are randomly chosen, there should be only a one-in-M chance that they have the same value from 0 to M – 1
(相当于任意随机选一个关键字，他等可能的落入对应的桶中，与确定性不同的是确定性是关键字已经给定)
堆积现象
查找成功时:
查找不成功时
不同的书可能定义不一样
空树的高度为-1，只有一个节点的树高度为0。
对于度为m的树，叶节点的个数为n0 = 1+
A backtracking algorithm for stepping through a tree（回溯法）:
Each node is visited multiple times in such a scheme（节点会被多次访问）
Displaying information about directory structures and the files contained within
The easiest implementation is to use a queue:
设度数为0,1,2的节点各有n0,n1,n2个,则：
高度(或者深度)为k的二叉树,则:
有n个节点的完全二叉树,若i是某个节点a的编号(编号的范围为1~n)
站在图的角度去看待先序，中序，后序遍历二叉树时，其实都是基于深度优先遍历。区别在于对于根节点的访问时间于子树访问时间的相对关系。
由先序或者后序任一种遍历加上中序遍历可以唯一确定一颗二叉树。同时，由中序遍历和层次遍历也能唯一确定一颗二叉树。原理为:
- 先序（后序）遍历确定根
- 中序遍历确定左右子树
关于单独给出先序遍历的序列，可以确定的不同形态二叉树的个数为Catalan数。这个用分治法的思路很好证明（即用递推公式）。
Catalan数：1/(n+1) * C(n, 2n)
树在转化成二叉树时，非终端节点的孩子中的最右子节点的右指针为空，对应二叉树中根节点的右孩子指针也为空。也就有 所有空右指针个数=非终端节点数+1（根除了其最右孩子的右指针为空外，自己的也为空）； 每一个非终端节点都对应了其相应二叉树中一个右指针为空的节点减一。
In a binary search tree, we require that
all objects in the left sub-tree to be less than the object stored in the root node
all objects in the right sub-tree to be greater than the object in the root object
the two sub-trees are themselves binary search trees
 |
 |
 |
 |
A binary search tree is said to be AVL balanced if:
 |
 |
 |
等价BBST与旋转调整
 |
 |
 |
对于失衡情况，从最深的那个失衡节点开始考虑推导最方便，下面的插入删除的失衡情况的复盘就是这么得来的
| zag和zig | zigzag和zagzig | 实现 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
哈夫曼树又叫做最优二叉树。他的特点是带权路径最短。
前缀码:任一字符的编码都不是另一字符编码串的前缀;前缀码与树的联系:根通往任一叶子节点的路径都不可能是通往其余叶子节点的子路径
哈夫曼编码算法流程:
哈夫曼树的构造算法:
While priority queue contains two or more nodes
通过遍历哈夫曼树得到哈夫曼编码
Perform a traversal of the tree to obtain new code words
按秩合并 : 对于每个节点，维护一个秩，他表示该节点的高度的一个上界。在使用按秩合并策略的UNION操作中，我们可以让具有较小秩的根指向具有较大秩的根。
特点:
路径压缩 : 在FIND-SET操作中，使查找路径中的每个节点指向根。由于rank表示的是高度的上界，则此操作不改变节点rank。
带路径压缩的按秩合并的分析:
时间复杂度:
深搜与广搜的时间复杂度相同，只是访问顶点的顺序不同。而且图的遍历的过程实际上是对每个顶点查找其邻接顶点的过程。其时间复杂度与采用的存储结构有关。当用邻接矩阵时的时间复杂度为O(n^2)，用邻接表时为O(n+e)。
DFS生成的生成树比BFS的高度相等或者更高。（可以想象BFS生成树为原图的一个子图，在其上面加边用DFS得到的生成树只可能更高）。
边分类:
| 括号引理 | BFS : 队列 | DFS : 栈 |
 |
 |
 |
| 通用算法 | 统一框架 | 统一框架 |
 |
 |
 |
属于贪心算法,MST是图的极小联通子图。
prim 算法只与顶点数有关系与边数没有关系，适用于稠密图
利用优先级排序的模版
| 极短跨边 | 极长环边 |
 |
 |
| 算法 | 实现 |
 |
 |
主要由最短边的选取算法上，所以该复杂度复杂度与顶点数无关，由边数决定。适用于稀疏图
| 策略 | 算法框架 |
 |
 |
| 正确性 | 复杂度 |
 |
 |
注意 MST!=SPT 两者的优化方向并不一样 （形象的理解就是生成MST的过程是全面扩张，生成SPT的过程是以某个点为中心按路径长度发散）
属于贪心算法 按路径长度递增来产生一个点到其他所有点的最短路径。（从初始点按路径长度扩张）
核心:
1. 被选中的节点全部是已经确认了到s的最短路径的（途径的节点全部在已被选中的节点集中）--这一点很重要
2. 选取新的节点时，被选的新节点不可能经过其他未被选节点到s的路径最短。（新节点到s的路径只经过被选中的节点）
3. 新的节点加入时，只影响其邻居节点到s的最短路径
应用条件：边不能有负数（由其贪心的本质决定，认为其他任何选择都会付出更大的代价）
| 最短路径性质 | SPT与MST的优化方向不一样 |
 |
 |
| 算法 | 实现 |
 |
 |
Floyd算法是一个经典的动态规划算法。
应用条件：可以有负边但是不能有负权回路（如果有负权环，那么最短路将无意义，因为我们可以不断走负权环，这样最短路径值便成为了负无穷。）
参考链接：https://houbb.github.io/2020/01/23/data-struct-learn-03-graph-floyd
| 最优解的结构特征 | 递归实现 |
 |
 |
| 动态规划 | 实现 |
 |
 |
所有点对之间的最短距离,应用:搜索图的中心点
有向无环图可以拓扑排序，其邻接矩阵没有明显特征，但是如为三角矩阵，则一定可以拓扑排序
Dependency between tasks: one task is required to be done before the other task can be done Dependencies form a partial ordering
Given a set of tasks with dependencies, is there an order in which we can complete the tasks?
A graph is a DAG if and only if it has a topological sorting
Proof strategy:
Such a statement is of the form a ↔ b and this is equivalent to:
a → b and b → a
First, we need a two lemmas:
Idea:
implement:
Therefore, the run time of a topological sort is:∂
and the memory requirements is Q(|V|)
The critical time of each task is the earliest time that it could be completed after the start of execution
The critical path is the sequence of tasks determining the minimum time needed to complete the project:
If a task on the critical path is delayed, the entire project will be delayed
（事件为顶点,活动为边）
事件的最早开始时间 = 该事件发出的活动的最早开始时间
事件的最迟发生时间-以它为结束点的活动的持续时间 = 该活动的最迟发生时间
若某条弧的最早和最迟发生时间相等,则这条弧为关键活动
若某些活动不为关键路径共享，减少他并不能影响其他关键路径，总时间仍然不变。
复杂度类P即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有可以在多项式时间内验证它的解是否正确的决定问题组成，或者等效的说，那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合。很可能，计算理论最大的未解决问题就是关于这两类的关系的：P和NP相等?
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
通过将问题P的求解归约为对问题Q的求解，就可以利用问题Q的易求解性来证明P的易求解性。一般，当P可以多项式时间归约到Q，说明Q问题比P问题更难。
 |
 |
NP-complete
NP-hard
迭代算法一般较为常见，递归算法更为直观。因为递归算法需要大量空间资源，所以经常需要将其改写成迭代算法，这里为体现算法的思想，我主要考虑以递归为出发点的思想来理解算法。
当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个重要特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句。于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。因此，只要有可能我们就需要将递归函数写成尾递归的形式。
以下为递归算法的两种主要思想：
| 数据结构 | 问题名称 | 问题描述 |
|---|---|---|
| 数组 | Max2 | 从数组区间A[lo,hi)中找出最大的两个整数A[x1]和A[x2] |
朴素的递归算法(减而治之或分而治之)之所以效率低，是因为他们反复求解相同的子问题。
动态规划的原理:
最优子结构性质 : 问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
如何发觉最优子结构?这里给出一个通用模式:
重叠子问题 :
重构最优解
动态规划有两种等价的实现方法:
为构建动态规划的解决方案,一些必要的过程:
例子:
| 数据结构 | 问题名称 | 问题描述 |
|---|---|---|
| 串 | LCS | 求两个子序列的最长公共子序列 |
如在快排中随机选取pivot
有一个问题需要说明：关于用递归实现快排时，如果每次先处理较短的分区能不能降低递归次数和递归栈的深度。我对于这个问题的理解是，都不能，这和网上的很多理解以及严慧敏老师书中的理解不一样。因为当我们直接分析快排的递归树时，一个节点代表一次递归调用，树的高度代表递归栈的深度，不论怎么调用，其实深度和次数都是不变的。
简介：
| 算法名称 | 类别 | 算法描述 | 稳定性 | 空间复杂度 | 时间复杂度（最坏） | 时间复杂度（最好） | 时间复杂度（平均） |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | 交换排序 | 从前向后比较相邻的两个元素,逆序就交换，每次都能让一个最大(或者最小)的元素就位 | 是 | O(1) | O(n^2) | O(n) | O(n^2) |
| 插入排序 | 插入排序 | 把序列看成 sorted[0,)+unsorted[r,n) 两部分,把l[r]插入到有序部分的合适位置 | 是 | O(1) | O(n^2) | O(n) | O(n^2)或者O(n+I)其中I为逆序对数 (详见清华大学PPT) |
| 二路归并排序 | 归并排序 | 利用分而治之的思想,将整个序列平均分为前后两个序列排序的子问题，递归merge | 是 | O(n) | O(nlogn) | O(nlogn) | O(nlogn) |
| 基数排序 | 基数排序 | 根据关键字位数设计d个桶，根据高位优先或者低位优先将每项分配到对应的桶，然后再收集，经过d次分配收集之后就有序了 | 是 | O(rd) rd为关键字一位的取值范围 | O(d*(rd+n)) n为关键字个数 | O(d*(rd+n)) | O(d*(rd+n)) |
| 快速排序 | 交换排序 | 每次选择一个元素作为pivot，经过一次迭代将其归位。把序列分成前后两个序列，采用分而治之的思想继续递归既可 | 否 | 迭代版本为O(1) 递归版本为O(logn) | O(n^2) | O(nlogn) | O(nlogn) |
| 一般选择排序 | 选择排序 | 从未排序的元素中挑选最大者,并使其就位 | 否 | O(1) | O(n^2) | O(n^2) | O(n^2) |
| 堆排序 | 选择排序 | 利用完全二叉堆的性质排序 | 否 | O(1) | O(nlogn) | O(nlogn) | O(nlogn) |
| 希尔排序 | 插入排序 | 缩小增量排序 | 否 | O(1) | O(n^1.3) | O(n^1.3) | O(n^1.3) |
算法分析：
| 算法描述 | 算法分析 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
。。。。
| 算法名称 | 问题描述 | 算法描述 | 时间复杂度 |
|---|---|---|---|
| LCS | 最长公共子序列 | ||
| KMP | 字符串模式匹配 |
这里包含了我整理时用到的所有课件。
这是我写的代码部分生成的doxygen文档介绍 http://howie.diskstation.me:8000/