На этом шаге мы рассмотрим первый способ поиска звена.
Поиск звена в двунаправленном списке можно производить в двух направлениях: с начала и с конца списка. Рассмотрим алгоритм поиска с начала списка.
Обозначим через Элем информационное поле звена, которое необходимо найти в списке. Вначале опишем алгоритм:
Res = NULL; //Указатель на искомое звено содержит NULL. q = (*nsp).sled; //Рабочий указатель установим на звено, //следующее за заглавным. while (q!=NULL && Res=NULL) { if ((*q).elem==Элем) // Если звено, содержащее элемент Элем, найдено, то //запоминаем указатель на найденное звено. Res = q; else // ... иначе: перемещаем рабочий указатель по списку. q = (*q).sled; }
Оформим приведенный выше алгоритм в виде функции:
node *PoiskForward (int el,node**nsp,node**ksp) // Функция возвращает указатель на найденное звено, // содержащее элемент el двунаправленного списка, // заданного указателями *nsp и *ksp, или NULL, если // звено в списке не найдено. { node *q; // Текущий указатель. node *Res; *Res = NULL; q = (**nsp).sled; while (q!=NULL && *Res=NULL) { if ((*q).elem==el) *Res = q; else q = (*q).sled;} return Res; }
На следующем шаге мы рассмотрим поиск звена, начиная с конца списка.
