问题标签 [clrs]

根据 StackOverflow 播客第 57 集的建议，我购买了“计算机程序的结构和解释”、“C 编程语言”、“Unix 编程环境”和“算法简介”。我想提高我的基本编程技能，为一些开源项目做出贡献，并改善我未来的就业前景。所选文本是否有建议的阅读顺序？另外，我应该更加注意书中的哪些特定主题/部分？谢谢。

您有一个有偏差的随机数生成器，它以概率 p 生成 1，以概率 (1-p) 生成 0。你不知道 p 的值。使用它可以生成一个无偏随机数生成器，它以 0.5 的概率生成 1，以 0.5 的概率生成 0。

注意：这个问题是 Cormen，Leiserson，Rivest，Stein 的算法介绍中的一个练习问题。（clrs）

我的作业是算法介绍练习11.1-3，内容如下：

建议如何实现一个直接访问表，其中存储元素的键不需要是不同的，并且元素可以有卫星数据。所有三个字典操作（插入、删除和搜索）都应该在 O(1) 时间内运行。不要忘记 Delete 将指向要删除的对象的指针作为参数，而不是键。

好吧，插入是没有问题的，因为它只是意味着在表中的适当位置创建一个链表（如果它不存在）并将元素添加到其中。给定一个键的搜索可以返回任何与该键匹配的元素，所以它只是意味着我们需要返回表中匹配列表的头部。

我的问题是删除操作。如果我修改对象以向其添加指向其在链表中的节点的指针，那么我可以在O(1)中删除，但我不确定是否允许更改该对象。有没有办法在不改变给定对象的情况下做到这一点？

我想知道在计算机科学背景下对“祖先”定义的共识是什么。

我只问是因为在《算法导论》，第二版，p。259 有一个算法的描述Tree-Successor(x)看起来很奇怪。在寻找节点x的后继者时，

[...] 如果节点x的右子树为空且x有后继y，则y是x的最低祖先，其左孩子也是x的祖先。

在一个根有 key2和 children的二叉搜索树1中3， 的后继1是它的 parent 2。在这种情况下，x是x的继任者y的左孩子。那么，根据本书的定义，x必须是它自己的祖先，除非我遗漏了什么。

我在勘误表中没有找到任何关于此的内容。

我的上一个 CLRS 问题取得了成功，这是另一个：

在《算法导论》，第二版，p。501-502，描述了不相交集的链表表示，其中每个列表成员维护以下三个字段：

• 集合成员
• 指向next对象的指针
• 指向第一个对象（集合representative）的指针。

尽管链表可以通过仅使用一个“链接”对象类型来实现，但教科书显示了一个辅助“链表”对象，其中包含指向“头”链接和“尾”链接的指针。拥有指向“尾部”的指针有助于Union(x, y)操作，因此无需遍历较大集合x中的所有链接即可开始将较小集合的链接附加y到它。

但是，为了获得对尾链接的引用，似乎每个链接对象都需要维护第四个字段：对 Linked List 辅助对象本身的引用。在这种情况下，为什么不完全删除 Linked List 对象并使用第四个字段直接指向尾部呢？

你会认为这是文本中的遗漏吗？

我正在阅读 CLRS 的“算法简介”。在第 2 章中，作者提到了“循环不变量”。什么是循环不变量？

在“算法简介，第 3 版”练习 24.3-5 中想要一个例子说明这是错误的（并不总是正确的）。那可能吗？在我看来，这是不可能的，因为在已经确定了到当前顶点的路径时，每条边都会放松。

一个字一个字地：

N. 教授声称拥有 Dijkstra 算法正确性的证明。他声称 Dijkstra 的算法按照它们在路径上出现的顺序松弛了图中每条最短路径的边，因此路径松弛特性适用于从源可到达的每个顶点。证明教授错误地构造了一个有向图，Dijkstra 的算法可以针对该有向图放宽最短路径的边缘无序。

不知道我是否应该把它放在数学 stackexchange 上，但是哦。

在 CLRS 的第 300 页...

他们定义了3个随机变量......

和指标随机变量Zn,1 Zn,2 Zn,3 ... Zn,n...

因此，他们继续进行证明（见正文），但在此过程中，他们提出了以下主张……

对于 Yn-i 也是如此。我的问题是那部分，除了它包含的键的数量......是的，子树的结构不受 Rn 的影响，但是 Rn 影响子树中键的数量这一事实似乎暗示了依赖于如何它限制了子树的高度。

我显然错过了一些关键的关系。任何帮助表示赞赏，谢谢。

在介绍算法第三版时，他们有一个红黑树删除的伪代码实现。这里是...

TREE-MINIMUM 只是找到树中的最小值，RB-TRANSPLANT 获取第二个参数的父节点并让它指向第三个参数，并让第三个参数的父节点成为第二个参数的父节点。

根据我的评论，他们测试 yp 是否为 z，如果是，则将 xp 设置为 y。但是 x 已经是 y.right，所以这就像说 y.right.p = y，但是 y.right.p 已经是 y！他们为什么这样做？

这是他们的解释...

“但是，当 y 的原始父节点是 z 时，我们不希望 xp 指向 y 的原始父节点，因为我们正在从树中删除该节点。因为节点 y 将向上移动以占据 z 在树中的位置，所以在第 13 行将 xp 设置为 y 会导致 xp 指向 y 的父节点的原始位置，即使 x == T.nil。”</p>

所以他们想让 x 的父母成为 y……它已经是 y……

此实现源自 CLRS 第 2 版（第 894 页）。while(1)在我看来很可疑。while 循环的终止条件应该是什么？

我试过k<=n了，但这似乎不起作用。我得到分段错误。代码中的缺陷是什么以及如何纠正它？