Удаление из стека максимального элемента.

В программе рассматриваются две ситуации, определяющие местоположение максимального элемента:

a) максимальный элемент - это первый элемент стека (рис.14);

б) максимальный элемент - это любой элемент стека, кроме первого (на рис.15 - это третий элемент).

Из рис.15 можно сделать вывод, что для удаления из стека заданного элемента необходимо знать адрес предшествующего элемента. Поэтому в отличие от предыдущего примера в программе дополнительно используется указатель Pred, определяющий адрес элемента, расположенного в стеке перед максимальным элементом. Если стек не пустой и Pmax=Pred, то максимальным элементом является первый элемент стека, в противном случае между ними существует следующее соотношение: Pmax = Pred^.Next.

Program DelMaxElem1;

TypePoinType = ^DynType;

DynType = record

Inf : integer;

Next : PoinType;

end;

Var Beg, { указатель входа в стек }

Run, { текущий указатель }

Pmax, { указатель макс.элемента }

Pred : PoinType; { указатель эл-та, предшествующего Pmax}

kmax : integer; { значение макс.элемента }

Begin

Формирование стека

Pmax:=Beg;

If Beg<>nil then

Begin

kmax:=Beg^.Inf;

Pred:=Beg; Run:=Beg;

WhileRun^.Next<>nil do

Begin

IfRun^.Next^.Inf>kmax then

Begin

kmax:=Run^.Next^.Inf;

Pred:=Run; Pmax:=Run^.Next;

End;

Run:=Run^.Next;

End;

IfPmax=Pred then

Beg:=Beg^.Next

Else

Pred^.Next:=Pmax^.Next;

Dispose(Pmax);

End;

Печать стека

End.

В программе DelMaxElem1 следует обратить внимание на следующую деталь.

Указателю предшествующего элемента стека назначено имя Pred, совпадающее с именем предописанной функции, которая определяет предыдущее значение ординальной переменной. Это допускается в Паскаль-программе, поскольку имя pred считается предописанным, а не зарезервированным. Однако если нам потребуется в программе записать kmax:=pred(kmax), то при компиляции будет выдано сообщение "Error 26: Type mismatch" (несоответствие типов). Тем не менее в этой программе функцию pred все же можно использовать, но это должно быть записано в виде kmax := System.pred(kmax), где System - имя стандартного модуля, содержащего функцию pred.

Указатели Pred и Pmax жестко связаны друг с другом, а именно Pmax = Pred^.Next. Поэтому в приведенной ниже программе DelMaxElem2 вместо двух указателей Pred и Pmax используется один указатель Pmax, но он адресует здесь элемент, предшествующий максимальному. Поскольку для первого элемента стека не существует предшествующего элемента, то Pmax = Beg как в случае, когда максимальным элементом стека является первый элемент, так и в случае, когда таким является второй элемент. В связи с этим в качестве признака удаления первого элемента в программе используется логическое выражение Pmax^.Inf=Beg^.Inf (если максимальный элемент равен первому элементу стека, то удалению подлежит первый элемент).

Program DelMaxElem2;

Type PoinType = ^DynType;

DynType = record

Inf : integer;

Next : PoinType;

end;

Var Beg, { указатель входа в стек }

Run, { текущий указатель }

Pmax : PoinType; { указатель предшествующего элемента }

kmax : integer; { значение макс.элемента }

Begin

Формирование стека

If Beg<>nil then

Begin

kmax:=Beg^.Inf;

Pmax:=Beg; Run:=Beg;

While Run^.Next<>nil do

Begin

IfRun^.Next^.Inf>kmax then

Begin

kmax:=Run^.Next^.Inf;

Pmax:=Run;

End;

Run:=Run^.Next;

End;

If kmax=Beg^.Inf then

Begin

Run:=Beg; Beg:=Beg^.Next

End

Else

Begin

Run:=Pmax^.Next; Pmax^.Next:=Pmax^.Next^.Next;

End;

Dispose(Run);

End;

Печать стека

End.