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

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

Алгоритм перебора для односвязного списка представляется программным примером 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;

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