在这里，我们将讨论乘法哈希方法。为此，我们使用哈希函数 −ℎ(𝑥) = ⌊𝑚𝑥𝐴⌋ 𝑚𝑜𝑑 𝑚 这里 A 是一个实值常数。这种方法的优点是 m 的值不那么关键。我们也可以将 m 作为 2 的幂。虽然任何 A 值都可以给出哈希函数，但有些 A 值比其他值更好。根据 Knuth，我们可以使用黄金比例作为 A，所以 A 将是$$A=\frac{\sqrt5-1}{2}=0.61803398$$当然，无论选择什么 A 值。鸽巢原理意味着如果 u ≥ ... 阅读更多

在这里，我们将讨论除法哈希。为此，我们使用哈希函数 −ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚 要使用此哈希函数，我们维护一个数组 A[0, … m – 1]。其中数组的每个元素都是指向链接列表头的指针。指向数组元素 A[i] 的链接列表 Li 包含所有满足 h(x) = i 的元素 x。这种技术被称为链式哈希。在这样的哈希表中，如果我们想增加一个元素 x，这将花费 O(1) 时间。我们计算索引 i = h(x)。... 阅读更多

在这里，我们将讨论具有整数键的哈希表。这里的键值 𝑥 来自宇宙 𝑈，使得 𝑈 = {0, 1, … , 𝑢 – 2, 𝑢 – 1}。哈希函数是 ℎ。此哈希函数的域是 𝑈。范围在集合 {0, 1, … , 𝑚 – 1} 中，且 𝑚 ≤ 𝑢。如果对于每个 𝑥 ∈ 𝑆，ℎ(𝑥) 都是唯一的，则哈希函数 h 被称为集合 𝑆 ⊆ 𝑈 的完美哈希函数。𝑆 的完美哈希函数 ℎ 是最小的... 阅读更多

在这里，我们将看到如何从二叉最大堆数据结构中删除元素。假设初始树如下所示：删除算法 delete(heap, n) − 开始    如果堆为空，则退出    否则       item := heap[1]       last := heap[n]       n := n – 1       对于 i := 1, j := 2, j = heap[j]，则中断          heap[i] := heap[j]       完成    结束 if    heap[i] := last 结束示例假设我们想从最终堆中删除 30：

在这里，我们将看到如何从二叉最大堆数据结构中插入和删除元素。假设初始树如下所示：插入算法 insert(heap, n, item) − 开始    如果堆已满，则退出    否则       n := n + 1       对于 i := n, i > 1，在每次迭代中设置 i := i / 2，执行          如果 item

与二项堆一样，斐波那契堆是树的集合。它们松散地基于二项堆。与二项堆中的树不同，斐波那契堆中的树是根植的但无序的。斐波那契堆中的每个节点 x 包含一个指向其父节点的指针 p[x]，以及一个指向其任何一个子节点的指针 child[x]。x 的子节点通过一个称为 x 的子列表的循环双向链表连接在一起。子列表中的每个子节点 y 都具有指针 left[y] 和 right[y]，分别指向 y 的左兄弟和右兄弟。如果节点 y 只是... 阅读更多

二项堆是二项树的集合。二项树 Bk 是递归定义的有序树。二项树 B0 由单个节点组成。二项树 Bk 由两个二项树 Bk-1 组成。它们连接在一起。一个的根是另一个的左最子节点。一些二项堆如下所示：二项树的一些属性是：Bk 二项树具有 2k 个节点。树的高度是 k。在深度 i 处恰好有 $$\left(\begin{array}{c}k\ j\end{array}\right)$$ 个节点，对于 0 到 k 范围内的所有 i。二项堆一个二项堆... 阅读更多

在本节中，我们将看到欧拉图和哈密顿图。但在深入研究之前，首先我们必须了解图中的轨迹是什么。假设我们有一个如下图所示的图：轨迹是一条路径，它是一系列边 (v1, v2), (v2, v3), …, (vk - 1, vk)，其中所有顶点 (v1, v2, … , vk) 可能并不都不同，但所有边都不同。在这个例子中，一条轨迹是 {(B, A), (A, C), (C, D), (D, A), (A, F)} 这是一个轨迹。但这不被认为是简单的... 阅读更多

图的深度优先搜索是相似的。但是对于有向图或有向图，我们可以找到一些类型的边。DFS 算法形成一棵称为 DFS 树的树。有四种类型的边，称为：树边 (T) − 存在于 DFS 树中的那些边。前向边 (F) − 与一组树边平行。（从较小的 DFS 编号到较大的 DFS 编号，以及较大的 DFS 完成编号到较小的 DFS 完成编号）后向边 (B) − 从较大的 DFS 编号到较小的 DFS 编号，以及较小的 DFS 完成编号到较大的 DFS 完成编号。交叉... 阅读更多

我们知道图是一种非线性数据结构。在此数据结构中，我们将一些值放入节点中，并且节点通过不同的边连接在一起。当我们可以将数据存储到图结构中时，我们还需要从图中搜索元素才能使用它们。对于在图中搜索，有两种不同的方法。广度优先搜索和深度优先搜索技术。广度优先搜索 (BFS)广度优先搜索 (BFS) 遍历是一种算法，用于访问给定图的所有节点。在此遍历算法中，选择一个节点并... 阅读更多