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



         

Реализация операций над связными линейными списками - часть 2


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




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