Data Structure Notes

发表于 2019-09-14 更新于 2022-02-05 分类于编程

数据结构基础学习笔记。

参考书目：Data Structures and Algorithm Analysis in C, 2nd edition, Mark Allen Weiss

表、栈与队列

表

表是一种线性数据结构，描述元素间的先后关系，每个元素拥有唯一的上一个相关元素和下一个相关元素。它是基础的数据结构，可以用来实现后面的栈与队列。

一个表涉及到的操作应有：

新建空表init
在指定位置插入新节点insert
删除指定位置节点delete
遍历链表/寻找指定元素find

我们可以使用数组来实现一个表，但是通常不这样做。对于C来说，数组初始化需要已知数组大小，若不清楚则需要留出足够大的空间，这是对存储空间的浪费；此外在进行插入和删除工作时较为麻烦：需要将指定位置之后的全部元素后移或前移一个位置。

使用链表进行表结构的描述是合适的，其主要特点是使用非连续内存空间进行表的保存，在插入/删除新节点时不必移动其他节点位置，并实现了动态特性，使表的大小可以动态调整。

链表节点可以描述如下：

typedef struct {
    ParamType param; // Any parameter you want ...
    struct Node *next;  // Pointer to next node
} Node;

关于表头

表头是一种结构上的设计，对数据本身没有含义。表头的使用使得一些操作（如涉及到改变一个节点位置的操作）更加方便，是否使用根据使用者的喜好而定。

我认为还是使用表头为好。一个表起始于表头节点，终止于空地址NULL，有始有终，结构清晰。

插入/删除操作需要注意的

插入操作时需要注意先让新节点指向它的下一个节点，在将前一个节点指向它，否则链表会中断。

类似的，删除时先将被删除节点的前一个节点连接到其后一个节点，再释放到被删除节点的内存。

其他

桶排序&基数排序

桶排序是一种简单的整数排序方式，需要已知整数范围。假设有$N$个整数，范围从$0~M-1$，顺序任意，桶排序过程如下：

建立$M$个“桶”，如长度为$M$的数组bucket
遍历$N$个整数，将整数$i$送入对应的“桶”bucket[i]
遍历bucket得到的就是有序的$N$个整数

应用中如果$M$范围较大，新建$M$个桶是浪费的，可以每次以一位进行桶排序，直到所有位都完成，这就是基数排序。如，对十进制整数，可以以10为基数，依次对个、十、百、千…数位进行桶排序。

基数排序的实现过程中可以使用链表。这是因为对每位进行桶排序的时候，每个桶里可能不只有一个数，此时需要按照入桶的先后顺序以链表组织一个桶里的所有数。

栈

栈是LIFO类型的结构，可用来实现一些依赖中间结果的数据调度工作。对于一个栈可以进行的操作为：

pop操作：弹出栈顶元素
push操作：将新元素压入栈

栈可以通过数组或链表来实现。

用数组实现栈

先来说数组实现。我们需要一个变量top来指示栈顶位置，即对应数组单元的序号。

初始化：新建数组stack，top置为-1
入栈：stack[++top] = new_element
出栈：return stack[top--]

数组实现栈的时候要规定最大栈容量防止溢出。

用链表实现栈

用链表实现栈不用考虑初始化最大栈容量。入栈只需在链表尾部增加一个节点，出栈则返回链表尾部节点值后将其内存释放。如果使用双向链表，进行pop操作的时候很简单就能更新栈顶地址，但是如果是单向链表，必须花费$O(N)$的时间找到链表尾部前一个地址，将其设置为栈顶。

所以，如果使用单向链表的话，栈顶应该指示链表头部，每次在链表头部前增加一个新节点进行push，或者将头部更换为下一个节点进行pop。

链表实现栈不需要规定最大栈容量并不意味着栈可以一直大下去。当内存空间耗尽无法再分配新节点空间时会出现错误。当然在设计合理的情况下一般也不会出现这种情况。

一个例子

栈可以实现简单的计算器。假设我们有一个表达式3 + 5 * 2 - 8 / 4，如何在符合运算优先级的情况下计算正确答案11？

我们用到两个栈ns和os，分别寄存操作数number和运算符operator。按顺序遍历表达式，遇到操作数压入ns，遇到运算符压入os。如果新遇到的运算符优先度比os栈顶优先度低，则弹出os栈顶运算符以及ns顶部两个数进行运算，结果压入ns，再将新运算符压入os。反复进行直至表达式遍历完成，之后依次弹出os栈顶与ns顶部两个数进行运算，结果压入ns，直到os为空，此时ns中只剩最终计算结果，将其弹出。

