Unix Man (Справочное руководство)



              

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 с определением для препроцессора следующих имен:

DIV USCR CHAINED
Вместо мультипликативной хеш-функции использовать остаток от деления на размер хеш-таблицы.
При поиске вызывать функцию сравнения, предоставляемую пользователем. Функция должна называться hcompar и вести себя подобно функции strcmp [см. ].

Для разрешения коллизий использовать списки синонимов. Если выбирается эта опция, то становятся доступными также следующие опции:

START Помещать новые элементы в начало списка синонимов (по умолчанию - в конец).
SORTUP Поддерживать списки синонимов отсортированными по ключу в порядке возрастания.
SORTDOWN Поддерживать списки синонимов отсортированными по ключу в порядке убывания.
<


Содержание  Назад  Вперед