Представление списков. список — это простая структура данных, широко используемая в нечисловом программировании

Список — это простая структура данных, широко используемая в нечисловом программировании. Список — это последовательность, составленная из произвольного числа элементов, например энн, теннис, том, лыжи. На Прологе это записывается так:

[ энн, теннис, том, лыжи ]

Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом [ ]. Во втором случае список следует рассматривать как структуру состоящую из двух частей:

(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).

Рандомно подобранные статьи с сайта:

2. Алгоритмы и структуры данных. Списки, стек, очередь, дек | Технострим


Похожие статьи:

admin