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

Поиск компоненты с заданным ключом необходим для процедур чтения и вставки компоненты в список по ключу. Пусть требуется найти компоненту списка с ключом Key. Рассмотрим фрагмент процедуры:

 {Исключаем из просмотра заглавное звено}
 pCKey := pBegin^.pNext; 
 {пока не конец списка и в списке ключ Key не найден}
 While (pCKey <> Nil) and (pCKey^.Element <> Key) do
    pCKey := pCKey^.pNext; {будем осуществлять переход к следующему элементу списка}

Здесь Key - ключ, тип которого совпадает с типом данных компоненты.

После выполнения этих операторов указатель pСKey будет определять компоненту с заданным ключом или такая компонента не будет найдена (см. рис. 1.).

Рис.1. Поиск ключа Key в однонаправленном списке

Приведем функцию поиска:

 Function Find_Key1 (pBegin: PtrRec; Key: TypeElement; var pCKey: PtrRec) : Boolean;
   var pAux : PtrRec;
 Begin
   Find_Key1 := False; pCKey :=Nil;	{предположим, что не нашли}
   pAux := pBegin^.pNext;	       {исключаем из рассмотрения заглавное звено}
   While (pAux <> Nil) and (pAux^.Element <> Key) do
      pAux := pAux^.pNext;	       {сместили указатель}
   If pAux <> Nil
      Then	{Элемент найден}
       Begin 
            Find_Key1 := True;
            pСKey := pAux;
      End; 
 End;

Приведем еще одну итерационную функцию поиска на языке Pascal:

 Function Find (pBegin: PtrRec; Key: TypeElement; var pСKey: PtrRec) : Boolean;
    var pAux : PtrRec;
   Begin
      Find := False; pСKey := Nil;
      pAux := pBegin^.pNext; 
      While (pAux <> Nil) and (pСKey = Nil) do 
         Begin 
            If pAux^.Element = Key
               Then  Begin
                       Find := True;
                       pСKey := pAux; 
                     End; 
             pAux := pAux^.pNext;
         End; 
 End;

Отметим, что в качестве "побочного" эффекта функция возвращают ссылку на пеpвое вхождение заданного элемента в однонаправленный список.

Пpиведем pекуpсивную функцию, осуществляющую поиск элемента в однонаправленном списке:

 Function Find_Кеу (pList: PtrRec; Key: Integer; var pСKey: PtrRec) : Boolean; 
 {pList - указатель на список, в котором ведется поиск}
 {Key - заданный ключ , pСKey  - указатель на найденное звено}
    var b : Boolean;
 Begin 
   b := False; 
   If (not b) and (pList <> Nil) 
      Then  If  pList^.Element = Key
               Then b := True 
               Else b := Find_Key (pList^.pNext, Key, pСKey);
     Find_Key := b;
     pСKey := pList;
 End;

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

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