Модели и структуры данных



         

Стеки в вычислительных системах - часть 2


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

Этот прием делает возможной легкую реализацию рекурсивных процедур. Когда процедура вызывает сама себя, то для всех ее локальных переменных выделяется новая память в стеке, и вложенный вызов работает с собственным представлением локальных переменных. Когда вложенный вызов завершается, занимаемая его переменными область памяти в стеке освобождается и актуальным становится представление локальных переменных предыдущего уровня. За счет этого в языках PASCAL и C любые процедуры/функции могут вызывать сами себя. В языке PL/1, где по умолчанию приняты другие способы размещения локальных переменных, рекурсивная процедура должна быть определена с описателем RECURSIVE - только тогда ее локальные переменные будут размещаться в стеке.

Рекурсия использует стек в скрытом от программиста виде, но все рекурсивные процедуры могут быть реализованы и без рекурсии, но с явным использованием стека. В программном примере 3.17 приведена реализация быстрой сортировки Хоара в рекурсивной процедуре. Программный пример 4.2 показывает, как будет выглядеть другая реализация того же алгоритма.

{==== Программный пример 4.2 ====} { Быстрая сортировка Хоара (стек) } Procedure Sort(a : Seq); { см. раздел 3.8 } type board=record { границы обрабатываемого участка } i0, j0 : integer; end; Var i0, j0, i, j, x : integer; flag_j : boolean; stack : array[1..N] of board; { стек } stp : integer; { указатель стека работает на увеличение } begin { в стек заносятся общие границы } stp:=1; stack[i].i0:=1; stack[i].j0:=N; while stp>0 do { выбрать границы из стека } begin i0:=stack[stp].i0; j0:=stack[stp].j0; stp:=stp-1; i:=i0; j:=j0; flag_j:=false;{проход перестановок от i0 до j0} while ia[j] then { перестановка } begin x:=a[i]; a[i]:=a[j]; a[j]:=x; flag_j:= not flag_j; end; if flag_j then Dec(j) else Inc(i); end; if i-1>i0 then {занесение в стек границ левого участка} begin stp:=stp+1; stack[stp].i0:=i0; stack[stp].j0:=i-1; end; if j0>i+1 then {занесение в стек границ правого участка} begin stp:=stp+1; stack[stp].i0:=i+1; stack[stp].j0:=j0; end; end;

Один проход сортировки Хоара разбивает исходное множество на два множества. Границы полученных множеств запоминаются в стеке. Затем из стека выбираются границы, находящиеся в вершине, и обрабатывается множество, определяемое этими границами. В процессе его обработки в стек может быть записана новая пара границ и т.д. При начальных установках в стек заносятся границы исходного множества. Сортировка заканчивается с опустошением стека.




Содержание  Назад  Вперед