BSEARCH(3C) BSEARCH(3C) НАЗВАНИЕ bsearch - бинарный поиск в отсортированной таблице СИНТАКСИС |#include | |char *bsearch ((char *) key, (char *) base, nel, sizeof (*key), compar) |unsigned nel; |int (*compar) ( ); ОПИСАНИЕ Функция bsearch предназначена для выполнения бинарного поиска в соответствии с алгоритмом, описанным в книге Д. Кнута: Искусство программирования для ЭВМ. Т. 3. Сортировка, поиск. - М.: Мир, 1978. Раздел 6.2.1, алго- ритм B. Функция bsearch возвращает указатель внутрь таблицы на искомые данные. Предварительно таблица должна быть от- сортирована в возрастающем порядке согласно предостав- ленной функции сравнения. Аргумент key указывает на объект данных, разыскиваемый в таблице (ключ поиска); base указывает на первый элемент таблицы; nel задает количество элементов в таблице; compar - это функция сравнения, аргументами которой при вызове служат два указателя на сравниваемые элементы. В соответствии с тем, какое целое число она возвращает: меньшее нуля, равное нулю или большее нуля, первый аргумент считается меньшим, равным или большим по отношению ко второму. ПРИМЕР Следующий пример демонстрирует поиск в таблице, содер- жащей указатели на узлы, которые состоят из цепочек символов и их длин. Таблица отсортирована в алфавитном порядке по цепочкам символов в узлах. Приведем фрагмент программы, который считывает цепочку символов и ищет соответствующий узел, затем распечаты- вает цепочку символов с ее длиной или выводит сообщение об ошибке. |#include |#include |#define TABSIZE 1000 |struct node { /* Структура узлов */ | char *string; | int length; |}; |struct node table [TABSIZE]; /* Таблица для поиска */ | ... |{ | struct node *node_ptr, node; | int node_compare (); /* Функция сравнения узлов */ | char str_space [20]; /* Пространство для ввода цепочки | символов */ | ... | node.string = str_space; | while (scanf ("%s", node.string) != EOF) { | node_ptr = | (struct node *) bsearch ((char *) (&node), | (char *) table, TABSIZE, | sizeof (struct node), node_compare); | if (node_ptr != NULL) { | (void) printf ("string = %20s, length = %d\n", | node_ptr->string, node_ptr->length); | } else { | (void) printf ("not found:%s\n", node.string); | } | } |} |/* | Следующая функция сравнивает два узла по цепочкам | символов на основе алфавитного порядка |*/ |int node_compare (node1, node2) |char *node1, *node2; |{ | return strcmp (((struct node *) node1) -> string, | ((struct node *) node2) -> string); |} ПРИМЕЧАНИЯ Указатели на ключ (key) и на первый элемент таблицы (base) должны иметь тип "указатель на элемент" и преоб- разовываться к типу "указатель на символ". В сравнении, осуществляемом функцией compar, не обяза- тельно должен участвовать каждый байт, поэтому элементы таблицы в дополнение к сравниваемым величинам могут со- держать произвольные данные. Хотя функция bsearch описывается как имеющая тип "ука- затель на символ", возвращаемое ею значение следует преобразовывать к типу "указатель на элемент". СМ. ТАКЖЕ hsearch(3C), lsearch(3C), qsort(3C), tsearch(3C). ДИАГНОСТИКА В случае неудачного поиска результатом служит пустой указатель NULL.