[解决了]
所以我决定尝试创建一个排序的双向链接跳过列表...
我很确定我很清楚它是如何工作的 . 当您插入x时，程序会在基本列表中搜索放置x的适当位置（因为它已排序），（概念上）翻转硬币，如果“硬币”落在a上，那么该元素将被添加到上面的列表中（或者在其中创建带有元素的新列表），链接到其下面的元素，并再次翻转硬币等 . 如果“硬币”随时落在b上，则插入结束 . 您还必须在每个列表中存储-infinite作为起始点，以便无法插入小于起点的值（意味着永远无法找到它） .
要搜索x，您可以从“左上角”（最高列表最低值）开始，然后“向右移动”到下一个元素 . 如果值小于x，则继续下一个元素等，直到“走得太远”并且值大于x . 在这种情况下，您将返回到最后一个元素并向下移动一个级别，继续此链，直到您找到x或x从未找到 .
要删除x，您只需搜索x并在每次列表中删除时将其删除 .
现在，我只想制作一个存储数字的跳过列表 . 我不认为STL中有任何东西可以帮助我，所以我需要创建一个包含整数值的类List，并具有成员函数，搜索，删除和插入 .
我遇到的问题是处理链接 . 我很确定我可以用一个指向前一个元素和前面元素的指针来创建一个处理“水平”链接的类，但我不确定如何处理“垂直”链接（指向相应的元素）在其他名单？）
如果我的逻辑有任何缺陷，请告诉我，但我的主要问题是：
-
如何处理垂直链接以及我的链接想法是否正确
-
现在，我读了我的 class 列表想法，我非常积极，但只是想验证一下 .
-
I 'm assuming the coin flip would simply call int function where rand()%2 returns a value of 0 or 1 and if it' s 0然后是值"levels up"，如果它为0则插入结束 . 这不正确吗？
-
如何存储类似于-infinite的值？
编辑：我已经开始编写一些代码，我正在考虑如何处理List构造函数....我猜测它的构造，“-infinite”值应该存储在vectorname [0]元素中，我可以只需在创建后调用insert就可以将x放在适当的位置 .
3 回答
只需存储2个指针 . 一个在上面调用，一个在你的节点类中调用 .
不确定你的意思 .
根据wikipedia，您也可以进行几何分布 . 我不确定发布的类型是否对完全随机访问很重要，但如果你知道你的访问模式，这显然很重要 .
我不确定你的意思 . 您可以用浮点数表示类似的东西 .
http://msdn.microsoft.com/en-us/library/ms379573(VS.80).aspx#datastructures20_4_topic4
http://igoro.com/archive/skip-lists-are-fascinating/
上面的跳过列表是用C＃实现的，但可以使用该代码计算出c实现 .
你使“垂直”和“水平”太复杂了 . 它们都只是指针 . 你在纸上绘制的小盒子上有线条，只是为了在想到它们时帮助想象一些东西 . 您可以调用指针“elephant”，如果您需要，它将转到下一个节点 .
例如 . “next”和“prev”指针与“上方”/“下方”指针完全相同 .
无论如何，祝你的功课好运 . 在我的数据结构课中，我有一次相同的作业 .