Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Явное использование стека
|
|
Стеком называется структура данных, в которой добавление и извлечение данных происходит с одного конца, называемого вершиной стека (рис. 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).
Упомянутой выше перестановки можно избежать, если вместо стека использовать очередь – структуру данных, где добавление и извлечение элементов происходит с разных концов. Это будет некоторым отступлением от точной имитации процессов при рекурсивных вызовах. Однако в данном примере это кажется более удобным: каждый рекурсивный вызов будет прямо заменяться добавлением параметров в очередь.
Date: 2016-07-18; view: 362; Нарушение авторских прав