| Сервер поддерживается Центром Информационных Технологий (095) 932-9212, 932-9213, 939-0783 E-mail: info@citforum.ru

Сервер содержит море(!) аналитической информации | CIT Forum CD-ROM

### 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 | При поиске вызывать функцию сравнения, предоставляемую пользователем. Функция должна называться hcompar и вести себя подобно функции strcmp [см. string(3C)].
CHAINED | Для разрешения коллизий использовать списки синонимов. Если выбирается эта опция, то становятся доступными также следующие опции:
| 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)
    	    }
    	  }
    	}

СМ. ТАКЖЕ
bsearch(3C), lsearch(3C), malloc(3C), malloc(3X), string(3C), tsearch(3C).

ДИАГНОСТИКА
Функция hsearch возвращает пустой указатель NULL, если значение переменной action равно FIND и элемент не может быть найден или если значение переменной action равно ENTER и таблица заполнена.

ПРЕДОСТЕРЕЖЕНИЯ
Функции hsearch и hcreate используют функцию malloc(3C) для выделения памяти.

ОГРАНИЧЕНИЯ
В каждый момент времени может быть активна только одна хеш-таблица.

Comments: info@citmgu.ru Designed by Andrey Novikov Copyright © CIT