Помощничек
Главная | Обратная связь


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

Принцип доступа к очереди – «первым пришел - первым ушел» (first in - first out, FIFO)



 

Принцип обработки, как для стека, так и для очереди определяет набор соответствующих процедур.

 

Для реализации очереди необходим список, для которого известны адрес первого и адрес последнего элементов.

 

Над очередью выполняются следующие операции:

 

1) добавление в конец очереди нового элемента;

2) определение пуста ли очередь;

3) доступ к первому элементу очереди;

4) исключение из очереди первого элемента.

Эти операции могут быть взяты из стандартного набора действий со списком.

 

Кроме рассмотренных очереди и стека есть ещё и третий вариант структуры данных - дек, очередь с двойным доступом, или, как ещё его называют, - двухконечный стек. Для дека добавление элементов, доступ к «вершине» и удаление элемента возможны с обоих концов списка.

 

Использование рекурсии при работе со списками.

 

Рекурсия является одним из удобнейших средств при работе с линейными списками. Она позволяет сократить код программы и сделать алгоритмы обхода узлов деревьев и списков более понятными.

По определению понятия, рекурсивная процедура - это процедура, в теле которой есть обращение к самой себе. Для того, чтобы процесс рекурсии не стал бесконечным и не вызвал переполнение стека, в каждой рекурсивной процедуре должен быть определен ограничитель рекурсии, блокирующий дальнейшее «размножение» тела процедуры.

Хотя рекурсии в списках не являются настолько очевидным решением, как в деревьях, все же они позволяют оптимизировать обработку линейных списков. В списках возможны два варианта прохода: из начала в конец и из конца в начало. Эти методы реализуются очень легко в случае с двунаправленными списками.

 

Рекурсию в линейных списках демонстрирует следующий пример: подсчет числа элементов в линейном однонаправленном списке.

Procedure Count_El ( q : El; var count : integer);

Begin

if q < > nil { ограничитель рекурсии }

Then begin

inc (count);

Count_El( q^.next , count);

End

End;

Графическая иллюстрация рекурсии для обработки списка

При входе в процедуру count = 0q=first (указатель на первый элемент списка).

Далее рекурсивная процедура работает так.

Анализируется значение указателя, переданного в процедуру. Если он не равен Nil (список не закончился), то счетчик числа элементов увеличивается на 1.

Далее происходит очередной вызов рекурсивной процедуры уже с адресом следующего элемента списка, а «текущая» рекурсивная процедура приостанавливается до окончания вызванной процедуры.

Вызванная процедура работает точно так же: считает, вызывает процедуру и переходит в состояние ожидания.

Формируется как бы последовательность из процедур, каждая из которых ожидает завершения вызванной процедуры.

Этот процесс продолжается до тех пор, пока очередное значение адреса не станет равным Nil (признак окончания списка).

В последней вызванной рекурсивной процедуре уже не происходит очередного вызова, так как не соблюдается условие q<>nil, срабатывает «ограничитель рекурсии». В результате процедура завершается без выполнения каких-либо действий, а управление возвращается в «предпоследнюю», вызывающую процедуру. Точкой возврата будет оператор, стоящий за вызовом процедуры, в данном тексте - End, и «предпоследняя» процедура завершает свою работу, возвращая управление в вызвавшую её процедуру.

Начинается процесс «сворачивания» цепочки ожидающих завершения процедур. Счетчик count, вызывавшийся по ссылке, сохраняет накопленное значение после завершения всей цепочки вызванных рекурсивных процедур.

Если из текста рассмотренной процедуры убрать использование счетчика, то получится некий базисный вариант рекурсивной процедуры, который можно применять при решении других задач обработки списка: распечатать содержимое списка; определить, есть ли в списке элемент с заданным порядковым номером или определенным значением информационного поля; уничтожить список с освобождением памяти и др.

 

Мультисписки

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.