name_of_list_type = type_of_elements*
Здесь name_of_list_type является доменом списка элементов типа type_of_elements. Например, тип list, описывающий список целых чисел, можно объявить следующим образом:
Domains
list = integer*
Составной список – это список элементов, принадлежащих разным типам. Для представления составного списка в Прологе все его элементы должны быть объявлены через функторы.
Например,
llist = l(list); s(symbol); i(integer); c(char)
list = llist*
Тогда список [a, 1, [b, c]] будет представлен следующим образом: [s(a), i(1), l([s(b), s(c)])].
Выполнение работы
Рекурсивные алгоритмы как нельзя лучше подходят для обработки рекурсивных структур данных.
Прохождение бинарных деревьев
Рассмотрим алгоритм обхода бинарного дерева в симметричном порядке. Этот алгоритм рекурсивен по своей природе и сводится к следующим шагам:
1. Пройти в симметричном порядке левое поддерево.
2. Попасть в корень.
3. Пройти в симметричном порядке правое поддерево.
На языке Паскаль этот алгоритм можно записать следующим образом:
type TPNode = ^Tree;
Tree = record
Element: string;
Left, Right: TPNode;
end;
procedure PBDSP (PTree: TPNode);
Begin
if PTree <> Nil then
begin PBDSP (PTree^.Left);
Writeln (PTree^.Element);
PBDSP (PTree^.Right)
End
end;
На языке Пролог симметричный порядок обхода дерева можно представить так:
traverse(empty).
traverse(
tree(Element, Left, Right)):-traverse(Left),
write(Element), nl,
traverse(Right).
Обработка списков
В качестве примера работы со списками рассмотрим процедуру поиска элемента в списке. Поиск представляет собой просмотр списка на предмет выявления соответствия между элементом данных (объектом поиска) и элементом просматриваемого списка. Если такое соответствие найдено, то поиск заканчивается успехом. В противном случае поиск заканчивается неуспехом. Элемент принадлежит списку, если выполняется одно из условий:
1. Элемент совпадает с головой списка.
2. Элемент принадлежит хвосту списка.
На языке Паскаль алгоритм поиска элемента в списке можно реализовать следующим образом:
type TList = ^TElemList;
TElemList = record;
Inf: char;
Next: TList;.
end;
function Find(Elem:Сhar; List:TList):boolean;
Begin
{Проверяется случай, когда список пуст}
if (List = Nil) then Find:=false
{Рассматривается случай, когда список не пуст}
else {искомый элемент совпадает с головой списка}
if List^.Inf = Elem then Find:= true
{иначе ищем элемент в хвосте списка}
else Find:= Find(Elem, List^.Next);
end;
Функция Find получает два аргумента: искомый элемент и список, в котором производится поиск.
На языке Пролог алгоритм поиска элемента в списке можно реализовать следующим образом:
