Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

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

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

VPS в России, Европе и США

Бесплатная поддержка и администрирование

Оплата российскими и международными картами

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...