前言

为了应对因为疫情原因导致的考试延迟，这一篇就来回顾并复习一下一学期的学习。内容比较主观，仅为个人理解！

概念理解

关于Algorithm, hash table, stack, linked list的一些定义与概念理解，我们一般需要掌握下面内容：

算法分析部分

What is an Algorithm？
算法(algorithm) 是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。它可能以不同的形式出现。
A sequence of finite instructions to be followed for solving a problem. An algorithm may be given in different forms.
What is data structure?
数据结构是一种整合数据、管理数据的方式。
The ways of organizing data. Program = algorithms + data structures.
What is ADT?
ADT（抽象数据类型）是一种抽象的数学模型，它定义了一组数据以及它们之间的关系和操作。
ADT is a specification of a set of data and the set of operations that operate on the data.

链表

链表操作的时间/空间复杂度是？
插入操作：时间复杂度O(1)，空间复杂度O(n)
删除操作：时间复杂度O(1)，空间复杂度O(n)
查找操作：时间复杂度O(n)，空间复杂度O(n)

栈

栈的结构特点是？
根据栈的结构，栈是一个后进先出/先进后出（LIFO/FILO）的结构。在表的头部压入（Push)，同时在表头弹出(Pop)。

队列

队列的结构特点是？
根据队列的结构，栈是一个先进先出（FIFO）的结构。在表的尾部入队（Enqueue)，在表头出队(Dequeue)。

树

什么是二叉查找树？
二叉树的一个节点的子节点至多有两个。它可以使数据在树中以顺序方式存储。
二叉查找树的结构特点是？
- 若其左子树非空，则左子树上所有节点各自的值都小于根节点的值
- 若其右子树非空，则右子树上所有节点各自的值都大于根节点的值
- 其左右子树都是一棵二叉查找树。
二叉查找树的时间复杂度是？
如果二叉查找树是平衡的,则n个节点的二叉排序树的高度为log(n+1)-1.（高度从0开始），它的查找时间复杂度为O(log(n))。
什么是AVL树？
AVL树是一种自平衡二叉搜索树，它的每个节点的左子树和右子树的高度最多相差1。

堆/优先队列

堆/优先队列的结构特点和时间复杂度是？
堆/优先队列我们可以看成是一个完全二叉树，它的高度为log(n)，平均时间复杂度为O(log(n))。
插入、删除操作时间复杂度为O(log(n))，获取最大/最小元操作时间复杂度为O(1)。

散列表

散列表操作的时间复杂度是？
散列(Hashing)是一种用于以常数平均时间（O(1)）执行插入、删除和查找的技术。

排列算法

列举xx排序的时间复杂度。

插入排序的基本思想？
插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
选择排序的基本思想？
每一趟在n-i+1(i=1,2,...,n-1) 个元素中选取关键字最小的元素作为有序序列的第 i 个元素。
归并排序的基本思想？
采用了分治法(divide and conquer)，划分成很多个小的问题，递归处理，并将分阶段得到的答案整合起来。
快速排序的基本思想？
采用了分治法(divide and conquer)，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

递归和递推

在编程中，我们解决重复的问题时，经常使用递归和递推（Recursion & iteration）。比较两者，它们各自有优有劣。下面通过斐波那契数列数列的例子看看它们的区别：

递归解决

int fib_recursive(int n)
{
    if(n <= 1)
        return 1;
    else return fib_recursive(n-1)+fib_recursive(n-2);
}

我们可以发现，递归的代码量相对少，而且比较直观，相当于直接把公式摆出来一样，一看就能知道它在干什么。

递推解决

int fib_iterative(int n)
{
    int ans[N];    //N>=n
    int ans[0]=1,ans[1]=1;
    for(int i=2;i<=n;i++)
        ans[i] = ans[i-1] + ans[i-2];
    return ans[n];
}

递推的原理是通过公式得到一个递推式，它一般更有效率。大部分情况下递归能写的，递推都能写。

递归与递推的比较

递归是把一个问题，分成更小的问题去解决，而递推是在掌握了问题的规律后的重复操作。总结来说，递归具有如下优点。

递归的优点

