Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Domains. element = i(integer); c(char); s(string)
|
|
element = i(integer); c(char); s(string)
listE = element*
Такое описание списка позволит иметь дело со списками вида:
[ i(–15), s(" Мама"), c('A'), s(" мыла"), c('+'), s(" раму"), i(48), c('! ') ]
Рекурсивное определение списка: список — это структура данных, определяемая следующим образом:
- пустой список ([ ]) является списком;
- структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.
Принято называть Hголовой списка, а T — хвостом списка. Фактически операция " | " позволяет разделить список на хвост и голову или, наоборот, присоединить объект (объекты) к началу списка.
Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост. Хвост, в свою очередь, также является списком, содержащим меньшее количество элементов, чем исходный список. Например, в списке [1, 2, 3] элемент 1 является головой, а список [2, 3] — хвостом, т.е. [1, 2, 3] = [ 1 | [2, 3] ].
В этом же списке можно выделить два первых элемента и хвост из третьего элемента [1, 2 | [3] ]. И, наконец, возможен вариант разбиения на голову из трех первых элементов и пустой хвост : [1, 2, 3 | [] ].
Чтобы организовать рекурсивную обработку списка, достаточно задать предложение, которое будет являться правилом остановки рекурсивной процедуры, а также рекурсивное правило, устанавливающее порядок обработки всего непустого списка.
Пример. Создать предикат, позволяющий вычислить длину списка, т.е. количество элементов в списке.
Для решения этой задачи воспользуемся фактом, что в пустом списке элементов нет, а количество элементов непустого списка, представленного в виде объединения первого элемента и хвоста, равно количеству элементов хвоста, увеличенному на единицу.
length([ ], 0). /* в пустом списке элементов нет */
length([_|T], L): – length(T, L_T), L = L_T + 1.
/* L_T — кол-во элементов в хвосте */
/* L — кол-во элементов исх. списка */
Соответствующий запрос может быть таким:
Goal: length([1, 2, 3], X).
Ввод и вывод списка
Ввод списка осуществляется с помощью предиката readterm(< тип списка>, Х). Для выводасписка используется оператор write(Х), при этом список Х рассматривается как один терм.
Пример 1. Организовать ввод списка из целых чисел.
Domains
list=integer*
Goal
write(" Введите список "), readterm(list, X), nl,
write(" список L = "), write(X), nl.
Пример 2. Организовать поэлементный ввод списка.
Domains
list=integer*
Predicates
Readlist(list)
Goal
write(" Введите список "), readlist(L), nl,
write(" список L = ", L).