КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Domains
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).
Дата добавления: 2015-02-09; просмотров: 150; Мы поможем в написании вашей работы!; Нарушение авторских прав |