Добавление элемента в упорядоченный стек.

Будем считать, что элементы стека расположены по возрастанию их численных значений.

Возможны два варианта включения нового элемента:

a) включение в начало стека (рис.16);

б) включение в произвольное место стека (рис.17).

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

Как следует из анализа рис.17, для изменения связей в стеке при добавлении элемента требуется знать адрес предыдущего элемента.

ProgramInsElem1;

Label 10;

Type PoinType = ^DynType;

DynType = record

Inf : integer;

Next : PoinType;

end;

Var Beg,Run,

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

{ включаемому новому элементу }

NewEl : PoinType; { указатель нового элемента }

k : integer;

Begin

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

Read(k); New(NewEl); NewEl^.Inf:=k;

If (Beg=nil) or (k<=Beg^.Inf) then

Begin

NewEl^.Next:=Beg; { включение нового эл-та }

Beg:=NewEl; { в начало стека }

End

Else

Begin

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

While Run<>nil do

If Run^.Inf > k then

Begin

NewEl^.Next:=Run; { включение нового эл-та }

Pred^.Next:=NewEl; { в середину стека }

Goto 10

End

Else

Begin

Pred:=Run; { перебор элементов }

Run:=Run^.Next { стека }

End;

Pred^.Next:=NewEl; { включение нового эл-та }

NewEl^.Next:=nil; { в конец стека }

End;

10:

Печать стека

End.

Если при просмотре стека не обнаружен элемент, превышающий значение k, то это означает, что значение k должно быть записано после последнего элемента стека.

Как и в предыдущем примере, программу InsElem1 можно реализовать без указателя Pred, возложив его функции на указатель Run.

ProgramInsElem2;

Type PoinType = ^DynType;

DynType = record

Inf : integer;

Next : PoinType;

end;

Var Beg,Run,

NewEl : PoinType; { указатель нового элемента }

k : integer;

Cond : boolean;

Begin

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

Read(k);

New(NewEl); NewEl^.Inf:=k;

If (Beg=nil) or (k<=Beg^.Inf) then

Begin

NewEl^.Next:=Beg; { включение нового эл-та }

Beg:=NewEl; { в начало стека }

End

Else

Begin

Run:=Beg; Cond:=true;

While (Run^.Next<>nil) andConddo

If Run^.Next^.Inf > k then

Begin

NewEl^.Next:=Run^.Next; { включение нового эл-та }

Run^.Next:=NewEl; { в середину стека }

Cond:=false

End

Else

Run:=Run^.Next;

IfCond then

Begin

Run^.Next:=NewEl; { включение нового эл-та }

NewEl^.Next:=nil; { в конец стека }

End;

End;

Печать стека

End.

Здесь следует обратить также внимание, что за счет небольшой модификации программы в InsElem2 исключен оператор Goto.