Библиотечные функции сортировки и поиска

В библиотеку включены функции для реализации поиска и сортировки структурных данных, размещенных в массивах. Эти функции характеризуются следующим образом:

1) в функции передаются параметры, представляющие характеристики массива – указатель на начало, размер одного структурного элемента данных и число элементов в массиве.

2) передается указатель на пользовательскую функцию, определяющую критерий сравнения структурных объектов.

3) при поиске передается еще указатель на ключевой элемент, который должен быть структурой того же типа, что и в массиве.

Прототипы находятся в файлах stdlib.h или search.h.

Функции lfind() и lsearch() выполняют линейный поиск в массиве, перебирая подряд все элементы.

Их спецификация следующая:

void *lfind(cjnst void *key, const void *base,size_t *phelem, size_t width,

int(*fcmp)(const void * elem 1,cjnst void *elem2))

void * lsearch (/* те же параметры*/

Функция lfind возвращает указатель на найденный элемент или Null, если элемент не найден, то добавляется в массив в конце еще один элемент, на который ссылается параметр key.

Параметры:

key – ссылка на ключевой элемент, это должна быть структура такая же как и в массиве.

base - начальный адрес массива для поиска

phelem - указатель на число элементов в массиве

width - размер одного структурного элемента

fcmp -указатель на пользовательскую функцию, которая должна принимать два параметра, указатель на структурные элементы того же типа что и в массиве.

Она должна возвращать 0 если элементы равны, по критерию сравнения, который пользователь заложил в эту функцию, или любое ненулевое значение в противном случае.

Функции bsearch () и gsort () реализуют, соответственно, бинарный поиск в упорядоченном массиве и сортировку методом Хоара.

Их спецификация следующая:

void * bsearch (/* те же параметры, что у предыдущих функций */)

Результат у bsearch() тот же, что у lfind(). Единственное отличие состоит в том, что функция (*fcmp) () должна возвращать значение меньше нуля, если

*elem1< * elem2, равное нулю, если

*elem1= * elem2, и больше нуля, если

*elem1> * elem2. и снова решение о том, как понимать отношения <, =, > возлагается на функцию пользователя.

void gsort ( void * base, sire_t phelem, size_t width,

int (* fcmp) (const void * elem1, const void * elem2)

То же назначение параметров, но отсутствует указатель на ключевой элемент. pnelem – само значение, а не указатель. Функция (* fcmp)() должна удовлетворять тем же условиям, что у bsearch(). Т.о., эта функция должна быть чуть сложнее, чем аналогичная функция для линейного поиска из-за того, что она должна давать направление для продолжения поиска элемента.