129. Структуры данных, используемые в пролог программе

Пролог – язык программирования, используемый для решения задач, сводимых к объектам и отношениям между объектами. Пролог применяется в тех случаях, когда необходимо использовать ЭВМ для решения задачи, которая может быть выражена в терминах объектов и отношений между ними.

Пролог-программы состоят из термов. Терм – это либо константа, либо переменная, либо структура.

Константы - это поименованные конкретные объекты или отношения.

Переменными в Прологе являются строки символов, цифр и символа подчеркивания, начинающиеся с заглавной буквы или символа подчеркивания.

Структурированный терм (структура)- это единый объект, состоящий из совокупности других объектов, называемых компонентами. Компоненты в свою очередь могут быть также структурами. Название структуры стоит перед скобками, а компоненты внутри скобок, через запятую. Название структуры - функтор. Пример: треугольник (точка(1,1), точка(2,2), точка(3,3)).

Название структуры – треугольник, она имеет три компонента. Компоненты внутри скобок сами являются структурированными термами с функтором – точка. Структура точка имеет два компонента.

Количество компонентов структуры называют арностью функтора.

Списки - одна из наиболее часто употребляемых структур в Прологе. При записи список заключают в квадратные скобки, а элементы списка разделяют запятыми: [слон, лошадь, обезьяна, собака]

Это список из четырех атомов - слон, лошадь, обезьяна, собака.

Элементами списка могут быть любые термы Пролога, т. е. атомы, числа, переменные и составные термы, что позволяет, в частности, составлять списки из списков. Пустой список записывается как [ ].

Первый элемент непустого списка называется головой, а остальная часть списка носит название хвост. У списка, состоящего только из одного элемента, головой является этот единственный элемент, а хвостом - пустой список. Обозначение [H|T] используется для представления списка с головой H и хвостом T. Если символ | помещен перед последним термом списка, то это означает, что этот последний терм определяет другой список. Полный список получится, если соединить этот подсписок с последовательностью элементов, расположенных до черты.

Разностные списки

Обычные и разностные списки тесно связаны. И те, и другие используются для представления последовательностей элементов. Любой список L может быть тривиально представлен как разностный список L\[ ]. Пустой список представляется посредством любого разностного списка, голова и хвост которого одинаковы, наиболее общей формой при этом будет разностный список As\As.

Для обозначения разности двух списков будем использовать структуру As\Bs. которая названа разностным списком. В этой структуре As- голова разностного списка, а Вs-его хвост. Для рассмотренного примера [1,2,3 | Xs] \ Xs есть наиболее общий разностный список, представляющий последовательность 1,2,3 (здесь [1,2,3 | Xs] - голова, а Xs- хвост разностного списка).

Возможность улучшения программ связана с эффективностью соединения разностных списков. Два неполных разностных списка могут быть соединены для образования третьего разностного списка за константное время. В противоположность этому соединение обычных списков с использованием стандартной программы append происходит за линейное время, пропорциональное длине первого списка.

Разностные структуры, справочники, очереди.

Бинарные деревья

Типы данных являются рекурсивными, если они допускают, чтобы в его структуре данных была рекурсия. Примером являются бинарные деревья.

Бинарное дерево – структура данных, которая либо пуста, либо состоит из трёх компонентов: корень, левое поддерево, правое поддерево, где левое и правое поддеревья это бинарные деревья.

Бинарное дерево упорядочено, если в нём все вершины левого поддерева меньше корня, все вершины правого поддерева больше корня.

Бинарный справочник – это бинарное дерево, у которого все вершины левого поддерева меньше корня, а все вершины правого поддерева больше корня и оба поддерева упорядочены.