hsearch()

Искать ключ в ассоциативном массиве (хэш-таблице)

Прототип:

#include <search.h>
ENTRY * hsearch( ENTRY item,
ACTION action );

Аргументы:

item
Структура типа ENTRY, объявленная в <search.h>, которая содержит:
char *key
указатель на ключ, используемый при сравнении записей.
void *data
указатель на данные произвольного типа, которые будут ассоциироваться с переданным ключом.
action
Перечислитель типа ACTION, также объявленный в <search.h>, определяющий действие, которое применяется в случае отсуствия записи в таблице.
ENTER
добавляет новую запись в таблицу в соответствующем месте. Если новая запись дублирует существующую, добавления не происходит, и hsearch() возвращает указатель на существующую.
FIND
не добавляет новую запись в таблицу. Если запись не найдена, hsearch() возвращает NULL.

Библиотека:

libc

Описание:

Функция hsearch() ищет запись согласно алгоритму D (6.4) из монографии под авторством Д.Кнута (см. Тематические ссылки). Перед использованием функции необходимо вызвать hcreate() для создания хэш-таблицы.

Функция hsearch() возвращает указатель на место в хэш-таблице, где находится запись. Эта функция использует strcmp() в качестве функция сравнения.

Функции hsearch() и hcreate() используют malloc() для выделения памяти.

Единовременно может быть использована только одна хэш-таблица. Для удаления таблицы можно использовать hdestroy().

Возвращаемое значение:

Найденный указатель или NULL в случаях, когда действие FIND не найдено, или когда передано действие ENTER, но таблица полностью занята.

Примеры:

Пример ниже читает строки, завершающиеся двумя числами, и помещает их в хэш таблицу, отбрасывая дубликаты. Затем он читает строки, находит соответсвующую запись в таблице и выводит ее.

#include <stdio.h>
#include <search.h>
#include <string.h>
#include <stdlib.h>
struct info { /* this is the info stored in table */
int age, room; /* other than the key */
};
#define NUM_EMPL 5000 /* # of elements in search table */
int main( void )
{
char string_space[NUM_EMPL*20]; /* space to store strings */
struct info info_space[NUM_EMPL]; /* space to store employee info */
char *str_ptr = string_space; /* next avail space in string_space */
struct info *info_ptr = info_space; /* next avail space in info_space */
ENTRY item, *found_item;
char name_to_find[30]; /* name to look for in table */
int i = 0;
/* create table */
(void)hcreate( NUM_EMPL );
while ( scanf( "%s%d%d", str_ptr, &info_ptr->age,
&info_ptr->room ) != EOF && i++ < NUM_EMPL )
{
/* put info in structure, and structure in item */
item.key = str_ptr;
item.data = (void *)info_ptr;
str_ptr += strlen( str_ptr ) + 1;
info_ptr++;
/* put item into table */
(void)hsearch( item, ENTER );
}
/* access table */
item.key = name_to_find;
while ( scanf( "%s", item.key ) != EOF )
{
if ( (found_item = hsearch( item, FIND )) != NULL )
{
/* if item is in the table */
(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 );
}
}
hdestroy();
return (0);
}

Классификация:

POSIX 1003.1 XSI

Точка остановки потока
Нет
Обработчик прерываний
Нет
Обработчик сигналов
Да
В потоке
Да

Тематические ссылки:

bsearch(), hcreate(), hdestroy(), malloc(), strcmp()

"The Art of Computer Programming, Volume 3, Sorting and Searching"/ Donald E. Knuth. — Addison-Wesley Publishing Company, 1973




Предыдущий раздел: Описание API системной библиотеки