中国大学MOOC(慕课)：浙江大学-陈越、何钦铭-《数据结构》笔记。
代码库：对应的学习资料，以及自己写的数据结构算法题的代码。
持续更新。
第一部分 基本概念
数据结构和算法的基本知识。
1.1 什么是数据结构
数据结构包含哪几个部分，互相之间的关系。
1.2 什么是算法
时间复杂度和空间复杂度。判断时间复杂度的小窍门。
1.3 最大子列和问题
第二部分 线性结构
2.1 线性表
举例说明线性表的应用场景。
线性表的抽象数据类型描述。
线性表的顺序存储结构（数组）和链式存储结构（链表）的实现。
以及两种不同的事项方式下，各项基本操作的实现。
2.2 堆栈
堆栈和线性表的区别。
堆栈的抽象数据类型的描述。
堆栈的数组和链表的实现方式。
堆栈的应用：前缀和中缀表达式的问题。
递归？
2.3 队列
队列和上述两者之间的区别和联系。
第三部分 树
3.1 树与树的表示
从二分查找引出树的定义。
树的各个定义的概念（这个一定要区分清楚）。
3.2 二叉树及存储结构
数组和链表的存储方式的差别。
3.3 二叉树的遍历问题
前序遍历，中序遍历，后序遍历。
3.4 二叉搜索树
二叉搜索树的定义。
3.5 平衡二叉树
平衡二叉树的调整问题。四种不同的情况。
3.6 堆
堆的定义及应用场景。
3.7 哈夫曼树与哈夫曼编码
3.8 集合及运算
第四部分 图
4.1 什么是图
4.2 图的遍历
4.3 最短路径问题
有权图的单源最短路算法（Dijkstra算法）：设一个集合为源点和已经确定了最短路径的顶点（源点到此节点）。我们定义dist[V]为s到v的只经过集合中点的最短路径长度。每次从没有被收录的点中挑选一个dist最小的点，然后将其收录到集合中，同时检查此点的所有邻接点，更新其最短路径。不能解决有负值的情况。算法的关键问题，如何查找未收录顶点中dist最小的点以及后续的路径更新。如果直接扫描所有的未收录的顶点，总的时间复杂度为$O(V^2 + E)$，适合稠密图。如果把dist存在最小堆中，则为$O(V log(V) + E logV) = O(E logV)$，适合稀疏图。
多源最短路算法：最简单粗暴的方式是直接把单源最短路算法调用V次，稀疏图的情况下时间复杂度为$O(V^2 log(V))$，但是在稠密图的情况下时间复杂度为$O(V^3 + E * V)$。
Floyd算法：：时间复杂度为$O(V^3)$，没有前面的后半部分。适用于稠密图。思想也是从第一个节点逐渐往后推，距离矩阵代表仅经过到目前为止的节点的情况的距离。这里的关键是距离矩阵的初始化，对角元为0，其他不连通的路径初始化为无限大。
4.4 最小生成树问题
基本概念：
树的特点：特殊的图，全连通，没有回路，V个顶点一定有V-1条边。
生成树：包含全部的顶点，V-1条边都在图里面，任加一条边都会够构成回路。
最小：边的权重和最小。（和之前的最短路径问题有相似点。）
图连通<——>存在最小生成树
贪心算法：每一步最优&权重最小。约束：只能用图中已有的边，只能正好用掉V-1条边，不能有回路。
Prim算法基本思想：从顶点出发，每次在未收录的顶点中找到一个与已有生成树最近的点V收录到树内，并记录由哪个树内节点出发到V的。收录完之后，更新V所有邻接点距离。限速步骤在查找最小距离的顶点，时间复杂度为$O(V^2)$，适合稠密图。最外层循环为中间节点k，内层循环为每两个节点本身的距离与插入k后距离的比较。
Kruskal算法基本思想：出示状态把所有点视为顶点，将森林合并为树。处理并收录的为边，从边的集合里找一条权重最小的边，拿出来之后检查其是否在已有的生成树中存在回路，没有回路即收录，有回路即丢弃。限速步骤：查找最小边——最小堆，查看是否构成回路——并查集（检查边的两个顶点是否属于同一个集合），时间复杂度为$O(E*log(E))$，稀疏图的情况下等价于$O(V*log(V))$。
4.5 拓扑排序问题
其实是一个从图中按照有向边依次访问的过程。
拓扑序：如果图中V->W有一条有向的路径，则V一定排在W之前。
Activity On Vertex，AOV(网络)，活动用顶点表示，如果有合理的拓扑排序，那么一定是Directed Acyclic Graph，DAG（有向无环图）。
算法基本思想：依次找到图中每一个入度为0的未输出过的结点，输出他并将他到每个邻接点的度减掉。限速步骤为第一步，若每次为全图扫描，时间复杂度为$O(V^2)$，另一种方法，每次把度为0的结点放到一个队列，再从队列访问，时间复杂度为$O(V+E)$。此算法可以用来检测图是否为DAG。
Activity On Edge，AOE(网络)，活动用边表示，顶点表示活动结束，一般用于安排项目的工序。边的权重为活动时间，顶点要表示最早完成及最晚完成时间。计算整个的工期从首节点往右递推，每个节点取最大的入度值作为最早完成时间。判断关键节点，从后往前推(相当于边反向了），取最小的入度值作为最晚完成时间，机动时间为后个节点的最晚减去前个节点的最早，再减去边的权重，即为机动时间，为0则为关键点。
第五部分 排序算法
若干前提：简单起见，谈论从小到大的整数排序。只谈论基于比较的排序。只讨论内部排序（都在内存中，相对的是内存外的排序）。稳定性：任意两个相等的数据，排序前后的相对位置不变。不同的算法适合不同特征的数据。
5.1 冒泡排序
基本思想：每次循环把前N个元素中两两相邻的元素依次比较，较大的往后排，最终把最大的放在最后。继续在前N-1个元素中执行以上循环。Tips：可以设置一个flag标记中途已完成所有排序，然后退出。最好时间复杂度$O(N)$，最坏情况下，两层N循环，时间复杂度为$O(N^2)$。适用于数组和链表的数据结构，并且具有稳定性。
5.2 插入排序
基本思想：每次取一个元素，跟队列的最后一个元素相比，若比他大，则放在最后，若比他小，就将队列的元素往后挪动一位，再跟前面的元素相比，直到找到合适的位置。实际算法就是在一个数组里，每次把在未排序队列里第一个元素依次往前比较，找到合适的位置插入。最好最坏时间复杂度为$O(N)$，$O(N^2)$。
逆序对的概念：对于i < j， 如果A[i] > A[j]，则称(i, j)为一个逆序对。
每次交换两个相邻元素则消去一个逆序对。插入排序复杂度为$O(N+I（逆序对）)$。
任意N个不同元素的序列平均逆序对为$N(N-1)/4$，由此，任意仅仅以交换相邻元素来排序的算法，平均时间复杂度为$\Omega(N^2)$。
排序算法的优化方向：1. 每次消去不止一个逆序对，2. 每次交换相隔较远的两个元素。
5.3 希尔排序
实际上是一种插入排序的优化。例如首先每间隔5个元素进行插入排序，然后进行每间隔3个元素的插入排序，最后进行每1个元素的插入排序。
首先遇到的问题是如何确定间隔，即增量序列的大小:
原始的希尔排序是间隔$D_k = \lfloor N/2 \rfloor, D_k= \lfloor D_k / 2 \rfloor$， 会遇到极端情况，前面所有的间隔因为不互质正好全错开，排序无效，要等到最后间隔为1进行全排序，即最坏情况时间复杂度为$\Theta(N^2)$。
Hibbard增量序列：$D_k = 2^k-1$，相邻元素互质。最坏情况时间复杂度为$\Theta(N^{3/2})$。
Sedgewick增量序列：略。其猜测的最坏情况时间复杂度为$\Theta(N^{4/3})$。
算法本身可能非常的简单，但是对其进行时间复杂度的分析非常难。
5.4 堆排序
选择排序：首先在未排序的序列中找到最小元素，然后将其与已经排序好的序列的后一个元素交换。最坏时间复杂度为$O(N^2)$。限速步骤在于如何在未排序的序列中找到这个最小值。
堆排序：实际上是选择排序的改进。把最小堆或者最大堆应用到找到最小元素这一步里面。一般的想法是，读入序列后把它改造成一个最小堆，由于我们需要的序列是从小到大排序的，所以依次弹出一个最小值，赋值给一个新的数组，问题在于需要额外开一个新的数组的空间。优化后的想法是利用最大堆，把原序列改造成最大堆之后，把顶点元素和和最后一个元素交换，并把剩下的元素再改造为最大堆，循环进行。这种情况下，最坏情况的时间复杂度比$O(N*log(N))$稍小，但是实际效果比不上使用Sedgewick增量序列的希尔排序。
5.5 归并排序
核心：有序子列的归并。主要的内容就是分别比较两个子列的头结点的大小，把较小的结点放到新序列的顶端。
二分法：分别递归的对左边排序，再递归的给右边排序。最后再把两段序列按照上面的有序子列的归并算法合起来。稳定。
非递归的算法：
归并排序有很多优点，比如说时间复杂度稳定在$O(N*log(N))$，并且排序结果是稳定的。但是归并排序的缺点在于需要另外一个等长的数组空间，并且数据在这两个数组之间要来回的读写。所以不适合用于全部在内存中完成的内排序。比较适合外排序。
5.6 快速排序
适合处理大规模的随机数排序。感觉快速排序算法挺神奇，乍看之下思想很简单，分治嘛，但是细看又觉得好像不是这么简单，想想觉得好像很多边界问题不好处理。但是最后实际动手实现一遍的时候，又觉得这东西还是可以的。
基本思路是找到一个主元（Pivot），就是整个序列中的一个分割点，然后根据分而治之的方法去递归的处理左右两边的序列。实际处理的元过程是，1.找主元，常用的Median3方法，我们比较首尾正中三个元素，排序后，取中间的元素替换尾部-1的位置待用。2.递归的过程：从左右两端分别向中间逼近，判断是否与主元处在正确的相对位置，每次找到一对位置错误的，就互换位置（这个过程实际上就是对应了5.2中指出来的排序优化的方法），最后把主元换到中间。这个过程实际上做的事情是把主元放到了最终的位置并把整个序列中的逆序对的数量大大减小了，两侧序列分别递归后最终所有的位置都会回正。
算法的时间复杂度很大程度上与主元的选取有关，如果每次主元都在边界上，最坏情况下时间复杂度达到了$O(N^2)$，处理好了这部分，时间复杂度就与大部分二分法的情况类似了$O(N*log(N))$。
5.7 表排序
要用到表排序的情形是，每个元素非常大，移动元素的时间不可忽略不计，那么就要优先保障移动次数最少。其核心思想是，定义一个指针数组table，第一次排序时不移动实际元素，而是利用其它的排序方法，将排序后的顺序存储在指针数组中。然后如果一定需要物理排序，那么利用N个数字的排列与其序列下标可以构成若干个独立的闭环这个属性，依次取移动。最坏时间复杂度（N/2个环）为$O(mN)$（m为每个元素复制需要的时间）。
5.8 基数排序
仅仅基于两两比较的排序算法，最坏情况时间复杂度的下界为$O(N*log(N))$。但是利用分段的思想，构造一种基于桶排序的方法，可以下降到线性复杂度。例如对多个三位数进行排序，首先基于个位数字将不同的数字分到不同的桶里，然后依次基于十位数，百位数进行分桶，最后合并。一般基于次位优先会比主位优先更好，因为次位优先实际上每次分桶后的顺序就是基于该位排序的相对位置，最后只要把多个桶的结果（多次调整后的相对位置）串联起来即是最终的结果，实际上没有一个两两比较的过程，而是一个分类的过程，大小的信息在排列空桶的时候就给定了。而主位优先在最开始的分类之后，还是要在各桶内部进行排序。基数排序的时间复杂度为$O(N+M)$（M为桶的数量）。
5.9 排序算法的比较
第六部分 散列查找
编译处理时，涉及到变量及属性的管理，例如新变量的定义（插入），变量的引用（查找）。实际上是一个动态查找的问题。已知的查找的方法：顺序查找$O(N)$，二分查找$O(log_2N)$，二叉搜索树$O(h)$（h为二叉查找树的高度），平衡二叉树$O(log_2N)$。所以这里要解决的基本问题是找到一个合适的数据安排的方法，便于后续的动态查找问题。
查找的本质：已知对象找位置。有序的安排对象：全序，半序。直接算出对象的位置：散列。散列查找的基本工作，计算位置，构造散列函数确定关键词存储的位置；解决冲突：应用某种策略解决多个关键词位置相同的情况。时间复杂度几乎是常量$O(1)$。
散列表（Hashing Table，哈希表）
以关键字为自变量，通过一个确定的函数计算出对应的函数值，作为数据对象的存储地址。可能不同的关键字会映射在同一个散列地址上，称为冲突，需要解决冲突的策略。
散列函数的构造方法
两个原则：计算简单，关键词对应的地址空间分布均匀。
构造方法：1. 直接定址法。取关键字的某个线性函数为散列地址。2. 除留余数法。设定一个除数取余数。h(key)=key mod p。这里的p一般取素数，减少冲突。3. 数字分析法。分析数字关键字在各位上的变化情况，取比较随机的位数作为散列地址。4. 折叠法。把关键词分割成位数相同的几个部分，然后叠加。5. 平方取中法。把数字平方后取中间的几个位。对于字符的关键字：1. ASCII码加和法，例如把所有的字符的对应的ASCII码的数字全部相加然后对表的大小取模，直接这么做的话冲突比较严重。2. 简单的改进，取前三个字符移位。3. 好的散列函数：移位法，把字符串看作是32进制（总共26个英文字母，然后取32可以直接用位运算左移5位）的数，转换为10进制后对表的大小取模。
冲突处理的方法
装填因子的概念：待填入的元素的个数除以表的总大小。散列表查找的性能分析：成功平均查找长度（对每个元素需要的查找次数之和除以总的元素个数），不成功平均查找长度（对于不在散列表的每个地址的可能的查找次数之和除以地址的大小）。
冲突处理的两种思路：换个位置再放，开放地址法。把同个位置的冲突对象组织在一起，链地址法。
开发地址法：一旦产生了冲突，就按照某种规则去寻找另外一个新的空的地址。若发生了i次冲突，则试探下一个的地址将增加$d_i$，基本公式为$h_i(key)=(h(key)+d_i)mod(TableSize)(1 \le i \lt TableSize)$。不同的$d_i$决定了不同解决方案。线性探测：$d_i=i$。平方探测：$d_i=\pm i^2$，平方探测要注意一个问题是，若是表的大小设置的不好，可能会出现某些地址永远不会被探测到，有定理显示，如果散列表的长度TableSize是某个整数树k的4k+3形式的素数时，平方探测法就可以探查到整个散列表的空间。双散列：$d_i=i*h_2(key)$，探测序列要保证所有的单元都能被访问到，所以应该选择这样的形式$h_2(key)=p-(key)mod(p)$。再散列：装填因子过大（实用最大的装填因子在0.5到0.85之间），查找的效率下降的时候，加倍扩大散列表。
分离链接法：把相应位置上所有的冲突的元素都存储在同一个单链表中。
散列表的性能分析
平均查找的长度来度量散列表的查找效率：成功或是不成功。而关键词比较的次数（也就是决定平均查找长度的关键）是取决于产生的冲突的多少的，最后影响产生的冲突的多少的又有以下的三个因素：散列函数是否均匀，处理冲突的方法是什么，以及散列表的装填因子（待插入的元素除以散列表的大小）。这里分析的关键是不同的冲突的处理方法和装填因子对效率的影响。
对于线性的探测法和平方探测法（平方探测法和双散列探测法的公式相同），可以证明的是均有关于装填因子的函数来计算期望的成功查找次数和不成功的查找次数。整体来讲，平方探测法的性能优于线性探测法，并且对于每种方法来说，成功的查找次数都比不成功的查抄次数要小。装填因子在0.5左右的时候，各方法差别不大，随着装填因子增加，各方法的平均查找次数指数增加，一般建议最大的合理的装填因子不应该超过0.85。
对于分离链接法，其装填因子被定义所有链表的平均长度。
散列表其实是以空间换取时间的方法，对于合适的散列函数，散列法的查找效率期望是$O(1)$。但是散列法的存储是随机的，不利于顺序查找、范围查找或者是最大值最小值的查找。