斯旺达克
发表于 2020年08月04日

数据结构学习

作为非计算机专业的学生，比别人起步晚，但是该迈过去的坎还是得迈过去。刚开始学习数据结构的时候，简单的浏览过一遍数据结构，但是现在只记得一些简单的数据结构了，而且平时用的非常少。现在又打算重新仔细地学习一下，也为了找工作做准备，写了好几年的代码，感觉对于数据结构又有了更多的认识，而且对模板和面向对象有更新的认识后，对于改造数据结构也开始有了一些感觉，所以想重新在梳理一遍。

求职考点

哈希、树的遍历六种方法是考的比较多的；

图中的广度优先搜索和深度优先搜索也是经常问到的。

表、栈和队列

随时都能手写一个ADT是基本功。ADT是抽象数据类型。

这应该也是STL学习中很重要的一环。

树

树有几个简单概念，比如结点，父节点和子节点关系通过指针实现；比如树叶指的是没有子嗣的结点。

  • 根的深度为0
  • 树叶的高度为0

树有个最大的优势是

  • 平衡树的最大深度不会超过O(logN)
  • 很多操作基于递归实现

树不一定要用指针实现，堆也是一种树，但是使用数组来实现的。

通过这两点可以让很多操作都实现O(logN)复杂度，因为执行过程经过的路径最大也就是O(logN)。但是由于不同操作会导致树越来越不平衡，尤其是insert和delete，所以有不同的学者提出了不同的平衡树。

有些情况下放弃了平衡条件，但是通过每次操作后进行一次自调整，可以实现在M次操作后最坏情形下实现O(MlogN)复杂度，摊还分析后每次操作平均是O(logN)的复杂度。

std::set和std::map都是用红黑树来实现的。

树的遍历

树的遍历有几种方式

  • 前序遍历：对任意结点，父节点在子节点之前被处理
  • 后续遍历：对任意结点，父节点在子节点后处理
  • 中序遍历：对任意结点，遍历方式都是从左子树，结点，右子树
  • 层序遍历：从深度最低的结点开始遍历

CRUD

平衡二叉树的CRUD操作都可以实现O(logN)复杂度，这是树的最大优势。

AVL树

根据结构性质插入数据后，当不满足平衡性质时，需要进行旋转：

对于一个结点，如果有两个树叶之间的高度大于2，则是不满足平衡性质的。设定M和N只能取{左，右}两个值，那么对于该节点的M子树和M子树的N子树来说，如果M=N进行单旋转；如果M！=N则进行两次单旋转，可以满足平衡性质。

单旋转只需要考虑两个节点，双旋转因为要两次单旋转需要考虑三个节点。

旋转函数的参数是指针的引用

void RotateWithLeftChild(AvlNode* & k2)
{
	AvlNode* k1=k2->left;
	k2->left=k1->right;
	k1->right=k2;
	k2->height=max{height(k2->left),height(k2->right)}+1;
	k1->height=max{height(k1->left),k2->height}+1;
	k2=k1;
}

这里最后的k2=k1的目的是，k2是指针的引用，通过把k1绑定到k2，让以前的k2的父结点有新的子节点k1。

伸展树

祖父G、父亲P和访问节点X三者之间关系，如果是zig-zag关系就是单旋转；如果是zig-zig关系就是双旋转。

伸展最终的目的是让访问的节点成为根节点。

优先队列

结构性质是子节点的值大于父节点，根是最小值；堆序性质是任何结点的左结点时该结点索引的两倍，右节点时该结点的索引两倍加一。

目的是为了实现增和删的复杂度都是O(logN)

堆的方法

增删通过空穴的上浮和下移来实现。增通过在数组最后增加一个空穴，然后根据堆序性质确定具体位置；删通过删除第一个元素即根元素实现空穴，再根据堆序性质确定具体位置。

值增加和减少会破坏堆序性质，需要进行上浮和下移操作。 数组构造堆(BuildHeap)，复杂度为O(N)到O(NlogN)。

如果要支持合并操作复杂度上界为O(logN)，那么有三种特殊堆：

  • 左式堆
  • 斜堆
  • 二项队列

不相交集类

等价关系满足三个形式：

  • 自反性
  • 对称性
  • 传递性

图论

基础概念包括

  • 顶点
  • 边
  • 权
  • 路径
  • 回路
  • 连通的无向图
  • 双连通的无向图(如果连通无向图中任意一个顶点删除后仍然是连通无向图)
  • 强连通的有向图
  • 弱连通的有向图（有向图不连通，但是基础图是连通的）
  • 完全图(任何两个顶点之间都有边)

向，环，连通，这三个性质是图中很重要的性质。

  • 向：邻接表中的都是单向，无向图需要在两个顶点的邻接表中都要存对方。
  • 连通：每个顶点之间都有路径
  • 环：边是互异的。所有无向图中(u,v)(v,u)不能组成环，而有向图中可以。

邻接表是表示图的标准方法；无向图的资源消耗比有向图多。

有向无环图(Directed Acyclic Graph)是很经典数据结构，比如区块链中就用到很多。

拓扑排序

邻接表表示有向图很方便，表示无向图时需要存储两倍数据。

入度指的是指向该顶点的边的数量。

邻接表，加上一个队列用于存储入度为零的顶点，可以提高简单拓扑排序的速率。简单的拓扑排序算法是不断找出入度为0的顶点，并将该点和其边删除，不断循环。算法复杂度是O(|E|+|V|)

无权有向图的最短路径算法

