HSEARCH(3C) HSEARCH(3C) НАЗВАНИЕ hsearch, hcreate, hdestroy - управление хеш-таблицами поиска СИНТАКСИС |#include | |ENTRY *hsearch (item, action) |ENTRY item; |ACTION action; | |int hcreate (nel) |unsigned nel; | |void hdestroy ( ) ОПИСАНИЕ Функция hsearch предназначена для выполнения поиска в хеш-таблице в соответствии с алгоритмом, описанным в книге Д. Кнута: Искусство программирования для ЭВМ. Т. 3. Сортировка, поиск. - М.: Мир, 1978. Раздел 6.4, ал- горитм D. Функция hsearch возвращает указатель внутрь таблицы на искомые данные. Аргумент item - это структура типа ENTRY (определенная во включаемом файле ), содержащая два указателя: 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 |#include | |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) для выделения памяти. ОГРАНИЧЕНИЯ В каждый момент времени может быть активна только одна хеш-таблица.@