当一个问题可以分解成更小的简单问题去解决时，递归优于递推。
Problems that can be broken down into a simpler version of the same problem, and the simpler version problem can be solved easily, recursion is better.
在一些算法中，递归相比于递推更易于编写与表达。例如基于分治法的排序、二叉搜索树（BST）、最短路径算法……
An algorithm you design that can be expressed intuitively using recursion but not be as easy to understand if described in iteration. Recursion is better and easier than iteration. For example, sorting, binary search tree (BST), shortest path algorithm...
如果需要多次调用同一段代码，我们可以把它做成一个函数，此时编写递归比递推更好更容易。
If we want to call the same block of code multiple times and the times might be little, we may make it a function, then recursion is better and easier than iteration.
递归代码通常更加简短且可读性高。如果你想让你的代码看起来简单明了，使用递归比迭代更好。
Recursive code is usually short, elegant and readable. If you want to make your code looks simple and clear, you may use recursive better than iterative.

递推的优点

效率通常更高，节省时间与空间的消耗。
在执行上减少了函数的调用，减少时间消耗。

栈与队列

这一部分主要是理解栈(stack)与队列(queue)的基本原理即可，更多情况下我们是使用这些基本的数据结构。详细部分请见：

【数据结构】表、栈和队列

栈

栈的基本原则就是先进后出（FILO），数据在栈的头部压入，在头部弹出。代码部分见上述文章。原理如图：

例如我们将{1,2,3}压入栈中，再出栈两次，再压入{4,5,6}，最后全部出栈。结果为：{3,2,6,5,4,1}

队列

队列的基本原则是先进先出（FIFO），数据在尾部入队，在头部出队。原理就和我们排队一样，如图：

队列我们一般会使用链表实现，我们也需要掌握基本的队列实现功能。例如，我们将{1,2,3}入队，然后出队两次，再将{4,5,6}入队，最后全部出队。其结果为{1,2,3,4,5,6}。

栈与队列实现的应用请看：

【数据结构】栈、队列与递归的应用

散列

散列(Hashing)是一种用于以常数平均时间（O(1)）执行插入、删除和查找的技术。它可以通过散列函数，提供关键字key直接得到要查找的记录内存存储位置。

具体解析：

【数据结构】散列

因为存储时很容易出现冲突，我们使用散列时需要去处理冲突，我们有分离链接法、开放定址法、双散列等。这里主要提一下双散列。

双散列即使用两个散列函数 hash1(key)，hash2(key). 先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，直到找到空闲的存储位置。

f(key)=(hash1(Key) + i * hash2(Key)) mod Tablesize

这个公式说明，我们先通过hash1函数判断位置，然后再将第二个散列函数应用到Key，并在距离1*hash2(Key), 2*hash2(Key) ......处探测。

我们一般取hash2(Key) = R - (Key mod R)，其中R 为小于TableSize 的质数。

举个例子：设H(k) = k mod 10为初始的散列函数，其中k为关键字。还有一个散列函数G(k) = 7 – (k mod 7) 。其中有6个关键字需要插入{89, 18, 49, 58, 69}

我们列一个表：

	0	1	2	3	4	5	6	7	8	9
After 89
After 18
After 49
After 58
After 69

插入89，H(89)=9，把89插入位置9；
插入18，H(18)=8，把18插入位置8；
插入49，H(49)=9 产生冲突，使用双散列，G(49)=7-(49%7)=7，Hi(49) = (H(49) + 1*G(49))%10 = 16%10 = 6，把49插入到位置6；
插入58，H(58)=8 产生冲突，使用双散列，G(58)=7-(58%7)=5，Hi(58) = (H(58) + 1*G(58))%10 = 13%10 = 3，把58插入到位置3；
插入69，H(69)=9 产生冲突，使用双散列，G(69)=7-(69%7)=1，Hi(49) = (H(69) + 1*G(69))%10 = 10%10 = 0，把69插入到位置0.

故这样操作后，我们得到的表格就是这样的：

	0	1	2	3	4	5	6	7	8	9
After 89										89
After 18									18	89
After 49							49		18	89
After 58				58			49		18	89
After 69	69			58			49		18	89

代码实现部分请见：

【数据结构】散列

图——拓扑排序