广度优先搜索(BFS)，通过一个队列实现，还未被处理的顶点的广度为无限大。广度为无限大的顶点出队，计算他的邻接点，如果需要入队则设置广度为无限大。复杂度为O(|E|+|V|)

加权有向图的最短路径算法

采用Dijkstra算法。只能用于权值为正的情况。 矩阵表，分别是序列idx，是否处理Known布尔值，最短路径长dv。如果要记录路径，需要增加一个前置顶点pv在矩阵表中。

  • 所有dv=INFINITY，所有known=false
  • 起点顶点的dv=0
  • 从起点出发，寻找邻接顶点，计算该邻接顶点的路径dv，当邻接顶点的known=true时比较dv大小选取较小值

存储Known和dv的数据结构的选择，需要根据E和V关系来选择：

如果图是稀疏的，也就是E比较少，那么需要用优先队列来存储所有dv和序列idx构成的结构体，这样在求min(dv)时可以以常数时间求得。

  • 用二叉堆查找邻接顶点时，一种方法时堆容器元素是个结构体，另一种是用一个std::array维护一个序列来查找，或者在堆中查找邻接顶点方便，可以使用配对堆。复杂度是O((|E|+|V|)log|V|)
  • 使用斐波那契堆可以有更好的复杂度O(|E|+|V|log|V|)

负值加权有向图的最短路径算法

需要用嵌套循环，算法复杂度是O(|E|*|V|)

最小生成树

连通图中生成树是存在所有结点的无环图。生成树不一定是唯一的，所以存在最小生成树。生成树的结构特性是，增加一条边形成的回路中减去任意一条边，则恢复生成树的结构特性。依据该特性，可以用贪心算法，得到最小生成树。

Prim算法

和Dijkstra算法类似，通过一个矩阵表来循环所有点，表中包括known布尔值，顶点dv(该顶点到所有known顶点最小值)和前置顶点pv。和Dijkstra区别在于更新法则是计算dw=min(dw,cwv)，其中cwv是w到v的权值。

  • dijkstra更新法则：当前顶点到初始顶点的路径长
  • prim更新法则：当前顶点dv值和邻接点值的最小值

kruskal算法

V颗树构成森林，最后又变成了一棵树。判定两条边是否需要连接，通过再森林构成的集合中实施find操作。

  • 将所有的边进行堆排序
  • 不断执行deleteMin操作直到宣称V-1条边
  • 堆中出队的边的两个顶点如果不在同一个森林中，则将该边加入森林

算法复杂度是O(|E|log|E|)，由于|E|=O(|V||V|)，因此实际上是O(|E|log|V|)。

深度优先搜索

dfs(){
	v.visted=true;
	for each Vertex w adjacent to v
		if(!w.visited)
			dfs(w)
}

由于顶点是有限个的，因此能够保证该算法最终会停止。且所有的边只会被访问一次，所以遍历时间能够保证为O(|E|+|V|)。

深度优先生成森林中的三种边：

  • 前向边：祖先结点指向后裔结点的虚线箭头；
  • 后向边：后裔结点指向祖先结点的虚线箭头；
  • 交叉边：不形成祖先或者后裔关系的两个结点之间的虚线箭头；

这三种边有一些性质可以用来判断图的性质：

  • 如果一个有向图没有后向边，则该有向图是无环的。

深度优先搜索可以用于判定图的性质。

  • 无向图：通过深度优先搜索，如果所有顶点被遍历，则该无向图是连通的。
  • 有向图：通过深度优先搜索，如果所有顶点被遍历，则该有向图是强连通的。
  • 连通图：通过深度优先搜索寻找割点，若没有割点，则该图是双连通图。

NP问题

计算机中有一类问题是non-deterministic问题，一种是recursively undecidable问题，递归不可判定的问题。NP问题是不可判定问题的一种，停机问题也是一种不可判定问题。

NP是non-deterministic polygonmial time既是不确定性的多项式复杂度时间的意思，表示该问题的算法复杂度是多项式时间的。我们通常希望的复杂度包括常数、对数、线性，最坏也应该是多项式时间。

排序

排序复杂度计算

定义逆序指对于i<j但a[i]>a[j]的序偶(i,j)。插入排序的运行时间是O(I+N)，其中I是逆序数量。

  • 插入排序(Inserting Sort)的思想是，在p位置之前的元素总是排序成功的。
  • 增量排序(Shell Sort)的思想是，设定一组增量hk,…,h2,h1，其中h1=1也就是相邻的排序。采用Hibbard增量可以实现最坏情形为O(N^(3/2))，采用Sedgewick增量可以实现O(N^(7/6))。
  • 堆排序(Heap Sort)的思想是，常数时间构建堆，然后执行常数deleteMin操作，算法复杂度为O(NlogN)
  • 归并排序(Merge Sort)，分治递归算法；数组分组，归并操作是将两个已经排序好的数组合并，该操作是线性复杂度
  • 快速排序(Quick Sort)，分治递归算法；集合拆分，通过枢纽元将集合拆分成大于枢纽元的集合和小于枢纽元的集合

间接排序的思路是，由于元素比较大，如果过多进行移动或者复制操作，会导致资源消耗非常大。因此采用指针数组，当排序结束后，进行最后的资源移动操作。

C++实现

在不同的实现中找到对应的算法，才能在真正的开发中使用起来。

STL中实现了

  • 单向链表：std::forward_list
  • 双向链表：std::list
  • 栈：std::stack
  • 队列：std::deque
  • 优先队列：std::priority_queue
  • 红黑树：在Windows中头文件xtree中有红黑树实现
  • 图：在Boost库中有adjacent_list和adjacent_matrix的实现