| Сервер поддерживается Центром Информационных Технологий (095) 932-9212, 932-9213, 939-0783 E-mail: info@citforum.ru

Сервер содержит море(!) аналитической информации | CIT Forum CD-ROM

### BSEARCH(3C)

НАЗВАНИЕ
bsearch - бинарный поиск в отсортированной таблице

СИНТАКСИС

    	#include <search.h>

    	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 <stdio.h>
    	#include <search.h>

    	#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

Comments: info@citmgu.ru Designed by Andrey Novikov Copyright © CIT