IPB

> Лекция №9.1: Рекурсивные подпрограммы
Чат
Форум
Загрузка...
 

страницы: 1 2 3 4

Динамические структуры данных: стек, очередь, дек. Рекурсивные процедуры и функции. Сравнение рекурсивных и нерекурсивных алгоритмов. Быстрая сортировка массива.

Содержание

Динамические структуры данных

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

Стек

Стеком называется динамическая структура данных, у которой в каждый момент времени доступен только верхний (последний) элемент. Лучше всего понятие стека можно проиллюстрировать примером стопки книг: в стопку можно добавить ещё одну книжку, положив её сверху; из стопки можно взять, не разрушив её, только верхнюю книгу. А для того, чтобы достать книжку из середины стопки, необходимо сначала убрать по одной все лежащие выше неё.

Последовательность обработки элементов стека хорошо отражают аббревиатуры LIFO (Last In First Out — «последним вошёл, первым вышел») и FILO (First In Last Out — «первым вошёл, последним вышел»).

Реализовать стек можно любым удобным для программиста способом: например, массивом. Тогда началом стека (его «верхним» элементом) будет последний компонент массива, а освобождение стека будет происходить в направлении от конца массива к его началу. При такой реализации нет необходимости в постоянном перемещении компонент массива.

Впрочем, наиболее эффективной всё равно будет реализация при помощи односвязного линейного списка, о котором пойдёт речь в следующей лекции.

Операции

Для стека должны быть определены следующие операции:

empty(<нач_стека>) : Boolean— проверка стека на пустоту;
add(<нач_стека>, <новый_элемент>) : <нач_стека>— добавление элемента в стек;
take(<нач_стека>) : <тип_элементов_стека>— считывание значения верхнего элемента;
del(<нач_стека>) : <нач_стека>.— удаление верхнего элемента из стека.

Очередь

Очередью называется динамическая структура, у которой в каждый момент времени доступны два элемента: первый и последний. Из начала очереди элементы можно удалять, а к концу — добавлять. Примером очереди программистcкой вполне может служить очередь обывательская: скажем, в продуктовом магазине.

Последовательность обработки элементов очереди хорошо отражают аббревиатуры LILO (Last In Last Out — «последним вошёл, последним вышел») и FIFO (First In First Out — «первым вошёл, первым вышел»).

Реализовать очередь также можно при помощи массива, хотя здесь уже не удастся полностью избежать перемещения его компонент. Пусть k–я компонента массива хранит начало очереди, а (k+s)–я — её конец. Тогда можно приписать новый элемент очереди в (k+s+1)–ю компоненту массива, а при удалении элемента из начала очереди её голова сдвинется в (k+1)–ю компоненту. В процессе работы может оказаться, что вся очередь «сдвинулась» к концу массива, и её снова нужно вернуть к началу. В этом случае и потребуется s перемещений компонент массива (s — это текущая длина очереди).

Однако наиболее эффективной снова будет реализация при помощи односвязного линейного списка (см. лекцию 10).

Операции

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

empty(<нач_очереди>) : Boolean— проверка очереди на пустоту;
add(<кон_очереди>, <нов_эл-т>) : <кон_очереди>— добавление элемента в конец очереди;
take_beg(<нач_очереди>) : <тип_эл-тов_очереди>— считывание значения первого элемента;
take_end(<кон_очереди>) : <тип_эл-тов_очереди>— считывание значения последнего элемента;
del(<нач_очереди>) : <нач_очереди>— удаление элемента из начала очереди.

Дек

Дональд Кнут1 ввёл понятие усложнённой очереди, которая называется дек (deque — Double-Ended QUEue — двухконцевая очередь). В каждый момент времени у дека доступны как первый, так и последний элемент, причём добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек — это симметричная двусторонняя очередь.

Реализация дека при помощи массива ничем не отличается от реализации обычной очереди, а вот в терминах списков дек удобнее представлять двусвязным (разнонаправленным) линейным списком (см. лекцию 10).

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

Рекурсия

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

Например, рекурсивно определяется функция факториал:

0! = 1
n! = n * (n - 1)!, для любого натурального n.

Другим примером рекурсивного определения может послужить определение арифметического выражения, приведённое в лекции 2.

Рекурсивные подпрограммы

В программировании рекурсивной называется подпрограмма, исполнение которой приводит к её же повторному вызову.

Если подпрограмма просто вызывает сама себя, то такая рекурсия называется прямой. Например:

procedure rec1(k : Byte);
begin
 {...}
  rec1(k - 1);
 {...}
end;

function rec2(k : Byte) : Byte;
begin
 {...}
  x := rec2(k - 1);
 {...}
end;

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

В случае косвенной рекурсии возникает проблема с описанием подпрограмм: по правилу языка Pascal, нельзя использовать никакой объект раньше, чем он был описан. Следовательно, невозможно написать в программе:

procedure rec_A(k : Byte);
begin
 {...}
  rec_B(k - 1);
 {...}
end;

procedure rec_B(k : Byte);
begin
 {...}
  rec_A(k - 1);
 {...}
end;

И здесь полезной оказывается возможность отрывать объявление подпрограммы от её описания (см. лекцию 8). Например, для косвенной рекурсии в случае двух процедур, вызывающих друг друга (rec_A → rec_B → rec_A), нужно такое описание:

procedure rec_A(k : Byte); forward;

procedure rec_B(k : Byte);
begin
 ...
  rec_A(k - 1);
 ...
end;

{ список аргументов уже описанной подпрограммы можно
  не повторять, но это усложняет восприятие программного текста }

procedure rec_A(k : Byte);
begin
 {...}
  rec_B(k - 1);
 {...}
end;

страницы: 1 2 3 4

Примечания

  1. ^ См. Д. Кнут. Искусство программирования для ЭВМ, любое издание. Т.1 Основные алгоритмы.
 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"