На этом шаге мы рассмотрим как найти звено в двунаправленном списке.

Поиск в двунаправленном списке может проводиться в двух направлениях:

1). Поиск в прямом направлении: от начала двунаправленного списка к его хвосту.

    Приведем функцию, в которой следующие параметры:
    pBegin - указатель на список (ссылка на заглавное звено);
    Key - искомый элемент;
    pCKey - ссылочная переменная, которой присваивается ссылка на первое по порядку звено, содержащее искомый элемент.

 Function Find_Forward (pBegin : PtrRec; Key : TypeElement; 
                      var pCKey: PtrRec): Boolean;
      var  pAux: PtrRec;
           Flag : Boolean;
   Begin
      Flag := False; pCKey := Nil;    {предположим, что не нашли...}
      pAux := pBegin^.pNext;          {исключим заглавное звено из рассмотрения}
      While  (pAux<>Nil) and (not Flag) do
         begin
            If  pAux^.Element = Key
               then
                     begin
                         Flag := True;
                         pCKey := pAux;
                     end;
            pAux := pAux^.pNext
         end;
      Find_Forward := Flag
   End;

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

2). Поиск в обратном направлении: от хвоста списка к заглавному звену.

    Приведем функцию на языке Рascal, параметры которой:
    pEnd- указатель на "хвост" списка (ссылка на последнее звено);
    Key - искомый элемент;
    pCKey - ссылочная переменная, которой присваивается ссылка на первое от хвоста звено, содержащее искомый элемент.

 Function Find_Back (pEnd : PtrRec; Key : TypeElement; var pCKey: PtrRec): Boolean;
      var  pAux : PtrRec; 
           Flag : Boolean; 
   Begin 
      Flag := False; pAux := pEnd; pCKey := Nil;
      While  (pAux<>Nil) and (not Flag) do 
         Begin 
            If  pAux^.Element = Key 
               then begin
                       Flag := True;
                       pCKey := pAux 
                    end; 
            pAux := pAux^.pPrev; 
         end; 
      Find_Back := Flag 
 End;

Рис.2. Результат поиска звена двунаправленного списка в обратном направлении

На следующем шаге мы рассмотрим включение звена в двунаправленный список.

Предыдущий шаг Содержание