[<<Previous Entry] [^^Up^^] [Next Entry>>] [Menu] [About The Guide]
 Поиск и сортировка (3C)

Существует несколько библиотечных функций для поиска, сортировки и
упорядочения данных в памяти. Ниже приведена информация, дополняющая
Справочное руководство программиста ОС UNIX System V.
Библиотечные функции learch, lfind, qsort и bsearch работают с
таблицами однотипных объектов, то есть с массивами. Элемент массива
может иметь любой тип, то есть быть целым, действительным, структурой,
объединением и т.д. Все функции при работе основываются на начале
массива, размере элемента и количестве элементов в массиве. В качестве
последнего параметра каждой функции передается пользовательская
функция сравнения. Эта функция получает два аргумента - элементы,
которые нужно сравнить. Если элементы являются структурами, то не
обязательно их сравнивать целиком. Можно выбрать различные поля как
первичные, вторичные и т.д. ключи для сравнения. Функция сравнения
вызывается из библиотечной функции. Для lsearch, lfind и bsearch
объект, на который указывает параметр key, сравнивается с элементами
таблицы. qsort производит сравнение элементов таблицы.
lsearch выполняет линейный поиск элемента, совпадающего с key, в
таблице, начинающейся с адреса base. Для lsearch и lfind функция
compar должна возвращать ноль при равенстве и ненулевое значение при
неравенстве. lsearch возвращает адрес элемента, который был найден в
таблице. Если такого элемента в таблице нет, lsearch включает его в
конец таблицы и увеличивает на единицу значение, на которое указывает
nelp. lfind делает только просмотр таблицы, возвращая NULL, если
объект не найден.
qsort  выполняет  сортировку  таблицы  из  nel  объектов,  начиная  со
стартового адреса таблицы.

Параметр  nel,   используемый  qsort  и  bsearch,  представляет  собой
беззнаковое целое.  Функция сравнения,  используемая qsort,  bsearch и
tsearch, должна  возвращать ноль,  если первый параметр равен второму,
положительное значение,  если первый  больше второго, и отрицательное,
если он меньше.

bsearch производит поиск в упорядоченной таблице. Он не делает
включения элементов в таблицу. Чтобы добавить элемент, вы должны
разместить его в конце таблицы и отсортировать увеличенную таблицу.
tsearch производит поиск/включение элемента в двоичное дерево. tfind
делает только поиск. Обе функции возвращают адрес соответствующего
узла дерева; tfind возвращает ноль, если элемент не найден.
hsearch выполняет поиск в хэш-таблице, возвращая адрес строки таблицы.
В этой строке содержатся адрес key и адрес data. Второй аргумент
функции может быть FIND - только поиск, или ENTER - поиск и включение.
По умолчанию, в качестве функции сравнения используется strcmp, а
коллизии разрешаются циклическим первым подходящим. Если вам доступен
исходный текст, вы можете изменить препроцессорные определения,
определяющие поведение функции.

lsearch(3C)   lfind()


qsort(3C)
bsearch(3C)


tsearch(3C)   tfind()     tdelete()    twalk()


hsearch(3C)   hcreate()   hdestroy()