拓扑排序，是对一个有向图构造拓扑序列的过程。它的基本思路是：从无圈图中选择一个入度为0的顶点，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者无圈图中不存在入度为0的顶点为止。

例如如图，回答下面问题：

说明图中各个顶点的入度（Indegree）。
由图生成一个邻接矩阵（Adjacency Matrix）。
这个图的连接状态是怎么样的（强连接、弱连接、不连接）。
找到所有可能的拓扑排序顺序（Topological Orderings）。

我们需要先了解相关的知识：

度

顶点V的度(Degree)是和V相关联的边的数目。在有向图中，度我们一般分为入度和出度。以顶点V为头的弧的数目称为V的入度(lnDegree)，以V为尾的弧的数目称为V的出度(OutDegree)。

强连通

在有向图G中，如果对于每一对Vi和Vj，都有Vi->Vj、Vj->Vi的路径，则称G是强连通图（Strong Connected）。有向图中的极大强连通子图称做有向图的强连通分量。

弱连通

有向图G中，若任意两个顶点之间均存在通路，则称G为弱连通图（Weak Connected）。均存在通路是指去除方向后连通即可。

总结即：

若每个顶点到其他各个顶点之间有通路，则是强连通的。
若有向图对应的无相图是连通的，则这个有向图是弱连通的。
一个有向图可以同时存在强连通和弱连通属性。

邻接矩阵

