0

我想请教您对哪种类型的程序甚至技术的想法，以便我可以更好地向我的同行解释循环链接列表和跳过列表理论的有用性。

我的编程信念是，如果你给他们例子和隐喻，一个人可以更好地掌握一个概念。

只是您对要创建的示例程序或解决方案（编程技术或算法）的想法。

干杯!

4

3 回答 3

1

循环链表的一个很好的用途是作业调度系统，其中每个作业使用给定资源（例如简单操作系统中的进程）获得一定的时间。

在这种情况下，有一个特定的意义不大，head因为您总是在列表中循环，您所需要的只是current指针。您可以在当前作业之后添加新作业，并使用current查找要删除的作业。进入下一份工作很简单：

current = current->next

可能的跳过列表是列表形式的字典。您维护一个指向第一个单词的指针a，它包含一个指向 *a 的普通指针和一个指向*aaardvark的跳过指针。baa

*a：我实际上不知道它们是否是正确的词，但它们应该很接近，希望你能明白。

于 2011-03-14T05:53:07.363 回答
0

来自维基百科：

循环链表可能是表示自然循环数组的自然选项，例如多边形的角、按 FIFO 顺序使用和释放的缓冲区池，或应在循环中分时共享的一组进程-罗宾顺序。在这些应用程序中，指向任何节点的指针充当整个列表的句柄。

一个易于可视化的循环列表如何工作的示例可能是想象一群人站在一个圆圈中，每个人只知道他左边的人的名字。因此，要在组中搜索一个人，您从第一个人（在这种情况下为任意人）开始，然后移动到他知道名字的人（即在他的左边），直到找到您要找的人或来找谁再次回到第一人称。向该组添加或删除一个人只需将一个人从圈子中放置/带走并更改他右边的人知道的名字（如果是添加，则告诉他左边的人的名字） . 我希望这个例子有意义，它基本上是我在学习链表时用来可视化它的方式。

跳过列表支持快速 (O(log(n))) 操作，并且可以用作排序数据结构 - 很像平衡二叉搜索树。这使得它们在我们需要快速数据插入/删除时间（如链表但与数组不同）并且具有快速访问时间（如数组但与链表不同）的任何地方都很有用。它们也适用于进行快速范围查询（例如，查找结构的索引 [i,j] 中所有元素的总和（或最大值、最小值、乘积等））。

对于跳过列表，我想不出一个足够简单的现实世界隐喻，数据结构看起来比我在日常生活中可以看到的任何对象都复杂得多。但是维基百科的解释很清楚，通过证明和算法来构建它应该是一个很好的起点。这是原始论文的链接，IMO 也非常易读。

于 2011-03-14T05:55:24.630 回答
0

跳过列表基本上是放置在常规排序链表顶部的一组附加列表（或真正的链接），以帮助搜索列表。

跳过列表在常规链表之上创建了一种二叉搜索树，因此搜索操作需要 O(log N) 时间而不是 O(N) 时间，从而使它们更快。您可以在任何想要使用常规链表但需要更快访问的地方使用它们。

以下页面有一个非常好的、易于理解的关于跳过列表的讨论：http: //igoro.com/archive/skip-lists-are-fascinating/

于 2011-03-14T06:05:53.727 回答