注意：在os依次弹出进行运算的时候，如果遇到次栈顶运算符为减号，要考虑变号的问题！

队列

队列是典型FIFO结构，实现先进先出的调度。同样的，队列可以使用数组和链表实现。

用数组实现队列

我们需要构造一个队列结构，有以下要素：

size：队列长度
front：队头序号
rear：队尾序号

同样，用数组实现队列的时候也要设计最大队列容量。

初始化：新建数组queue，size = 0，front = 1，rear = 0
入队：size += 1，queue[++rear] = new_element
出队：size -= 1，return queue[front++]

size的使用不是必须的，不过最好使用size显式判断队列何时为空，何时为满。

队头/尾移动到数组尾端时可以让其回到开头，以循环数组的方式继续模拟队列。使用循环数组时对队列是否为空的检验很重要。

用链表实现队列

一下子变得简单了很多。无需提前确定最大队列容量，入队时向链表尾部加入新节点，出队时返回头节点的下一个节点值后将其释放，注意不是释放头节点！

树

树可以说是运用最广泛与最重要的结构了。树描述数据间的层次关系，每个节点有且仅有一个父节点，但可以拥有任意数量子节点。

几个属性：

深度：从根节点开始到指定节点的路径长
高度：从指定节点开始到达其子树中最远叶节点的路径长

描述一棵通常的树

很自然，我们可以定义树中每个节点，使用指针表示节点间的联系。但是有个问题：对于一棵通常的树而言，其子节点数量是不确定的，直接定义指向每个子节点的指针无法程序化进行。

为解决该问题，我们使用第一个子节点指针和下一个兄弟节点指针进行节点间关系描述，这样既描述了节点和当前层级其他节点的关系又描述了和下一层级节点的关系。

所以对一棵通常的树，对节点结构定义如下：

typedef struct {
    ParamType param; // Any parameter you want ...
    struct Node *firstChild;
    struct Node *nextSibling;
} Node;

这里是对一般树节点结构的定义，后面会看到，对于特殊的树（如二叉树），受到结构的要求，我们可以直接定义全部指向子节点的指针。

二叉树

二叉树的每个节点只存在两个孩子，所以直接定义为：

typedef struct {
    ParamType param; // Any parameter you want ...
    struct Node *leftChild;
    struct Node *rightChild;
} Node;

二叉查找树

二叉树最重要结构之一。二叉查找树要求每个节点node满足node.leftChild.value < node.value < node.rightChild.value的平衡条件。

对二叉查找树有以下几类操作：

初始化
搜索节点
插入节点
删除

对树的所有操作都体现了其特有的递归处理风格。

初始化

通过直接初始化一棵空树的根可以从零开始建立一棵树；当然我们也可以对一棵非空树的根递归地进行初始化操作从而释放整棵树的空间，最后返回一棵空树的根。

搜索与插入

两者基础都是搜索。对二叉查找树而言只需从根开始比较输入值与根节点值大小，然后递归地向左右子树进行比较直至叶节点（它的左右子树均为空）即可。搜索发生在上述过程中，找到目标节点即可停止；插入操作在达到叶节点后插入到左/右子树即可。

对于重复元素，一般考虑使用一个节点属性（如频数）表示个数，而不是增加树的节点。

删除

比较麻烦的操作，方法有常规删除和懒惰删除。

先说懒惰删除。懒惰删除不涉及树结构的变化，使用特别的标记注明哪些节点是被删除掉的，当访问这些节点的时候执行特定的处理。比如我们可以使用频数标记，注明了节点值出现的次数。

常规删除进行树结构的改变，分多种情况讨论。

当被删除节点为叶节点时一切都是美好的，只需要释放该节点的空间。当被删除节点只有一个孩子，事情也不是很复杂，我们让其唯一的孩子代替被删除节点，然后释放其空间即可，当然这里要注意做好节点地址备份，因为在用子节点替换之后，被删除节点的地址改变了。

但是如果被删除节点有两个孩子就稍微麻烦一点。通常，我们使用被删除节点右子树中最小节点值替换被删除节点值（替换节点属性而不是向后的引用指针！），然后从被删除节点的右子树中递归地删除那个最小值节点。由于右子树中的最小节点一定是一个叶节点，因此在递归删除过程中很容易使用上文提到的方式对叶节点进行删除。因此，常规删除中应该同时包含所有情况的讨论以便在对双子树节点进行删除时能递归地进行。

