Списки. Включение элемента в начало списка. Алгоритм добавления и исключения

Списки

Рассмотрим структуры данных, которые можно создавать с помощью указателей. Начнем со связных списков. Связный список представляет собой цепочку записей-узлов, в которой каждая запись содержит основные данные и ссылку на следующую запись и цепочке. Во главе списка находится указатель («корень»), который указывает на первую запись в списке (рисунок - 1).

Указателю в последней закиси списка обычно присваивается значение nil, служащее признаком конца списка.

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

Пусть есть два типа: Node и Ptr, определенные следующим образом:

Type

Ptr = ^Node;

Node = record

                    Key:integer;

                    Next:Ptr;

                    …

                    end;

var     p,q: Ptr;

Каждая переменная типа Node состоит из трех компонент, а именно поля данных (key), ссылки на следующий элемент (next) и, возможно, какой-либо другой информации.

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

Сначала список должен быть пуст:

p:=nil;

Сначала элемент типа Node размещается в памяти процедурой new(q), и ссылка на него присваивается некоторой вспомогательной переменной q. После этого ссылкам присваиваются новые значения, и операция на этом заканчивается.

New(q);

q^.key:=данные;

q^.next:=p;

P:=q;

Целиком процесс формирования списка из k элементов представлен фрагментом:

p:=Nil;

While k>0 do begin

new(q);

q^.next:=p;

q^.key:=данные;

p:=q;

k:=k-1;

Таким образом порядок элементов в списке обратен порядку их включения.

Алгоритм добавления и исключения

Рассмотрим проблему добавления и исключения компонент, находящихся в середине списка.

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

q^.next:=p^.next;

p^.next:=q;

Несколько труднее реализовать процедуру вставки перед, которая используется в тех случаях, когда в нашем распоряжении оказывается ссылка на компоненту списка, перед которой надо вставить новую компоненту. Однонаправленная цепочка связей должна затруднить работу, поскольку нет «хода» к элементам, предшествующим данному.

Кроме того, нужно проверять случай, когда q является первой компонентой списка.

Процедуру вставки элемента со ссылкой q перед элементом со ссылкой w можно описать следующим образом:

if w=p then begin

q^.next:=w;

p:=q;

end

else begin

z:=p

while z^.next<>w do z:=z^.next;

z^.next:=q;

q^.next:=w;

end;

Имеется еще один способ реализации процедуры вставки перед. Он заключается в том, что новая компонента q на самом деле включается после w, но затем новая компонента q и w «меняются» значениями полей данных.

q^.next:=w^.next;

w^.next:=q;

x:=w^.key;

w^.key:=q^.key;

q^.key:=x;

Исключение из списка

Теперь рассмотрим процесс исключения из списка. Исключение элемента, следующего за w, очевидно.

w^.next:=w^.next^.next;

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