c++ - 在 C++ 中实现跳跃列表

Question

[已解决]

所以我决定尝试创建一个排序的双向链接跳跃列表...

我很确定我很好地掌握了它的工作原理。当您插入 x 时，程序会在基本列表中搜索放置 x 的适当位置(因为它已排序)，(概念上)抛硬币，如果“硬币”落在 a 上，则该元素将添加到它上方的列表中(或者创建一个包含元素的新列表)，链接到它下面的元素，然后再次抛硬币，等等。如果“硬币”在任何时候落在 b 上，则插入结束。您还必须在每个列表中存储一个 -infinite 作为起点，这样就不可能插入一个小于起点的值(意味着永远找不到它。)

要搜索 x，您可以从“左上角”(最高列表最低值)开始，然后“向右移动”到下一个元素。如果该值小于 x，则继续下一个元素，依此类推，直到您“走得太远”并且该值大于 x。在这种情况下，您返回到最后一个元素并向下移动一个级别，继续此链，直到您找到 x 或永远找不到 x。

要删除 x，您只需搜索 x 并在每次出现在列表中时将其删除。

现在，我只想制作一个存储数字的跳表。我认为 STL 中没有任何东西可以帮助我，所以我需要创建一个类 List，它包含一个整数值并具有成员函数、搜索、删除和插入。

我遇到的问题是处理链接。我很确定我可以创建一个类来处理带有指向前一个元素和前面元素的指针的“水平”链接，但我不确定如何处理“垂直”链接(指向相应的元素在其他列表中？)

如果我的逻辑有任何缺陷请告诉我，但我的主要问题是:

1. 如何处理垂直链接，我的链接思路是否正确
2. 既然我读了我的 List 类想法，我认为 List 应该包含一个整数 vector 而不是一个整数。事实上，我非常肯定，但只是想要一些验证。
3. 我假设抛硬币会简单地调用 int 函数，其中 rand()%2 返回值 0 或 1，如果它是 0，则值“升高”，如果它是 0，则插入结束。这是不正确的吗？
4. 如何存储类似于-infinite 的值？

编辑:我已经开始编写一些代码并正在考虑如何处理 List 构造函数....我猜测在其构造中，“-infinite”值应该存储在 vectorname[0] 元素中我可以在它创建后对其调用 insert 以将 x 放在适当的位置。

Answer 1

http://msdn.microsoft.com/en-us/library/ms379573(VS.80).aspx#datastructures20_4_topic4

http://igoro.com/archive/skip-lists-are-fascinating/

上述跳过列表是用 C# 实现的，但可以使用该代码制定出 C++ 实现。