AVL树

现在让我们更进一步，二叉查找树实现了对数据的有效组织，通过递归的方法维护结构，但是它存在固有的问题——一个二叉查找树可能极度不平衡，某个节点的两棵子树高度可能相差甚远，在进行维护时的代价过高。

因此我们引入平衡的概念，使得任何节点的深度都不宜过深，加入平衡的二叉查找树称为平衡二叉树。实现平衡的方法很多，最传统的是通过旋转操作构建的AVL树。

AVL树定义为任意节点两子树高度差不超过1的二叉查找树。插入操作会导致树结构发生改变并影响平衡性，因此AVL树要求在进行打破平衡的操作后对树进行维护，使其仍保持平衡条件。维护方式也是对树结构的一些调整，称旋转。

AVL树的旋转

解决何时旋转，在哪里旋转，向什么方向旋转。

旋转分成左/右单旋转和左/右双旋转，旋转操作调整了子树的高度。由于插入操作只会影响插入点到根节点之间子树的平衡性，因此我们从插入点向根节点回溯找到第一个打破平衡性的节点，该节点将作为旋转操作的实施点。

插入操作会导致以下后果：

节点左子节点的左子树进行插入（左-左，使用左单旋）
节点右子节点的右子树进行插入（右-右，使用右单旋）
节点左子节点的右子树进行插入（左-右，使用左双旋）
节点右子节点的左子树进行插入（右-左，使用右双旋）

前两种情况对应单旋转，后两种情况对应双旋转（P82-P85）。找到一字型或之字形结构能很好确定旋转类型。

实际上，双旋转的之字形结构是两个一字型结构叠加，因此自底向上进行两次单旋转就能实现双旋转。在具体实现中，先实现单旋转的结构重组，再用单旋转定义双旋转是个很好的选择。

每次插入操作完成后都要进行AVL平衡的维护，因此我们需要额外为每个节点添加一个height变量记录其作为根节点的子树的高度。插入新节点后检查左右子树的height属性，一旦不平衡则进行旋转，旋转后更新子树高度。采用哪种旋转则根据插入节点的位置决定。

一旦进行过改变结构的操作都要重新计算高度！

AVL树插入例程在P88。

伸展树

我决定跳过这一节…说起来太复杂了。简单总结一下，就是可以将任意一个节点通过AVL树的旋转方式将其调整到根节点（但不保证平衡性），从而方便对该节点的访问，这个过程叫做展开。

树的遍历

一共三种：

前序遍历
中序遍历
后序遍历

遍历顺序区别于何时访问根节点，实现方法也是基于递归，结构上用栈实现。

还有一种方式叫做层序遍历，实际上就是广度优先搜索，用队列实现。

Huffman树

Huffman树实现了一种保证优先度的树结构，Huffman树的叶节点带有权值，Huffman树的构造过程从叶节点开始，每次选择两个最小权值的叶节点生成一个根节点，根节点权重为两个叶节点权重之和，然后将生成的根节点和剩下的叶节点一起重复构造新的根节点，直至最后。这种构造方式保证了WPL（Weighted Path Length，带权路径长）最优，带权路径长定义如下：

$$
WPL = \sum_i w_i l_i
$$

其中$w_i$表示第$i$个叶节点权重，$l_i$表示从根节点到第$i$个叶节点经过的路径长。

在所有构造方式中，Huffman树的WPL最小。

实现

一般使用数组实现。$n$个叶节点的Huffman树使用长度为$2n-1$的数组进行表示，数组前$n$个元素存储所有叶节点的权重；从第$n+1$个元素开始，选择之前所有元素中两个最小权重求和，作为该元素的权重，依次向后直至最后一个元素。

同时还要注意每个元素要存储层级关系。用一个域描述当前节点的父节点，分别用两个域描述左右子节点。描述父节点是能够自底向上地遍历Huffman树任意一条叶节点到根节点的路径（Huffman编码时需要完成根-叶节点的路径）。

实现中用数组下标进行节点间关系指示，节点结构可定义为如下：

struct Node {
    DataType data; // Weights
    int left_child; // Index of left child
    int right_child; // Index of right child
    int parent; // Index of parent, 0 for root node
};

2019.9.24，想了一下，鉴于树和图的关系比较近，决定先总结图相关知识。

