我注意到 Scheme 和 Lisp（我猜）支持循环列表，并且我在 C/C++ 中使用循环列表来“简化”元素的插入和删除，但它们有什么用呢？
Scheme 确保它们可以被构建和处理，但是为了什么？
是否存在需要圆形或尾圆形的“杀手”数据结构？
问问题
4174 次
5 回答
6
说它支持“循环列表”有点过分。你可以在 Lisp 中构建各种循环数据结构。就像在许多编程语言中一样。Lisp 在这方面并没有什么特别之处。拿你典型的“算法和数据结构”一书来实现任何循环数据结构：图形、环……一些 Lisps 提供的是可以打印和读取循环数据结构。对此的支持是因为在典型的 Lisp 编程领域中，循环数据结构很常见：解析器、关系表达式、单词网络、计划……
数据结构包含循环是很常见的。真正的“循环列表”并不经常使用。例如，考虑一个任务调度程序，它运行一个任务并在一段时间后切换到下一个。任务列表可以是循环的，以便在“最后一个”任务之后调度程序执行“第一个”任务。事实上，没有“最后一个”和“第一个”——它只是一个循环的任务列表，调度程序无休止地运行它们。您还可以在窗口系统中拥有一个窗口列表，并使用一些键盘命令切换到下一个窗口。窗口列表可以是圆形的。
当您需要廉价的下一个操作并且数据结构的大小事先未知时，列表很有用。您始终可以将另一个节点添加到列表中或从列表中删除一个节点。列表的通常实现使获取下一个节点和添加/删除项目变得便宜。从数组中获取下一个元素也相对简单（增加索引，在最后一个索引处转到第一个索引），但添加/删除元素通常需要更昂贵的移位操作。
此外，由于构建循环数据结构很容易，因此可以在交互式编程期间进行。如果您随后使用内置例程打印循环数据结构，那么打印机可以处理它会是一个好主意，因为否则它可能会永远打印一个循环列表......
于 2010-03-07T09:33:51.780 回答
4
你玩过大富翁吗？
如果不玩计数器和模数等游戏，您将如何在游戏的计算机实现中表示大富翁棋盘？循环列表是很自然的。
于 2010-03-07T10:08:17.047 回答
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)
ETC...
无论如何，这是我使用循环列表的一种方式。
我在一个OpenGL 演示中使用了这种技术，该演示是从Processing book中的一个示例移植而来的。
埃德
于 2010-03-07T14:04:09.210 回答
2
例如，从 Scheme/LISP 的角度来看，双链表数据结构是“循环的”，即如果您尝试将 cons 结构打印出来，您会得到反向引用，即“循环”。因此，实际上并不是关于拥有看起来像“环”的数据结构，从 Scheme/LISP 的角度来看，任何具有某种反向指针的数据结构都是“循环的”。
“正常” LISP 列表是单链接的，这意味着从列表中删除项目的破坏性突变是 O(n) 操作；对于双链表，它是 O(1)。这是双链表的“杀手级功能”，在 Scheme/LISP 上下文中是“循环的”。
于 2010-03-07T06:50:41.040 回答
0
循环列表的一种用途是在使用 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，它可以接受不同大小的列表。
于 2011-05-21T06:03:33.803 回答