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

       

Вставка и извлечение элементов из списка


Определяем элемент, после которого необходимо вставить элемент в список. Вставка производится с помощью процедуры InsAfter(Q, X), а удаление - DelAfter(Q, X).

При этом рабочий указатель P будет указывать на элемент, после которого необходимо произвести вставку или удаление (рис 29).

Пример:

Пусть необходимо вставить новый элемент с информационным полем X после элемента, на который указывает рабочий указатель P.

Для этого:

          1) Необходимо сгенерировать новый элемент.

Q = GetNode

          2) Информационному полю этого элемента присвоить значение X.

Info(Q) = X

          3) Вставить полученный элемент.

    Ptr(Q) = Ptr(P)

    Ptr(P) = Q

Это и есть процедура InsAfter(Q, X).

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

Для этого:



1) Присваиваем Q значение указателя на удаляемый элемент.

Q = Ptr(P)

2) В переменную  X сохраняем значение информационного поля удаляемого элемента.

X = Info(Q)

3) Меняем значение указателя на удаляемый элемент на значение указателя на следующий элемент и производим удаление .

    Ptr(P) = Ptr(Q)

    FreeNode(Q)

Это и есть процедура DelAfter(P, X).

На языке Паскаль вышеописанные процедуры будут выглядеть следующим образом:

procedure InsAfter(var Q: PNode; X: Integer);

var

  Q: PNode;

begin

  New(Q);

  Q^.Info:=X; 

  Q^.Next:=P^.Next;

  P^.Next:=Q;

procedure DelAfter(var Q: PNode; var X: Integer);

var

  Q: PNode;

begin

  Q:=P^.Next;

  P^.Next:=Q^.Next;

  X:=Q^.Info;

  Dispose(Q);

end;



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