Динамические структуры данных: стеки, очереди, деки, страница 2

Сохранение формальных параметров, локальных переменных, адреса возврата.

Вход

                                                                                                             ПРОЛОГ

 

Выход по адресу возврата

Восстановление последних сохраненных параметров, локальных переменных, адреса возврата

Обращение процедуры к самой себе

Промежуточные вычисления

Окончательные вычисления

Проверка

                                                                                                                                    ТЕЛО

ЭПИЛОГ

Рисунок 6.2

Рассмотрим рекурсивную функцию для вычисления факториала

int fact(int n).

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

if (n==0).

Блок промежуточных вычислений в нашем случае объединяется с блоком обращения к процедуре:

return(n*fact(n-1)).

Блок окончательных вычислений

return(1);

С каждым обращением к рекурсивной процедуре ассоциируется номер уровня.

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

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

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

ОЧЕРЕДИ.

Линейный список, в котором допускается включение элемента только с одного конца, а исключение – только с другого, называется очередью. Информация в таком списке обрабатывается по принципу FIFO (первым пришел, первым вышел). Пример очереди - организация данных о выполняемых задачах в системах с разделением времени. Также, как и для стека, очередь может использовать в качестве структуры хранения массивы и связанные списки. Ниже на рис.6.3 приведены три примера структуры хранения очереди на базе одномерного массива.

Вариант 1

+---------------------------------------------+

¦ r  ¦ e1 ¦ e2  ¦ e3 ¦...¦er ¦    ¦   ¦   ¦    ¦    ¦     ¦

¦     ¦     ¦       ¦     ¦    ¦    ¦    ¦   ¦   ¦    ¦    ¦     ¦

+---------------------------------------------+

Вариант 2.

f                       r

+-----------------------------------------------+

¦ f  ¦  r ¦       e1 ¦e2 ¦e3 ¦... ¦   ¦en ¦    ¦    ¦     ¦

¦    ¦     ¦            ¦    ¦     ¦    ¦   ¦     ¦    ¦    ¦     ¦

+-----------------------------------------------+

Вариант 3.

r          f

+---------------------------------------------------------------+

      ¦Д   ¦И   ¦...  Э ¦Л ¦Е ¦М  Е  Н ¦Т  Ы ¦_ ¦О ¦Ч   ¦Е  ¦Р   ¦Е ¦

      ¦     ¦      ¦         ¦    ¦   ¦    ¦    ¦    ¦   ¦      ¦  ¦    ¦      ¦    ¦     ¦    ¦

+---------------------------------------------------------------+

 

+-----------+

¦  f    ¦  r     ¦

¦       ¦         ¦

+-----------+

В варианте 1 очередь начинается со второго элемента массива, r - характеризует общее число элементов очереди.  Он не эффективен с точки зрения выполнения операции извлечения элемента из очереди. Вариант 2 более эффективен с этой точки зрения, а вариант 3 развивает

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

ДЕКИ.

Дек – структура памяти в форме списка, которая позволяет добавлять элементы как в конец, так и в начало последовательности. То есть дек обладает одновременно свойствами стека и очереди. Возможны варианты деков с ограничениями:

- дек с ограниченным входом допускает включение элементов только с одного конца;

- дек с ограниченным выходом допускает извлечение элементов только с одного конца.