Представление списков. Список - это простая структура данных, широко используемая в нечисловом программировании
Список - это простая структура данных, широко используемая в нечисловом программировании. Список - это последовательность, составленная из произвольного числа элементов, например энн, теннис, том, лыжи. На Прологе это записывается так:
[ энн, теннис, том, лыжи ]
Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом [ ]. Во втором случае список следует рассматривать как структуру состоящую из двух частей:
(1) первый элемент, называемый головой списка;
(2) остальная часть списка, называемая хвостом.
Например, для списка
[ энн, теннис, том, лыжи ]
энн - это голова, а хвостом является список
[ теннис, том, лыжи ]
Подытожим:
- Список - это структура данных, которая либо пуста, либо состоит из двух частей: головы и хвоста. Хвост в свою очередь сам является списком.
- Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде
[ Элемент1, Элемент2, ... ]
или
[ Голова | Хвост ]
или
[ Элемент1, Элемент2, ... | Остальные]
Некоторые операции над списками
Списки можно применять для представления множеств, хотя и существует некоторое различие между этими понятиями: порядок элементов множества не существенен, в то время как для списка этот порядок имеет значение; кроме того, один н тот же объект может встретиться в списке несколько раз. Однако наиболее часто используемые операции над списками аналогичны операциям над множествами. Среди них
- проверка, является ли некоторый объект элементом списка, что соответствует проверке объекта на принадлежность множеству;
- конкатенация (сцепление) двух списков, что соответствует объединению множеств;
- добавление нового объекта в список или удаление некоторого объекта из него.
Составление программы для отношения принадлежности может быть основано на следующих соображениях:
· (1) Х есть голова L, либо
· (2) Х принадлежит хвосту L.
· Это можно записать в виде двух предложений, первое из которых есть простой факт, а второе - правило:
· принадлежит( X, [X | Хвост ] ).
· принадлежит ( X, [Голова | Хвост ] ) :-
принадлежит( X, Хвост).
Сцепление ( конкатенация)
Для сцепления списков мы определим отношение
Конк( L1, L2, L3)
Здесь L1 и L2 - два списка, a L3 - список, получаемый при их сцеплении.
На прологе это можно записать следующим образом:
конк( [X | L1, L2, [X | L3]):-
конк( L1, L2, L3).