Структуры и алгоритмы обработки данных

Примеры типичных операций над списками


Задача 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;



Содержание раздела