Поиск звена в двунаправленном списке

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

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

   
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. Результат поиска звена двунаправленного списка в обратном направлении

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



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий