LSEARCH(3C) LSEARCH(3C)
НАЗВАНИЕ
lsearch, lfind - последовательный поиск и обновление
СИНТАКСИС
#include
#include
char *lsearch((char *)key,(char *)base,nelp,sizeof(*key),compar)
unsigned *nelp;
int (*compar) ( );
char *lfind((char *)key,(char *)base,nelp,sizeof(*key),compar)
unsigned *nelp;
int (*compar) ( );
ОПИСАНИЕ
Функция lsearch предназначена для выполнения последова-
тельного поиска в соответствии с алгоритмом, описанным
в книге Д. Кнута: Искусство программирования для ЭВМ.
Т. 3. Сортировка, поиск. - М.: Мир, 1978. Раздел 6.1,
алгоритм S.
Функция lsearch возвращает указатель внутрь таблицы на
искомые данные. Если данные не найдены, они добавляются
в конец таблицы. Аргумент key указывает на объект дан-
ных, разыскиваемый в таблице (ключ поиска). Base указы-
вает на первый элемент таблицы. Nelp - указатель на це-
лое, содержащее текущее количество элементов в таблице.
Это целое значение увеличивается на единицу, если в
таблицу добавляются данные. Compar - функция сравнения,
предоставляемая пользователем (например, функция
strcmp). Функция сравнения вызывается с двумя аргумен-
тами - указателями на сравниваемые элементы. Она должна
возвращать нулевое значение, если элементы равны, и
значение, не равное нулю, в противном случае.
Функция lfind выполняет то же самое, что и функция
lsearch, но не добавляет данные в таблицу при неудачном
поиске, возвращая в этом случае пустой указатель NULL.
ПРИМЕЧАНИЯ
Указатели на ключ (key) и на первый элемент таблицы
(base) должны иметь тип "указатель на элемент" и преоб-
разовываться к типу "указатель на символ".
В сравнении, осуществляемом функцией compar, не обяза-
тельно должен участвовать каждый байт, поэтому элементы
таблицы в дополнение к сравниваемым величинам могут со-
держать произвольные данные.
Хотя функция lsearch описывается как имеющая тип "ука-
затель на символ", возвращаемое ею значение следует
преобразовывать к типу "указатель на элемент".
ПРИМЕР
Приведем фрагмент программы, который считывает цепочки
символов в количестве, меньшем TABSIZE, и длиной, мень-
шей ELSIZE, и помещает прочитанные цепочки в таблицу,
исключая дубликаты.
#include
#include
#define TABSIZE 50
#define ELSIZE 120
char line [ELSIZE], tab [TABSIZE] [ELSIZE],
*lsearch ();
unsigned nel = 0;
int strcmp ();
...
while (fdets (line, ELSIZE, stdin) != NULL &&
nel < TABSIZE)
(void) lsearch (line, (char*) tab, &nel,
ELSIZE,strcmp);
...
СМ. ТАКЖЕ
bsearch(3C), hsearch(3C), string(3C), tsearch(3C).
ДИАГНОСТИКА
Если искомый объект данных найден, то обе функции,
lsearch и lfind, возвращают указатель на него. В про-
тивном случае функция lfind возвращает пустой указатель
NULL, а функция lsearch возвращает указатель на новый,
добавленный объект.
СЮРПРИЗЫ
Недостаток свободного пространства в таблице для добав-
ления нового объекта данных может привести к непредска-
зуемым последствиям.
|