用二维矩阵来表示顶点(V,V')的相邻关系，这个矩阵是邻接矩阵(Adjacency Matrix)。

若Vi与Vj相邻，则矩阵中(i,j)处为1，反之为0。无向图中，它们沿着主对角线对称，每一行加起来则为那个顶点的度。

接下来我们就可以回答上列问题：

Q: 说明图中各个顶点的入度（Indegree）。
A: A:0, D/F:1, C/E:2
Q: 由图生成一个邻接矩阵（Adjacency Matrix）。
A: 如下表：

From\To	A	C	D	E	F
A	0	1	1	0	1
C	0	0	0	1	0
D	0	1	0	0	0
E	0	0	0	0	0
F	0	0	0	1	0

Q: 这个图的连接状态是怎么样的（强连接、弱连接、不连接）。
A: 这个图是弱连接图。
Q: 找到所有可能的拓扑排序顺序（Topological Orderings）。
A: 分情况讨论。

有如下三种情况，其中X(N)，X表示顶点，N为它的入度：

ADCFE
刚开始时，A(0),C(2),D(1),E(2),F(1), 我们删除A和它的弧，并添加到答案序列中，于是得到C(1),D(0),E(2),F(0). 我们如果按照字母表顺序删除的话，此时先删除D，则得到C(0),E(2),F(0). 按照字典序继续删除C，则得到E(1),F(0). 接下来删除F，则剩下E(0)。删除E即删除全部顶点，得到答案顺序{ADCFE}
ADFCE
这个顺序是按照队列的顺序删除，即我们入队读入的队列为{ADCFE}，基本过程与上面相同。
AFDCE
这个顺序是按照图的上下顺序，基本过程差不多。

拓扑排序的代码实现部分请看：

【数据结构】拓扑排序

堆、优先队列与堆排序

堆

定义

堆(Heap)是一种基于完全二叉树（complete binary tree）的数据结构。完全二叉树（complete binary tree）是除了最后一层可能没有填满外，所有的层都被填满的二叉树，且最后一层从左向右填充。即只有最后一层节点右边不放满的二叉树。

二叉堆（Binary Heap）是一个堆，满足：

二叉堆基于一颗完全二叉树。
堆中某个节点的值总是不大于或不小于其父节点的值。

我们把某个节点的值总是不大于其父节点的值的堆称为最小堆（Min-Heap），把某个节点的值总是不小于其父节点的值的堆称为最大堆（Max-Heap）。即最大最小指的是（子）树根节点是最大/小的。

整个过程，时间复杂度如下：

插入操作，操作数为h（高度），时间复杂度是 $O (l o g n)$
删除操作，操作数为h（高度），时间复杂度是 $O (l o g n)$
获取堆顶，时间复杂度是 $O (1)$

实现

我们一般使用数组来实现。按照一定的顺序排号：

我们把对应序号的节点值输入到对应序号的数组元素中去，于是有：

其中数组的首位置0是空的，我们把它当成一个指示结点（相当于链表中的哑结点，指向首节点）

对于数组中的结点i，它的值为array[i]，它的父母节点（若有）为i/2（整除，一般floor函数操作），左节点为2i，右节点为2i+1。

我们的实现，一般是指初始化/插入/删除。以最小堆为例子。

定义

typedef int ElementType;
struct HeapStruct
{
    int Capacity;    //最大容量
    int Size;    //当前大小
    ElementType *Elements;    //堆数组
};
typedef struct HeapStruct *Heap;

初始化

Heap Initialize(int n)
{
    Heap H = (Heap)malloc(sizeof(struct HeapStruct));
    if(H==NULL)
    {
        printf("Out of space!\n");
        exit(-1);
    }
    H->Elements = (ElementType *)malloc((n+1)*sizeof(ElementType));
    if(H->Elements == NULL)
    {
        printf("Out of space!\n");
        exit(-1);
    }
    H->Capacity = n;
    H->Size = 0;
    H->Elements[0] = MinData;    //H->Elements[0] 作为一个索引，被初始化为一个很小的值
    return H;
}

我们初始化时，要设置最大容量（Capacity），当前容量设置为0，以及一个索引[0]，它一定比输入数组中的所有元素要小，保证不会出界。

插入

我们的插入操作需要考虑插入的位置。我们一般会先插入到最后，然后开始比较，向上冒泡——用递归比较插入结点与其父母结点的大小，如果插入节点小则向上交换调整，否则就结束。这个原理需要了解，才能理解代码怎么做。

void Insert(ElementType X, Heap H)
{
    if(IsFull(H))    //省略了这个函数的定义，这是判断堆是否已满
    {
        printf("Heap is full, cannot insert!\n");
        return;
    }
    realloc(H->Elements,sizeof(H->Elements) + sizeof(ElementType));    //在数组后面增添一个位置，如果非动态可以不用这句
    for(int i=++H->Size;i>=1;i/=2)    //向上冒泡的过程，i从新位置开始
    {
        if(X < H->Elements[i/2])    //如果插入的值小于它的父母结点的值
        {
            H->Elements[i]=H->Elements[i/2];    //把父母结点的值赋到新开的当前位置
            continue;
        }
        else     //如果插入的值大于它的父母节点了，此时说明找到了位置
        {
            H->Elements[i] = X;    //插入当前位置
            break;
        }
    }
}

具体注释写得很清楚了。

删除

删除操作即删除最小元，即删除根节点，因为这是一个最小堆。

删除的过程是一个下沉操作，我们先记录删除元素的值以便返回。接下来通过比较得到根的左右结点和最后一个结点中的最小值，并把最小值赋值到根节点上。

比较的过程如下：

若左结点最小，则把左结点的值赋值到根结点上，然后以左节点为新的根继续寻找；
若右结点最小，则把右结点的值赋值到根结点上，然后以右节点为新的根继续寻找；
若最后一个结点最小，则把它赋值到根结点上，并停止寻找。

我们根据这个思路可以得到代码：

ElementType DeleteMin(Heap H)
{
    ElementType MinElement, LastElement;
    if(IsEmpty(H))
    {
        printf("Heap is empty!\n");
        return H->Elements[0];
    }
    MinElement = H->Elements[ 1 ];
    LastElement = H->Elements[H->Size--];
    for(int i=1;2*i<=H->Size;)
    {
        if(H->Elements[i*2] < H->Elements[i*2+1] && H->Elements[i*2] < LastElement) //左结点比右结点和最后结点小 
        { 
            H->Elements[i] = H->Elements[i*2];
            i*=2;
        }
        else if(H->Elements[i*2+1] < H->Elements[i*2] && H->Elements[i*2+1] < LastElement) //右结点比左结点和最后结点小 
        { 
            H->Elements[i] = H->Elements[i*2+1];
            i=i*2+1;
        }
        else if(LastElement < H->Elements[i*2] && LastElement < H->Elements[i*2+1])    //最后一个结点最小
        {
            H->Elements[i] = LastElement;
            break;
        }
    }
    return MinElement;
}