数据结构与算法

25 篇

回溯算法

定义

回溯算法实际上一个类似枚举的深度优先搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回(也就是递归返回),尝试别的路径。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

继续阅读

数据结构与算法(二十三)——有向图

定义

一幅有方向性的图(有向图)是由一组顶点和一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点。

在一幅有向图中,一个顶点的出度为由该顶点指出的边的总数;一个顶点的入度为指向该顶点的边的总数。

一条有向边的第一个顶点称为它的,第二个顶点则被称为它的

继续阅读

数据结构与算法(二十二)——广度优先搜索

定义

给定一幅图和一个起点S,找到从S到给定目的顶点V的一条最短路径。

使用一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将顶点加入队列,然后重复以下步骤直到队列为空:

  • 取队列中的下一个顶点V并标记它。
  • 将与V相邻的所有未被标记过的顶点加入队列。

继续阅读

数据结构与算法(二十)——无向图

定义

图是由一组顶点和一组能够将两个顶点相连的边组成的。

enter image description here

当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并称该连接依附于这两个顶点。

某个顶点的度数即为依附于它的边的总和。子图是由一幅图的所有边的一个子集组成的图。

路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。是一条至少含有一条边且起点和终点相同的路径。简单环是一条不含有重复顶点和边的环。路径或环的长度为其中所包含的边数。

继续阅读

数据结构与算法(十九)——散列表

定义

如果所有的键都是小整数,可以用一个数组来实现无序的符号表,将键作为数组的索引而数组中键i处所储存的就是它对应的值。这样我们就可以快速访问任意键的值。

散列表是这种简易方法的扩展并能处理更加复杂的类型的键。我们需要用算术操作将键转化为数组的索引来访问数组中的键值对。

使用散列的查找算法分为两步。第一步是用散列函数将被查找的键转化为数组的一个索引。第二步是处理碰撞冲突的过程。

继续阅读

数据结构与算法(十八)——平衡查找树之红黑二叉查找树

定义

红黑二叉查找树是一种简单的数据结构,用来实现2-3树。

替换3-结点

红黑二叉查找树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。

我们将树中的链接分为两种类型,红链接将两个2-结点连起来构成一个3-结点,黑链接则是2-3树中的普通链接。

继续阅读

数据结构与算法(十七)——平衡查找树之2-3查找树

定义

二叉查找树在最快的情况下,性能还是很糟糕。

我们希望能够保持二叉查找树的平衡性。在一棵还有N个结点的树中,我们希望树的高度为logN,这样就能够保证所有的查找都能在logN次比较内结束。

2-3查找树允许树中的一个结点保存多个键。我们将一棵标准的二叉查找树中的结点称为2-结点(含有一个键和两条链接),现在引入3-结点,它含有两个键和三条链接。2-结点和3-结点中的每条链接都对应着其中保存的键所分割产生的一个区间。

继续阅读