3.1. Представление списков

3.1. Представление списков

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

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

Однако таково лишь внешнее представление списков. Как мы уже видели в гл. 2, все структурные объекты Пролога — это деревья. Списки не являются исключением из этого правила.

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

(1) первый элемент, называемый головой списка;

(2) остальная часть списка, называемая хвостом.

Например, для списка

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

энн — это голова, а хвостом является список

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

В общем случае, головой может быть что угодно (любой прологовский объект, например, дерево или переменная); хвост же должен быть списком. Голова соединяется с хвостом при помощи специального функтора. Выбор этого функтора зависит от конкретной реализации Пролога; мы будем считать, что это точка:

.( Голова, Хвост)

Поскольку Хвост — это список, он либо пуст, либо имеет свои собственную голову и хвост. Таким образом, выбранного способа представления списков достаточно для представления списков любой длины. Наш список представляется следующим образом:

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

На рис. 3.1 изображена соответствующая древовидная структура. Заметим, что показанный выше пример содержит пустой список []. Дело в том, что самый последний хвост является одноэлементным списком:

[ лыжи ]

Хвост этого списка пуст

[ лыжи ] = .( лыжи, [] )

Рассмотренный пример показывает, как общий принцип структуризации объектов данных можно применить к спискам любой длины. Из нашего примера также видно, что такой примитивный способ представления в случае большой глубины вложенности подэлементов в хвостовой части списка может привести к довольно запутанным выражениям. Вот почему в Прологе предусматривается более лаконичный способ изображения списков, при котором они записываются как последовательности элементов, заключенные в квадратные скобки. Программист может использовать оба способа, но представление с квадратными скобками, конечно, в большинстве случаев пользуется предпочтением. Мы, однако, всегда будем помнить, что это всего лишь косметическое улучшение и что во внутреннем представлении наши списки выглядят как деревья. При выводе же они автоматически преобразуются в более лаконичную форму представления. Так, например, возможен следующий диалог:

?- Список1 = [а, b, с],

 Список2 = (a, .(b, .(c,[]) ) ).

Список1 = [а, b, с]

Список2 = [а, b, с]

?- Увлечения1 = .( теннис, .(музыка, [] ) ),

 Увлечения2 = [лыжи, еда],

 L = [энн, Увлечения1, том, Увлечения2].

Увлечения1 = [теннис, музыка]

Увлечения2 = [лыжи, еда]

L = [энн, [теннис, музыка], том, [лыжи, еда]]

Рис. 3.1. Представление списка [энн, теннис, том, лыжи] в виде дерева.

Приведенный пример также напоминает вам о том, что элементами списка могут быть любые объекты, в частности тоже списки.

На практике часто бывает удобным трактовать хвост списка как самостоятельный объект. Например, пусть

L = [а, b, с]

Тогда можно написать:

Хвост = [b, с] и L = .(а, Хвост)

Для того, чтобы выразить это при помощи квадратных скобок, в Прологе предусмотрено еще одно расширение нотации для представления списка, а именно вертикальная черта, отделяющая голову от хвоста:

L = [а | Хвост]

На самом деле вертикальная черта имеет более общий смысл: мы можем перечислить любое количество элементов списка, затем поставить символ "|", а после этого — список остальных элементов. Так, только что рассмотренный пример можно представить следующими различными способами:

[а, b, с] = [а | [b, с]] = [a, b | [c]] = [a, b, c | [ ]]

Подытожим:

• Список — это структура данных, которая либо пуста, либо состоит из двух частей: головы и хвоста. Хвост в свою очередь сам является списком.

• Список рассматривается в Прологе как специальный частный случай двоичного дерева. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде

[ Элемент1, Элемент2, ... ]

или

[ Голова | Хвост ]

или

[ Элемент1, Элемент2, ... | Остальные]

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

2.4. Создание списков

Из книги автора

