Я отмечаю, что Scheme и Lisp (я думаю) поддерживают круговые списки, и я использовал круговые списки в C/С++ для "упрощения" вставки и удаления элементов, но для чего они хороши?
Схема гарантирует, что они могут быть построены и обработаны, но для чего?
Есть ли структура данных 'killer', которая должна быть круговой или круговой?
Говорить, что он поддерживает "циклические списки", немного. Вы можете создавать все виды круговых структур данных в Lisp. Как во многих языках программирования. В этом отношении нет особого значения Lisp. Возьмите свою типичную книгу "Алгоритмы и данные" и внедрите любую круговую структуру данных: графики, кольца... Что предлагает некоторые Lisp, так это то, что можно печатать и читать круговые структуры данных. Поддержка этого заключается в том, что в типичных областях программирования Lisp распространены круговые структуры данных: парсеры, реляционные выражения, сети слов, планы,...
Обычно структуры данных содержат циклы. Реальные "круговые списки" часто используются не так. Например, подумайте о планировщике задач, который запускает задачу и через некоторое время переключается на следующую. Список задач может быть круглым, так что после "последней" задачи планировщик берет "первую" задачу. На самом деле нет "последнего" и "первого" - это всего лишь круговой список задач, и планировщик запускает их без конца. Вы также можете иметь список окон в оконной системе, а с помощью некоторой ключевой команды вы переключитесь на следующее окно. Список окон может быть круглым.
Списки полезны, когда вам нужна дешевая следующая операция, и размер структуры данных неизвестен заранее. Вы всегда можете добавить еще один node в список или удалить node из списка. Обычные реализации списков позволяют получить следующий node и добавить/удалить элемент дешево. Получение следующего элемента из массива также относительно просто (увеличение индекса, при последнем индексе перейдите к первому индексу), но для добавления/удаления элементов обычно требуется более дорогостоящие операции смены.
Так же, как легко создавать круговые структуры данных, можно просто сделать это во время интерактивного программирования. Если вы затем распечатываете циклическую структуру данных со встроенными подпрограммами, было бы неплохо, если бы принтер мог ее обработать, так как в противном случае она может печатать круглый список навсегда...
Вы когда-нибудь играли в монополию?
Без игр с счетчиками и модулем и т.д., как бы вы представляли Monopoly board в компьютерной реализации игры? Циклический список является естественным.
Например, структура данных с двойным соединенным списком является "круговой" в точке зрения схемы / LISP, т.е. если вы пытаетесь распечатать контурную структуру, вы получаете обратные ссылки, то есть "циклы". Таким образом, это не значит, что структуры данных выглядят как "кольца", любая структура данных, в которой у вас есть какие-то backpointers, является "круговой" с точки зрения схемы /LISP.
"Обычный" LISP список является односвязным, что означает, что деструктивная мутация для удаления элемента из списка является операцией O (n); для двойных связанных списков это O (1). Это "функция убийцы" двойных связанных списков, которые являются "круговыми" в контексте Scheme/ LISP.
Добавление и удаление элементов в начало списка дешево. к добавьте или удалите элемент из конца списка, вам нужно пройти весь список.
С круговым списком вы можете иметь некоторую очередь фиксированной длины.
Настройте круговой список длины 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 demo, которую я портировал из примера в Обработка книги.
Ed
Одно использование круговых списков - это "повторять" значения при использовании версии карты srfi-1. Например, чтобы добавить 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, которая может принимать списки разных размеров.