logo标签列表

在Lisp或Scheme中，循环列表有什么好处？

lispschemecircular-list
14

我注意到Scheme和Lisp（我猜）支持循环列表，并且我在C/C++中使用循环列表来“简化”元素的插入和删除，但是它们有什么用处？

Scheme确保它们可以构建和处理，但是用于什么目的？

是否存在需要循环或尾循环的“杀手级”数据结构？

我现在了解到Scheme的环境模型需要（太强？）循环列表：在环境中分配的过程“指向”它的环境 - 一个循环列表。 - philcolbourn
5个回答
6
说支持“循环列表”有点过了。在Lisp中，您可以构建各种循环数据结构，就像在许多编程语言中一样。在这方面，Lisp并没有什么特别之处。拿出你典型的“算法和数据结构”书籍，并实现任何循环数据结构：图形、环等。一些Lisp提供的是可以打印和读取循环数据结构。之所以支持这一点，是因为在典型的Lisp编程领域中，循环数据结构很常见：解析器、关系表达式、单词网络、计划等等。
数据结构包含循环是很常见的。真正的“循环列表”并不经常使用。例如，考虑一个任务调度程序，它运行一个任务，然后在一段时间后切换到下一个任务。任务列表可以是循环的，以便在“最后”任务之后，调度程序会执行“第一个”任务。事实上，没有“最后”和“第一个”，这只是一个任务的循环列表，调度程序无休止地运行它们。您还可以在窗口系统中拥有窗口列表，并使用某些键命令切换到下一个窗口。窗口列表可以是循环的。
当您需要廉价的下一个操作并且数据结构的大小事先未知时，列表很有用。您始终可以向列表添加另一个节点或从列表中删除节点。列表的常规实现使得获取下一个节点和添加/删除项变得便宜。从数组中获取下一个元素也相对简单（增加索引，在最后一个索引处转到第一个索引），但添加/删除元素通常需要更昂贵的移位操作。
此外，由于构建循环数据结构很容易，因此在交互式编程期间可能会这样做。如果然后使用内置例程打印循环数据结构，则最好打印机能够处理它，否则它可能会永远打印循环列表...
“支持”一词是指特定的语法，用于描述循环列表的读写（正如您所说）。例如：(#0=(1 2) (x y . #0#))；此外，Scheme的list?谓词指定循环列表不是列表——或者这是特定实现的结果？ - philcolbourn
好的，我可以看出任务调度器是一个循环列表。这是一个很好的例子。在LISP或Scheme中，你会如何插入或删除一个任务？ - philcolbourn
1
@philcolbourn 你提到的特定语法在Lisp中适用于所有带有循环的数据结构，而不仅仅是循环列表。你可以使用破坏性列表操作将对象添加到循环列表中。这是Lisp和/或编程课程中的典型编程练习... - Rainer Joswig
好的，那么循环链表使得访问下一个元素变得容易（没有基本情况），但需要使用非函数式的 set-car! 和 set-cdr! 操作来改变该列表。 - philcolbourn
4

你曾经玩过大富翁吗？

如果不考虑使用符号、模数等游戏元素，如何在计算机实现中表示大富翁棋盘呢？一个循环列表是很自然的。

2
你会如何在计算机实现游戏时表示大富翁棋盘？作为一个数组，这样我就不必在每次移动时遍历棋盘上的每个方格。 - Cam
说实话，你只需要保留一个指向当前方块的指针，这样你就不必那样做了。 - UK-AL
1
使用常规列表，您必须编写逻辑以告诉数组中的位置从末尾移动到开头。使用循环列表，无论如何，您都可以使用相同的逻辑：从当前位置移动X个位置。循环列表确实在这里是自然的选择。 - Dave
2

在列表的开头添加和删除元素是廉价的。要从列表的末尾添加或删除元素，您必须遍历整个列表。

使用循环列表，您可以拥有一种固定长度的队列。

设置一个长度为5的循环列表：

> (import (srfi :1 lists))
> (define q (circular-list 1 2 3 4 5))

让我们向列表中添加一个数字：

 > (set-car! q 6)

现在，让我们将其作为列表的最后一个元素：
 > (set! q (cdr q))

显示列表：
 > (take q 5)
 (2 3 4 5 6)

因此，您可以将其视为一个队列，在此队列中，元素从列表末尾进入并从头部移除。

让我们将7添加到列表中：

> (set-car! q 7)
> (set!     q (cdr q))
> (take q 5)
(3 4 5 6 7)

无论如何，这是我使用循环列表的一种方式。

我在一个OpenGL演示中使用了这种技术，该演示是我从Processing书籍中的一个示例移植而来。

Ed

用数组不是更容易吗？ - philcolbourn
2

例如，双向链表数据结构在Scheme/LISP的视角中是“循环”的，即如果您尝试将cons结构输出打印出来，则会得到反向引用，即“循环”。因此，它实际上不是关于具有看起来像“环”的数据结构，任何具有某种类型的反向指针的数据结构都是从Scheme/LISP的角度来看是“循环”的。

“正常”的LISP列表是单向链表，这意味着从列表中删除项目的破坏性突变是O(n)操作;对于双向链表，它是O(1)。这是双向链表的“杀手功能”，在Scheme/LISP上下文中是“循环”的。

你说“正常”的LISP列表是单向链接的 - 我理解。但是你是否也在说LISP / Scheme中的循环列表是双向链接的？ - philcolbourn
我认为他的意思是“如果你有一个双向链表，它就是循环的”。在Lisp/Scheme术语中，循环列表仅意味着列表中至少有一个引用指向更靠近开头的至少一个单元。 - Vatine
是的，他说双向链表满足“循环”的要求。 - Cam
在C语言中，双向链表不一定是循环的，尽管这可能是一种约定。我也认为删除操作不是O(1)，因为你需要遍历整个链表来查找要删除的元素。这将是O(n)，对吗？ - philcolbourn
在双向链表中删除“当前元素”是O(1)，而删除其他元素则是O(N)。在单向链表中删除“当前元素”是O(N)，但删除“当前元素后面的元素”是O(1)。 - Vatine
1
@philcolburn：C语言中的双向链表满足双向链表的最低标准，有一个指向“前一个”和“后一个”元素的引用。如果至少有一个元素可以沿着指针序列跟踪并最终回到原始元素，则该结构是循环的。 - Vatine
1
循环链表的一种用途是在使用srfi-1版本的map时“重复”值。例如，要将val添加到lst的每个元素中，我们可以编写以下代码：
(map + (circular-list val) lst)

例如：

(map + (circular-list 10) (list 0 1 2 3 4 5))

返回：

(10 11 12 13 14 15)

当然，您可以通过将+替换为(lambda (x) (+ x val))来实现此目的，但有时上述习惯用法可能更方便。请注意，这仅适用于srfi-1版本的map，该版本可以接受不同大小的列表。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接