9 1 Представление списков Сортировка
9. 1. Представление списков. Сортировка...
9 1 1 Замечания в некоторых альтернативных способах представления списков
9. 1. 1. Замечания в некоторых альтернативных способах представления списков
В главе 3 была введена специальная система обозначений для списков (специальная прологовская нотация)...
Упражнения
Упражнения
9. 1. Определите отношение
список( Объект)
для распознавания случаев, когда Объектявляется стандартным прологовским списком.
Посмотреть ответ...
9 1 2 Сортировка списков
9. 1. 2. Сортировка списков
Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изл...
Рисунок 9 1 Сортировка списка процедурой быстрсорт
Рисунок 9. 1. Сортировка списка процедурой быстрсорт.
встав( X, [Y | УпорСпис], [Y | УпорСпис1]):- &...
Рисунок 9 2 Быстрая сортировка
Рисунок 9. 2. Быстрая сортировка.
становится тривиальной операцией после применения разностного представления списков, введенного в гл. 8. Для того, чтобы использовать эту идею в нашей проце...
Рисунок 9 3 Более эффективная
Рисунок 9. 3. Более эффективная реализация процедуры быстрсортс использованием разностного представления списков. Отношениеразбиение( Х, Спис, Меньш, Больш)определено, как на Рисунок 9.2.
бы...
Упражнения
Упражнения
9. 5. Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:
?- слить( [2, 5, 6, 6, 8],...
9 2 Представление множеств двоичными деревьями
9. 2. Представление множеств двоичными деревьями
Списки часто применяют для представления множеств. Такое использование списков имеет тот недостаток, что проверка принадлежности...
Рисунок 9 4 Двоичное дерево
Рисунок 9. 4. Двоичное дерево.
Существует более эффективный и более привычный способ представления двоичных деревьев: нам нужен специальный символ для обозначения пустого дерева и функтор дл...
Рисунок 9 5 Представление двоичных деревьев
Рисунок 9. 5. Представление двоичных деревьев.
Эти правила непосредственно транслируются на Пролог следующим образом:
внутри( X, дер( -, X, -) ).
&...
Рисунок 9 6 Двоичный справочник Элемент 6 найден после прохода по отмеченному пути 5>8>6
Рисунок 9. 6. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5-->8-->6.
Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если...
Рисунок 9 7 Поиск элемента Х в двоичном справочнике
Рисунок 9. 7. Поиск элемента Х в двоичном справочнике....
Рисунок 9 8 (а) Дерево Д построенное
Рисунок 9. 8. (а) Дерево Д, построенное как результат достижения целей: внутри( 5, Д), внутри( 3, Д), внутри( 8, Д). (b) Дерево, получ...
Упражнения
Упражнения
9. 9. Определите предикаты
двдерево( Объект) справочник( Объект)
распознающие, явл...
9 3 Двоичные справочники добавление и удаление элемента
9. 3. Двоичные справочники: добавление и удаление элемента
Если мы имеем дело с динамически изменяемым множеством элементов данных, то нам может понадобиться внести в него новый...
Рисунок 9 9 Введение в двоичный
Рисунок 9. 9. Введение в двоичный справочник нового элемента на уровне листьев. Показанные деревья соответствуют следующей последовательности вставок:добавить( Д1, 6, Д2), добавить( Д2, 6, Д...
Рисунок 9 10 Вставление в двоичный справочник нового элемента в качестве листа
Рисунок 9. 10. Вставление в двоичный справочник нового элемента в качестве листа.
Определим отношение добавить. Простейший способ: ввести новый элемент на самый нижний уровень дерева, так чт...
Рисунок 9 11 Удаление X из двоичного
Рисунок 9. 11. Удаление X из двоичного справочника. Возникает проблема наложения "заплаты" на место удаленного элемента X.
операции добавления листа:
...
Рисунок 9 12 Заполнение пустого места после удаления X
Рисунок 9. 12. Заполнение пустого места после удаления X.
то можно использовать следующую идею (Рисунок 9.12): если самую левую вершину Y поддерева Правпереместить из ее текущего положения в...
Рисунок 9 13 Удаление элемента из двоичного справочника
Рисунок 9. 13. Удаление элемента из двоичного справочника.line();
Для того, чтобы добавить Х в двоичный справочник Д, необходимо одно из двух:
добавить Х на место корня дерева (так, что Х...
Рисунок 9 14 Внесение Х в двоичный справочник в качестве корня
Рисунок 9. 14. Внесение Х в двоичный справочник в качестве корня.
Ответ мы получим, если учтем следующие ограничения на L1, L2:
L1 и L2 - двоичные справочники; множество всех вершин, содер...
Рисунок 9 15 Внесение элемента на произвольный уровень двоичного справочника
Рисунок 9. 15. Внесение элемента на произвольный уровень двоичного справочника.
На Рисунок 9.15 показана программа для "недетерминированного" добавления элемента в двоичный справоч...
9 4 Отображение деревьев
9. 4. Отображение деревьев
Так же, как и любые объекты данных в Прологе, двоичное дерево Т может быть непосредственно выведено на печать при помощи встроенной процедуры write. Од...
Рисунок 9 16 (а) Обычное изображение
Рисунок 9. 16. (а) Обычное изображение дерева. (b) То же дерево,отпечатанное процедурой отобр (дуги добавлены для ясности)...
Рисунок 9 17 Отображение двоичного дерева
Рисунок 9. 17. Отображение двоичного дерева....
Упражнение
Упражнение
9. 14. Наша процедура изображает дерево, ориентируя его необычным образом: корень находится слева, а листья - справа. Напишите (более сложную) процедуру для отображени...
9 5 Графы
9. 5. Графы...
9 5 1 Представление графов
9. 5. 1. Представление графов
Графы используются во многих приложениях, например для представления отношений, ситуаций или структур задач. Граф определяется как множество вершинв...
Рисунок 9 18 (а) Граф (b) Направленный граф Каждой дуге приписана ее стоимость
Рисунок 9. 18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.
Для представления направленного графа...
9 5 2 Поиск пути в графе
9. 5. 2. Поиск пути в графе
Пусть G - граф, а А и Z - две его вершины. Определим отношение
путь( А, Z, G, Р)
где Р - ациклический путь...
Рисунок 9 20 Поиск в графе Граф ациклического пути Путь из А в Z
Рисунок 9. 20. Поиск в графе Графациклического пути Путь из А в Z.
На Рисунок 9.20 программа показана полностью. Здесь принадлежит- отношение принадлежности элемента списку. Отношение
...
Рисунок 9 21 Поиск пути в графе Путь путь между А и Z в графе Граф стоимостью Ст
Рисунок 9. 21. Поиск пути в графе: Путь - путь между А и Z в графе Графстоимостью Ст.
Эту процедуру можно использовать для нахождения пути минимальной стоимости. Мы можем построить путь мини...
9 5 3 Построение остовного дерева
9. 5. 3. Построение остовного дерева
Граф называется связным, если между любыми двумя его вершинами существует путь. Пусть G = (V, Е) - связный граф с мн...
Рисунок 9 23 Построение остовного
Рисунок 9. 23. Построение остовного дерева: "декларативный подход".Отношения вершина и смежсм. на Рисунок 9. 22....
Упражнение
Упражнение
9. 15. Рассмотрите остовные деревья в случае, когда каждому ребру графа приписана его стоимость. Пусть стоимостьостовного дерева определена как сумма стоимостей составляющих его ребер....
Резюме
Резюме
В данной главе мы изучали реализацию на Прологе некоторых часто используемых структур данных и соответствующих операций над ними. В том числе
Списки: &nbs...
Литература
Литература
В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограм...
