HSEARCH(3C)
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 с определением для препроцессора следующих имен:
| Вместо мультипликативной хеш-функции использовать остаток от деления на размер хеш-таблицы. | |
| При поиске вызывать функцию сравнения, предоставляемую пользователем. Функция должна называться hcompar и вести себя подобно функции strcmp [см. ]. | |
| Для разрешения коллизий использовать списки синонимов. Если выбирается эта опция, то становятся доступными также следующие опции: | |
| 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) } } }
СМ. ТАКЖЕ
, , , , , .
ДИАГНОСТИКА
Функция hsearch возвращает пустой указатель NULL, если значение переменной action равно FIND и элемент не может быть найден или если значение переменной action равно ENTER и таблица заполнена.
ПРЕДОСТЕРЕЖЕНИЯ
Функции hsearch и hcreate используют функцию для выделения памяти.
ОГРАНИЧЕНИЯ
В каждый момент времени может быть активна только одна хеш-таблица.
