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

Явное использование стека

Читайте также:
  1. II. Использование различных типов фотоплёнок.
  2. IV. Использование светофильтров при съёмке и печати.
  3. VII. Порядок учета коммунальных услуг с использованием приборов учета, основания и порядок проведения проверок состояния приборов учета и правильности снятия их показаний
  4. А) да, их использование в последнее время относится к профилактической эндодонтии
  5. Бухгалтерский учет с использованием нормативных затрат. Различие учета по нормативной и по фактической себестоимости.
  6. Во-вторых, следить за тем, чтобы негативные эмоции в молитве не проистекали из жадности и себялюбия.
  7. Возможное использование

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

Рис. 13. Наглядное представление стека. Push (проталкивание) – традиционное название для операции добавления данных в стек, Pop (выталкивание) – традиционное название для операции извлечения данных из стека.

Когда одна процедура или функция вызывает другую, то параметры первой процедуры, а также место, с которого ее выполнение должно продолжиться после того как отработает вызванная процедура (точка возврата), запоминаются в так называемом стеке вызовов. Если вызванная процедура в свою очередь чего-нибудь вызывает, то ее параметры и точка возврата также добавляются в стек.

При рекурсивных вызовах стек вызовов хранит цепочку из данных об одновременно работающих процедурах. Во всех продвинутых средах разработки эту цепочку вместе с запомненными параметрами процедур можно просмотреть во время отладки. Соответствующая команда обычно называется “Call Stack” (в Delphi ей соответствует сочетание клавиш Ctrl – Alt – S).

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

Для начала реализуем в виде класса стек, хранящий параметры процедуры:

  type //Запись для хранения параметров процедур Parameters = record //Список параметров end;   //Стек удобно реализовать с помощью связанных списков //(http://www.tvd-home.ru/prog/16_4) PList = ^List; List = record Data: Parameters; Next: PList; end;   //Описанный одновсязанный список соединим с методами //добавления и удаления элементов и получим стек. Stack = class private StackTop: PList; public //Добавление данных procedure Push(NewData: Parameters); //Извлечение данных function Pop: Parameters; //Проверка наличия данных function Empty: boolean; end;   implementation   //Добавление данных procedure Stack.Push(NewData: Parameters); var NewElement: PList; begin New(NewElement); NewElement^.Data:= NewData; NewElement^.Next:= StackTop; StackTop:= NewElement; end;   //Извлечение данных function Stack.Pop: Parameters; var PopedElement: PList; begin PopedElement:= StackTop; StackTop:= StackTop^.Next; Pop:= PopedElement^.Data; Dispose(PopedElement); end;   //Проверка наличия данных function Stack.Empty: boolean; begin Empty:= StackTop = nil; end;

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

  procedure Recurs(P1: Parameters); begin DoSomething(P1); if <условие> then begin P2:= F(P1); Recurs(P2); P3:= G(P1); Recurs(P3); end; end;

В данной процедуре некоторые действия (DoSomething) выполняются много раз при разных значениях параметров. Нерекурсивный аналог должен хранить эти параметры в стеке. Каждый рекурсивный вызов будет соответствовать добавлению очередных параметров в стек. Вместо рекурсии появляется цикл, который выполняется, пока в стеке есть необработанные параметры.

  procedure NonRecurs(P1: Parameters); var S: Stack; P: Parameters; begin S:= Stack.Create; S.Push(P1); while not S.Empty do begin P1:= S.Pop; DoSomething(P1); if <условие> then begin P3:= G(P1); S.Push(P3); P2:= F(P1); S.Push(P2); end; end; end;

Обратите внимание, что рекурсивные вызовы шли сначала для параметров P2, потом для P3. В нерекурсивной процедуре в стек отправляются сначала параметры P3, а только потом P2. Это связано с тем, что при рекурсивных вызовах в стек, по сути, отправляется недовыполненная часть процедуры, которая в нашем случае содержит вызов Recurs(P3).[21]


Дата добавления: 2015-08-09; просмотров: 61 | Нарушение авторских прав


Читайте в этой же книге: Сложная рекурсия | Пример 2. | Рекуррентные соотношения. Рекурсия и итерация | Основные определения. Способы изображения деревьев | Прохождение деревьев | Представление дерева в памяти компьютера | Примеры рекурсивных алгоритмов | Ханойские башни | Синтаксический анализ арифметических выражений | Быстрые сортировки |
<== предыдущая страница | следующая страница ==>
Задачи на графах| Запоминание последовательности рекурсивных вызовов

mybiblioteka.su - 2015-2024 год. (0.006 сек.)