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