问题标签 [skip-lists]

我的跳过列表的删除方法正在无限循环中！我遵循了这个网站http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html的伪代码。除了删除之外，其他方法似乎工作正常。这是我的代码：

这是我的整个代码http://pastebin.com/StJRzixN
谢谢

我是一名 CS 学生，我的万圣节周末刚刚被我无法调试的编程作业毁了。这可能是这里为数不多的不会立即被标记为“重复”的问题之一。

分配是一个“跳过列表”或单链表（用 C 编程），其中每个节点都有一个可变大小的指针数组，由随机的“硬币”投掷决定。3 次成功的投掷导致高度为 3，依此类推。然后，每个数组都链接到具有相似高度的其他数组 - 第七层链接到下一个第七层，第六层到下一个第六层，一直到第一个或数组元素0，它自然地链接到列表中的下一个项目。

由于大多数项目没有更高的级别，因此这是在 log(n) 时间内搜索的好方法，而不是简单的 n。插入、删除和搜索的速度要快得多，但代价是内存成本更高。这只是理论 - 这是一张图片：跳过列表

你们中的许多人已经知道这些东西，但我只是想稍微解释一下，并表明我确实了解这里发生的事情的基础知识。

问题是一个随机的段错误，它用“CODE 6 - ABORT”消息搞砸了所有提供的测试。当我运行我的主文件时，我会在代码中的指定位置随机出现段错误（<-----Segfaults）——它发生在大约一半的时间，并且可以在任何一行。测试还给了我很多“错误指针”和“minmap 块错误”消息。

我对此束手无策。我在课堂上得了 93 分，但如果我不能完成这件可恶的事情，那分数就会下降到 87 分。

任何帮助表示赞赏，这是代码：

定义

造成随机故障的主要方法

...最后，魔鬼的数据结构：

包含和添加是问题所在，尽管可能还有其他问题。奇怪的是，这通常发生在我释放另一个列表之后，但我在我的代码中找不到任何工件。

如果你帮我解决这个问题，我会寄 20 美元和一盘饼干到你选择的地址。

所以我在学校一直在研究跳过列表，我们简要讨论了如果我们要在跳过列表中使用“不公平硬币”而不是公平硬币，（例如：不公平硬币翻转导致值“ Heads”设置为 p，其中 0 < p < 1（因此“Tails”的概率为 1 -p）。

由于我们这么快就跳过了这个话题，所以我对此有些疑惑，但我并不真正理解。

1. 如果我们这样做，跳过列表的高度/大小会发生什么变化？如果概率出现偏差，这显然会改变事情，对吧？假设它包含任意 n 个元素，显然高度会与我们使用公平硬币不同。

2. 将任意节点添加到跳过列表时，预期的促销数量将如何变化？我不知道在这种情况下是否会这样，但这是一个讨论话题。

我不是在找人在没有我真正理解的情况下给出答案，但如果你能真正解释为什么会发生这些变化，以便我能理解它是如何受到概率变化的影响的，我将不胜感激。

编辑：我想我在将不同概率与 Pat Morin 的《开放数据结构》一书第 99 页提供的方程式进行了一些比较后现在理解了。一旦我弄清楚了，我会在评论中发布我的解决方案，以帮助其他人解决同样的问题。

我正在努力使用 java 中的 skiplist 实现。基本上一切正常，但put方法执行时间太长。这是我的代码，我浏览过教程并查看了一些人的代码，但我似乎看不出问题出在哪里（如果您测量放置 100000 个随机元素需要很长时间才能工作）。

任何想法为什么要花这么长时间？

我正在尝试使用来自http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html的伪代码在 PHP 中实现一个跳过列表。我设法让它在 java 中正常工作，但在 PHP 中却不行。我的 put 方法总是返回 null，因此，我的 get 方法也返回 null。
我不太明白我要去哪里错了，所以我很感激任何帮助！

谢谢！

使用 skip-list 按字母顺序显示数据的时间复杂度是多少？如果我们使用四节点实现，跳过列表的时间复杂度是多少？

我有一个要求，我必须创建模板类的哨兵节点。哪个需要参考自己

现在我想做类似的事情

而且我不必通过一个，它让我默认构造函数不可用。

我需要创建一个跳过列表。这需要边界哨兵。

可以使用多个存储桶和索引线程并行创建哈希索引。

是否也可以将跳过列表索引的计算*分布在多个 CPU 内核上，或者数据结构是否固有地阻止了这种情况？

*建立索引，而不是索引利用率！

我试图了解跳过列表如何用于插入，但是当我将其绘制出来时，它不起作用。

所以我想在上面的链表上插入 5。

从第 0 行开始：从 -inf 开始，将 5 与 +inf 进行比较，移动到下一行。

移至第 1 行：

是 5 <= 4，不。比较右边的内容，+inf。从元素 4 向下移动到第 2 行。

移至第 2 行：

现在我们在 4 和 9 之间遍历，所以比较类似于 5 <= 4？不。是 5 <= 9 吗？是的。在 4 到 9 之间插入。

但是现在 5 没有出现在第 3 行？我究竟做错了什么？

我在尝试为我的跳过列表编写复制功能时遇到了问题。由于大部分课程已经完成，我不想改变我的设计。

每个节点有两个指针，一个指向同一层的下一个节点，另一个指向下一层的等效节点。在我的班级中，有一个向量存储指向每个级别的头节点的指针。

我的私人复制功能：

该函数在水平方向上正常工作，每个节点都复制并相互链接，但它不会垂直设置任何链接。
curr->below似乎不对，任何人都可以得到一些建议如何使这项工作？