Page 34 - 4800

ЛАБОРАТОРНА РОБОТА № 4
СПИСКИ І ПРОЦЕДУРИ ЇХ ОБРОБКИ

Мета роботи: Ознайомитися з використанням списків у Пролог-програмах та з
перетворенням набору фактів у списки. Вивчити рекурсивних процедур обробки
списків.

4.1 Списки як рекурсивні структури даних

Список – широко використовувана структура даних, яку зручно застосовувати
при рекурсивній обробці інформації, склад і кількість якої змінюється в ході процесу
обробки.
Список – упорядкована послідовність елементів, що може мати довільну
довжину. Елементами списку можуть бути будь-які терми:
– константи;
– змінні;
– структури, що можуть включати й інші списки.
Списки широко використовуються при створенні баз даних і знань, експертних
систем, карт міст, програм на ЕОМ і математичних об'єктів (графи, формули, функції).
Список – це або порожній список (записується в квадратних дужках []), що не
містить жодного елемента, або структура, що має у своєму складі два компоненти:
“голову” і “хвіст” списку.
“Голова” і “хвіст” списку є компонентами функтора, що позначається крапкою.
Наприклад, список, що складається з одного символьного елемента “а” може бути
записаний у вигляді. (а,[]) і його представлення у вигляді дерева має структуру,
наведену на рис 4.1, а.

a) (функтор) б)
a

b
а [] с []
(голова) (хвіст)
Рисунок 4.1 –
Представлення списку

Розглянемо ще один приклад. Нехай є список, що складається з трьох
символьних даних ’а’, ’b’, і ’с’, який можна записати у вигляді: (а, (b, (с, []))) або
представити у вигляді бінарного дерева, структура якого приведена на рис.4.1,б.
Запис складних списків за допомогою функтора не зручний, тому в Пролозі
використовується інша форма запису, при якій елементи списку заключаються у
квадратні дужки і розділяються комами. Так для розглянутих прикладів запис списків з
використанням скобкової форми запису буде мати вигляд: [а] та [а, b, c], відповідно.
Непорожній список можна розглядати як список, що складається з двох частин:
– першого елемента списку – голови списку;
– частини списку, що залишилася – хвоста списку.
Голова є елементом списку і є неподільною. Хвіст – це є список, що складається
з всіх елементів вихідного списку, за винятком першого елемента. Хвіст може бути
поділений і далі на голову і хвіст.
Виконуючи аналогічні операції, цей процес можна продовжувати, поки список
не стане порожнім. З цього випливає очевидний висновок, що список є рекурсивною
структурою даних.
У Пролозі введена спеціальна форма для представлення списку з “головою” Х и
“хвостом” Y, де для поділу на Х та Y використовується символ вертикальної риски,
тобто [Х | Y].
Використовуючи даний підхід, список [а, b, c] можна записати як [a | [b, c]]. Тут
“а” – голова списку, перший його елемент, а [b, c] – “хвіст” списку, частина списку, що
починається з другого елемента.

34