图

图可以看做树结构的超集，描述多个节点间的关系。数学上图可以定义为顶点和边的集合：
$$
\mathbf{G} = (V,E)
$$

一些定义

方向性：边是否有方向规定。有向图：$(u,v) \neq (v,u)$；无向图：$(u,v) = (v,u)$
有环性：是否存在环。有环图：从顶点$n$出发能够返回顶点$n$；无环图：从顶点$n$出发无法返回。有向图中相邻两个顶点可以构成环，但是在无向图中定义相邻顶点间无法构成环（即无向图中至少三个节点成环）
连通图：满足无向图中任意顶点到其他顶点都存在一条路径的图
强连通图：满足连通条件的有向图
弱连通图：非强连通图，但是去掉有向性后退化得到的无向图是连通图的有向图
有权图：边带有权重属性

表示

两种表示方法：

邻接矩阵：适合稠密连接的图，对$N$顶点图构造$N\times N$布尔矩阵，表示连接关系；对于有权图，矩阵元素为权重
邻接链表：适合稀疏连接的图，对$N$顶点图构造$N$元数组，存储链表头，每个链表元素为第$i$顶点的相邻顶点

基本算法

遍历

遍历是基本中的基本。经典方法：

其中使用visited记录遍历过的节点用来防止重复访问。

树作为简单的图，这两种方法也是经常使用的方法。

最短路径

这应该是非常经典的问题了，我们分两类：

BFS+队列搜索无权图最短路径
Dijkstra搜索有权图最短路径

对于无权图，常用方法是使用广度优先搜索（BFS）遍历整张图，找到终点时停止。BFS的遍历顺序满足了找到的一定是最短路径，实现起来通常结合队列。先将起点加入队列作为队头，再每次将距离为1的顶点加入队列，当所有距离为1的顶点入队后，若没有找到终点，则队头出队并记录为“已访问”，最短路径长度+1，再对新队头重复寻找距离为1且未访问过顶点的操作直至最终找到终点。

对于有权图，我们使用Dijkstra算法，维护一张路径表$T$。$T$可以定义为如下（假设起点为$v_1$）：

Node	Visited	$d$	$p$
$v_1$	0	0	0
$v_2$	0	$\infty$	0
…	…	…	…
$v_n$	0	$\infty$	0

这是一张初始化空表，记录每个节点是否已被访问过，从起点开始经过已访问节点到每个节点的最小距离$d$以及前一个节点$p$。

我们可以用合适的结构实现这个表，然后从起点开始反复更新这个表，更新访问状态、$d$和$p$，即Dijkstra所做的事情，用伪代码表示：

RoutineTable T;
while (1) {
    start = find_min_d_unvisited(T); // Find start for minimum d in unvisited nodes
    T[start].visited = 1; // Visit new start node
    for neighbor in adjacent(T[start]) {
        if (!neighbor.visited) {
            update(T[neighbor].d, T[neighbor].p); // Revise T with a possible shorter path
        }
    }
}

即，对于已经访问到的路径，如果找到一个新的邻接节点，检查新节点是否能让路径缩短，如果能，则更新为最短路径。记住，表$T$中记录的永远是从起点出发的最短路径！

所有节点全部访问过（visited）后，整幅图的路径全部探明，因此算法结束，从终点根据$p$回溯至起点即为最短路径。

Motivation

或许从Bellman方程上能更好理解Dijkstra算法的动机。Bellman方程描述的最短路径关系：

$$
D_{min}(s,t) = D_{min}(s,v) + \min{d(v,t)}
$$

上述Bellman方程使用类似递归的方式，定义了如何表示从点$s$到$t$的最短距离，其中$v$为中间节点。Bellman方程成立的条件是要求每次都要基于上次找到的最短路径$D_{min}(s,v)$，还要找到下一步走的最短路径$\min{d(v,t)}$。

那么Dijkstra算法就分别解决这两步，最开始寻找所有未访问节点中$d$最小的节点进行访问解决了$D_{min}(s,v)$是谁的问题，其中找到的那个节点就是中间节点$v$；然后在$v$的邻接节点中找到路径最短的那个，即确定了$\min{d(v,t)}$。因此Dijkstra最外层一轮循环之后等价于更新了一遍Bellman方程。所以算法实际上就是不断更新Bellman方程直到所有点全部访问完。

最大流

流问题是另一类图问题。…

Rikoの地下劇場