Domains

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 <> Nilthen

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. Элемент принадлежит хвосту списка.

На языке Паскаль алгоритм поиска элемента в списке можно реализовать следующим образом:

typeTList = ^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 получает два аргумента: искомый элемент и список, в котором производится поиск.

На языке Пролог алгоритм поиска элемента в списке можно реализовать следующим образом: