Var cur : sllptr; { адрес текущего элемента }

begin

cur:=head; { 1-й элемент списка назначается текущим }

while cur <> nil do begin < обработка c^.inf >

обрабатывается информационная часть того эл-та, на который указывает cur. Обработка может состоять в:

печати содержимого инф.части;

модификации полей инф.части;

сравнения полей инф.части с образцом при поиске по ключу;

подсчете итераций цикла при поиске по номеру;

и т.д., и т.п.

cur:=cur^.next;

из текущего эл-та выбирается указатель на следующий эл-т и для следующей итерации следующий эл-т становится текущим; если текущий эл-т был последний, то его поле next содержит пустой указатель и, т.обр. в cur запишется nil, что приведет к выходу из цикла при проверке условия while

end; end;

{ конец примера }

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

cur:=cur^.prev;

Алгоритм перебора для двусвязного списка мы оставляем читателю на самостоятельную разработку.

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

Вставка элемента в середину односвязного списка показана на рис.1 и в примере 2.

Рис. 1: Вставка элемента в середину 1-связного списка

{==== Программный пример 2 ====}

{ Вставка элемента в середину 1-связного списка }

Procedure InsertSll(prev : sllptr; inf : data);

{ prev - адрес предыдущего эл-та; inf - данные нового эл-та }

Var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

cur^.next:=prev^.next; { эл-т, следовавший за предыдущим теперь

будет следовать за новым }

prev^.next:=cur; { новый эл-т следует за предыдущим }

end;

Рисунок 2 представляет вставку в двухсвязный список.

Рис. 2: Вставка элемента в середину 2-связного списка

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

Рис. 3: Вставка элемента в начало 1-связного списка

Программный пример 3 представляет процедуру, выполняющую вставку элемента в любое место односвязного списка.

{==== Программный пример 3 ====}

{ Вставка элемента в любое место 1-связного списка }

Procedure InsertSll

var head : sllptr; { указатель на начало списка, может измениться в

процедуре, если head=nil - список пустой }

prev : sllptr; { указатель на эл-т, после к-рого делается вставка,

если prev-nil - вставка перед 1-ым эл-том }

inf : data { - данные нового эл-та }

var cur : sllptr; { адрес нового эл-та }

begin

{ выделение памяти для нового эл-та и запись в его инф.часть }

New(cur); cur^.inf:=inf;

if prev <> nil then begin { если есть предыдущий эл-т - вставка в

середину списка, см. прим. 2 }

cur^.next:=prev^.next; prev^.next:=cur;

end

else begin { вставка в начало списка }

cur^.next:=head; { новый эл-т указывает на бывший 1-й эл-т списка;

если head=nil, то новый эл-т будет и последним эл-том списка }

head:=cur; { новый эл-т становится 1-ым в списке, указатель на

начало теперь указывает на него }

end; end;

Удаление элемента из списка

Удаление элемента из односвязного списка показано на рис. 4.

Рис. 4: Удаление элемента из 1-связного списка

Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис.4.а). Мы, однако, на рис. 4 и в примере 1 приводим процедуру для случая, когда удаляемый элемент задается своим адресом (del на рис.4). Процедура обеспечивает удаления как из середины, так и из начала списка.

{==== Программный пример 1 ====}

{ Удаление элемента из любого места 1-связного списка }

Procedure DeleteSll(

var head : sllptr; { указатель на начало списка, может

измениться в процедуре }

del : sllptr { указатель на эл-т, к-рый удаляется } );

var prev : sllptr; { адрес предыдущего эл-та }

begin

if head=nil then begin { попытка удаления из пустого списка

асценивается как ошибка (в последующих примерах этот случай

учитываться на будет) }

Writeln('Ошибка!'); Halt;

end;

if del=head then { если удаляемый эл-т - 1-й в списке, то

следующий за ним становится первым }

head:=del^.next

else begin { удаление из середины списка }

{ приходится искать эл-т, предшествующий удаляемому;

поиск производится перебором списка с самого его начала,

пока не будет найдет эл-т, поле next к-рого совпадает

с адресом удаляемого элемента. }

prev:=head^.next;

while (prev^.next<>del) and (prev^.next<>nil) do

prev:=prev^.next;

if prev^.next=nil then begin

{ это случай, когда перебран весь список, но эл-т не найден,

он отсутствует в списке; расценивается как ошибка

(в последующих примерах этот случай учитываться на будет)

Writeln('Ошибка!'); Halt;

end;

prev^.next:=del^.next;

{ предыдущий эл-т теперь указывает

на следующий за удаляемым }

end;

{ элемент исключен из списка, теперь можно освободить

занимаемую им память }

Dispose(del);

end;

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

Рис. 5: Удаление элемента из 2-связного списка

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

Перестановка элементов списка.

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

Рис. 6: Перестановка соседних элементов 1-связного списка

{==== Программный пример 2 ====}

{ Перестановка двух соседних элементов в 1-связном списке }

Procedure ExchangeSll(

prev : sllptr { указатель на эл-т, предшествующий

переставляемой паре } );