Модели и структуры данных



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



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

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

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

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









Содержание    Назад    Вперед