На этом шаге мы рассмотрим поиск компоненты однонаправленного списка с заглавным звеном по ключу.
Поиск компоненты с заданным ключом необходим для процедур чтения и вставки компоненты в список по ключу. Пусть требуется найти компоненту списка с ключом 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;
На следующем шаге мы рассмотрим, как вставить новый элемент в однаправленный список перед ключом.