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)
для выделения памяти.
ОГРАНИЧЕНИЯ
В каждый момент времени может быть активна только одна
хеш-таблица.
|