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

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

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

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

{ Перебор 1-связного списка }

Procedure LookSll(head : sllptr);

{ head - указатель на начало списка }

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;

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

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

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

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

{==== Программный пример 5.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;

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

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

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

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

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

{==== Программный пример 5.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 { если есть предыдущий эл-т - вставка в

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

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

end

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

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

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

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

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

end; end;