Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
VPS/VDS серверы. 30 локаций на выбор

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

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

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

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

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

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

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

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

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

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

HSEARCH(3C)

НАЗВАНИЕ
hsearch, hcreate, hdestroy - управление хеш-таблицами поиска

СИНТАКСИС


	#include <search.h>

	

	ENTRY *hsearch (item, action)

	ENTRY item;

	ACTION action;

	

	int hcreate (nel)

	unsigned nel;

	

	void hdestroy ( )

ОПИСАНИЕ
Функция hsearch предназначена для выполнения поиска в хеш-таблице в соответствии с алгоритмом, описанным в книге Д. Кнута: Искусство программирования для ЭВМ. Т. 3. Сортировка, поиск. - М.: Мир, 1978. Раздел 6.4, алгоритм D.

Функция hsearch возвращает указатель внутрь таблицы на искомые данные. Аргумент item - это структура типа ENTRY (определенная во включаемом файле <search.h>), содержащая два указателя: item.key указывает на сравниваемый ключ, а item.data указывает на любые дополнительные данные, ассоциированные с этим ключом. Указатели на переменные типов, отличных от символьного, следует преобразовывать к типу "указатель на символ". Аргумент action имеет тип ACTION и задает способ действий в случае неудачного поиска: значение ENTER означает, что искомый элемент следует поместить в таблицу; значение FIND означает, что в случае неудачи нужно вернуть пустой указатель NULL.

Функция hcreate выделяет достаточное количество пространства для таблицы и должна вызываться перед использованием функции hsearch. Значением переменной nel является ожидаемое максимальное количество элементов таблицы. Это число можно взять с запасом, чтобы уменьшить среднее время поиска.

Функция hdestroy ликвидирует таблицу поиска, за вызовом этой функции может следовать последующий вызов функции создания таблицы hcreate.

ПРИМЕЧАНИЯ
Функция hsearch использует открытую адресацию с мультипликативной хеш-функцией. Исходный текст функции предоставляет и другие возможности, которые можно выбрать, компилируя hsearch с определением для препроцессора следующих имен:
DIV Вместо мультипликативной хеш-функции использовать остаток от деления на размер хеш-таблицы.
USCR При поиске вызывать функцию сравнения, предоставляемую пользователем. Функция должна называться hcompar и вести себя подобно функции strcmp [см. string(3C)].
CHAINED Для разрешения коллизий использовать списки синонимов. Если выбирается эта опция, то становятся доступными также следующие опции:
START Помещать новые элементы в начало списка синонимов (по умолчанию - в конец).
SORTUP Поддерживать списки синонимов отсортированными по ключу в порядке возрастания.
SORTDOWN Поддерживать списки синонимов отсортированными по ключу в порядке убывания.

Кроме того, есть флаги препроцессора для получения отладочной печати (-DDEBUG) и для включения драйвера отладки в вызываемую функцию (-DDRIVER). Для получения более детальной информации следует обратиться к исходному тексту функции.

ПРИМЕР
Следующая программа считывает тройки: цепочка символов и два числа, и размещает их в хеш-таблице, отбрасывая дубликаты. Затем считываются цепочки символов, находятся и распечатываются соответствующие элементы хеш-таблицы.


	#include <stdio.h> 

	#include <search.h> 



	struct info {         /* Дополнительная информация, ас- 

	                         социированная с ключом */ 

	  int age, room; 

	}; 



	#define NUM_EMPL 5000 /* Количество элементов в таблице 

	                         поиска */ 



	main () 

	{ 

	/* Массив для размещения цепочек символов */ 

	  char string_space [NUM_EMPL*20]; 



	/* Массив для размещения информации о служащих */ 

	  struct info info_space [NUM_EMPL]; 



	/* Указатель на свободное место в массиве цепочек */ 

	  char *str_ptr = string_space; 



	/* Указатель на свободное место в массиве служащих */ 

	  struct info *info_ptr = info_space; 



	  ENTRY item, *found_item, *hsearch (); 



	  char name_to_find [30]; /* Искомое имя */ 

	  int i; 



	/* Создать таблицу */ 

	  (void) hcreate (NUM_EMPL); 



	/* Цикл чтения исходной информации */ 

	  while (scanf ("%s%d%d", str_ptr, &info_ptr->age, 

	          &info_ptr->room) != EOF && i++ < NUM_EMPL) { 



	/* Сформировать элемент таблицы */ 

	    item.key = str_ptr; 

	    item.data = (char *) info_ptr; 

	    str_ptr += strlen (str_ptr) + 1; 

	    info_ptr++; 



	/* Поместить элемент в таблицу */ 

	    (void) hsearch(item, ENTER); 

	  }; 



	/* Доступ к таблице */ 

	  item.key = name_to_find; 

	  while (scanf ("%s", item.key) != EOF) { 



	    if ((found_item = hsearch (item, FIND)) != NULL) { 



	    /* Если элемент найден в таблице */ 

	      (void) printf ("found %s, age= %d, room= %d\n", 

	         found_item->key, 

	         ((struct info *) found_item->data)->age, 

	         ((struct info *) found_item->data)->room); 

	     

	    } else { 

	    /* Если элемент не найден в таблице */ 

	      (void) printf ("no such employee %s\n", 

	         name_to_find) 

	    } 

	  } 

	} 

СМ. ТАКЖЕ
bsearch(3C), lsearch(3C), malloc(3C), malloc(3X), string(3C), tsearch(3C).

ДИАГНОСТИКА
Функция hsearch возвращает пустой указатель NULL, если значение переменной action равно FIND и элемент не может быть найден или если значение переменной action равно ENTER и таблица заполнена.

ПРЕДОСТЕРЕЖЕНИЯ
Функции hsearch и hcreate используют функцию malloc(3C) для выделения памяти.

ОГРАНИЧЕНИЯ
В каждый момент времени может быть активна только одна хеш-таблица.

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

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

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

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

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

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

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

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

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

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

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

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

Новости мира 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
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...