Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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





Поделиться с друзьями:


Дата добавления: 2015-10-01; Мы поможем в написании ваших работ!; просмотров: 368 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Студент может не знать в двух случаях: не знал, или забыл. © Неизвестно
==> читать все изречения...

2806 - | 2369 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.