На этом шаге мы рассмотрим построение кольцевых списков.
Все списочные структуры, которые мы рассматривали до сих пор, были свободны от циклов.
Под циклическим (кольцевым) списком понимается список, в котором указатель из некоторой ячейки направлен на такое место в списке, откуда данная ячейка может быть достигнута снова [2, с.37]. Циклические списки не допускают непосредственного представления в списочной нотации, но могут быть изображены с помощью графической нотации.
Например, следующие списки являются циклическими:
Рис.1. Примеры циклических списков
Такие списки невозможно построить, если единственным способом формирования новых начальных ячеек является только процедура CONS. Цикличность можно ввести только с помощью "Replace-функций" (заменяющих функций) RPLACA и RPLACD, изменяющих существующий список "физически".
Пример 1. Построение кольцевого списка.
Используя функцию RPLACD, можно определить функцию CIRCLE, превращающую список LST в кольцевой список.
(DEFUN CIRCLE (LAMBDA (LST)
(MAKE_CIRCLE LST LST)
))
; ------------------------------ ;
(DEFUN MAKE_CIRCLE (LAMBDA (LST Y)
( (NULL LST) LST)
( (NULL (CDR LST)) (RPLACD LST Y) )
( MAKE_CIRCLE (CDR LST) Y )
))
Пример 2 [1, с.136].
Предикат LCYCLEP возвращает значение T, если в значении аргумента есть цикл по цепочке CDD-указателей, и NIL в противном случае (в результате многократного применения функции CDR к значению аргумента можно получить атом).
(DEFUN LCYCLEP (LAMBDA (X)
(AND (NOT (ATOM X)) (NOT (ATOM (CDR X)))
(LCYCLE1 (CDR X) (CDDR X)))
))
; ------------------------ ;
(DEFUN LCYCLE1 (LAMBDA (X Y)
(OR (EQ X Y) (AND (NOT (ATOM Y))
(NOT (ATOM (CDR Y)))
(LCYCLE1 (CDR X) (CDDR Y)))
)
))
Тестовые примеры:
$ (LCYCLEP (A B C)) NIL $ (LCYCLEP (RPLACD (CDDR (A B C)) (A B C))) T $ (LCYCLEP (CONS X NIL)) NIL
Пример 3 [1, с.137].
Предикат CYCLEP возвращает значение T, если значение аргумента - циклическая списочная структура, и значение NIL, если в значении аргумента нет циклов (циклических цепочек указателей). Использует функцию CYCLE1, первый аргумент которой - одна из вершин (подструктур) списочной структуры, исследуемой в CYCLEP, второй аргумент - путь от этой вершины к исходной вершине, третий - список уже обследованных вершин.
(DEFUN CYCLEP (LAMBDA (X)
(NULL (CYCLE1 X NIL T))
))
; ------------------------- ;
(DEFUN CYCLE1 (LAMBDA (X U V)
(COND ( (ATOM X) V )
( (MEMBER X U) NIL )
( (MEMBER X V) V )
( (NULL (SETQ V (CYCLE1 (CAR X)
(SETQ U (CONS X U))
V))
)
NIL )
( (NULL (SETQ V (CYCLE1 (CDR X) U V))) NIL )
( T (CONS X V) )
)
))
(1)Лавров С.С., Силагадзе Г.С. Автоматическая обработка данных. Язык лисп и его реализация. - М.: Наука, 1978. - 176 с.
(2)Фостер Дж. Обработка списков. - М.: Мир, 1974. - 72 с.
На следующем шаге мы познакомимся с множествами .