2.4. Создание списков Простые списки можно создать с помощью обрывов страниц, но HTML предлагает для этого лучший инструмент.Списки – важный инструмент, они применяются для организации и группировки данных. Это может пригодиться при создании карты сайта (то есть его


Параметры списков

Из книги автора

Параметры списков Списки среди блочных элементов стоят особняком. В основном, из-за того, что, во-первых, содержат в себе другие блочные элементы (отдельные пункты), а во-вторых, включают маркеры и нумерацию, которые расставляет сам Web-обозреватель. Вот о маркерах и


Параметры списков

Из книги автора

Параметры списков Списки среди блочных элементов стоят особняком. В основном, из-за того, что, во-первых, содержат в себе другие блочные элементы (отдельные пункты), а во-вторых, включают маркеры и нумерацию, которые расставляет сам Web-обозреватель. Вот о маркерах и


Содержимое списков

Из книги автора

Содержимое списков Для формирования содержимого некоторых списков стандартных диалогов Windows используется ряд стандартных параметров (о ветвях, используемых для формирования списков стандартных диалогов, будет рассказано чуть позже). Эти параметры создаются в дочерних


1.13. Оформление списков

Из книги автора

1.13. Оформление списков При оформлении маркированного списка наиболее предпочтительно использовать символ. Знак маркировки должен находиться в начале абзаца. Расстояние от левого края печати до текста в списке должно составлять 0,63 см (что соответствует стандартным


7.5. Обработка списков

Из книги автора

7.5. Обработка списков В этом разделе мы рассмотрим некоторые основные предикаты, полезные при работе со списками. Поскольку Пролог позволяет работать с произвольными структурами данных, списки не могут играть в нем той незаменимой роли, какая им отводится в других языках


3. Представление графа списком списков. Алгоритм обхода графа в ширину

Из книги автора

3. Представление графа списком списков. Алгоритм обхода графа в ширину Граф можно определить с помощью списка списков следующим образом: Type List = ^Tlist; Tlist = record inf : Byte; next : List; end; Graph = ^TGpaph; TGpaph = record inf : Byte; smeg : List; next : Graph; end; При обходе графа в ширину мы выбираем произвольную


4.5. Создание списков

Из книги автора

4.5. Создание списков Очень часто бывает необходимо выделить какие-нибудь части текста визуально (например, при перечислении). Простое выделение абзаца не дает должного эффекта. В этом случае есть смысл воспользоваться маркерами или нумерацией. Маркеры объединяют пункты,


Пример 24-3. Комбинирование "ИЛИ-списков" и "И-списков"

Из книги автора

Пример 24-3. Комбинирование "ИЛИ-списков" и "И-списков" #!/bin/bash# delete.sh, утилита удаления файлов.# Порядок использования: delete имя_файлаE_BADARGS=65if [ -z "$1" ]then echo "Порядок использования: `basename $0` имя_файла" exit $E_BADARGS # Если не задано имя файла.else file=$1 # Запомнить имя файла.fi[ ! -f "$file" ]


6.2.2. Вывод списков

Из книги автора

6.2.2. Вывод списков Кроме стандартного прологовского формата для списков существуют несколько других естественных форм их внешнего представления, которые в некоторых ситуациях являются более предпочтительными. Следующая процедуравывспис( L)выводит список L так, что


9.1. Представление списков. Сортировка

Из книги автора

9.1. Представление списков. Сортировка 9.1.1. Замечания в некоторых альтернативных способах представления списков В главе 3 была введена специальная система обозначений для списков (специальная прологовская нотация), которую мы и использовали в последующем изложении.


9.1.2. Сортировка списков

Из книги автора

9.1.2. Сортировка списков Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядкабольше( X, Y)означающее, что X больше, чем Y,


1.13. Оформление списков

Из книги автора

1.13. Оформление списков При оформлении маркированного списка наиболее предпочтительно использовать символ «». Знак маркировки должен находиться в начале абзаца. Расстояние от левого края печати до текста в списке должно составлять 0,63 см (что соответствует стандартным


5.11. Оформление списков

Из книги автора

5.11. Оформление списков Word позволяет создавать нумерованные и маркированные списки. Нумерация в списках проставляется автоматически и меняется в зависимости от перемещения, добавления или удаления элементов списка.Для форматирования текста в виде списков с различными


14.6. Создание списков

Из книги автора

14.6. Создание списков Предположим, нам нужно создать небольшой список. Например, список сотрудников и их мобильных телефонов. Или же список доходов нашего магазина. В первом случае у нас будут три заголовка — Номер (сотрудника), Фамилия и Телефон. Во втором случае — Дата и