Примеры типичных операций над списками
Задача 1.
Требуется просмотреть список и удалить элементы, у которых информационные поля равны 4.
Обозначим P - рабочий указатель, в начале процедуры P = Lst. Введем также указатель Q, который отстает на один элемент от P. Когда указатель P найдет элемент, последний будет удален относительно указателя Q как последующий элемент.
Q = Nil
P = Lst
While P <> Nil do
If Info(P) = 4 then
If Q = Nil then
Pop(Lst)
FreeNode(P)
P = Lst
Else
DelAfter(Q, X)
EndIf
Else
Q = P
P = Ptr(P)
EndIf
EndWhile
Задача 2.
Дан упорядоченный по возрастанию Info - полей список. Необходимо вставить в этот список элемент со значением X, не нарушив упорядоченности списка.
Пусть X = 16. Начальное условие: Q = Nil, P = Lst. Вставка элемента должна произойти между 3 и 4 элементом (рис.3.10).
Q =Nil
P = Lst
While (P <> Nil) and (X > Info(P)) do
Q = P
P = Ptr(P)
EndWhile
if Q = Nil then
Push(Lst, X)
EndIf
InsAfter(Q, X)
Реализация примеров на языке Паскаль:
Задача 1:
Q:=nil;
P:=Lst;
While P <> nil do
If P^.Info = 4 then
begin
If Q = nil then
begin
Pop(Lst);
P:=Lst;
end
Else Delafter(Q,X);
End;
Else
begin
Q:=P;
P:=P^.Next;
end;
end;
Задача 2:
Q:=nil;
P:=Lst;
While (P <> nil) and (X > P^.Info) do
begin
Q:=P;
P:=P^.Next;
end;
{В эту точку производится вставка}
If Q = nil then Push(Lst, X);
InsAfter(Q, X);
End;
