Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Первый аргумент представляет собой указатель на начало сортируемого массива. Стандарт ANSI С разрешает приведение типа указателя на данные к типу указателя на void, таким образом, позволяя первому фактическому аргументу qsort() ссылаться на массив любого вида.

Во втором аргументе передается количество элементов, подлежащих сортировке. Прототип преобразует это значение в тип size t. Как уже несколько раз упоминалось, size t является целочисленным типом, который возвращается операцией sizeof и определен в стандартных заголовочных файлах.

Из-за того, что функция qsort() преобразует свой первый аргумент в указатель на void, она утрачивает информацию о размере каждого элемента массива. Чтобы скомпенсировать это, следует явно сообщить qsort() размер объекта данных. Именно для такой цели служит третий аргумент. Например, если вы сортируете массив типа double, то в третьем аргументе должны указать sizeof (double).

Наконец, qsort() требуется указатель на функцию, которая будет использоваться для определения порядка сортировки. Функция сравнения должна принимать два аргумента — указатели на два сравниваемых элемента. Она возвращает положительное целое число, если первый элемент должен следовать за вторым, ноль, если элементы одинаковы, и отрицательное целое число, если второй элемент должен следовать за первым. Функция qsort() вызывает эту функцию с передачей ей значений указателей, которые вычисляет на основе другой предоставленной информации.

Форма функции сравнения задана в последнем аргументе прототипа qsort():

int (*compar)(const void *, const void *)

Здесь видно, что последний аргумент qsort() представляет собой указатель на функцию, возвращающую значение int и принимающую два аргумента, каждый из которых является указателем на тип const void. Эти два указателя ссылаются на сравниваемые элементы.

Препроцессор и библиотека С 701

Листинг 16.17 и последующее обсуждение иллюстрируют способ определения функции сравнения и применения функции qsort(). В программе создается массив случайных значений с плавающей запятой, который затем сортируется.

Листинг 16.17. Программа gsorter .с

702 Глава 16

Ниже показаны результаты пробного запуска:

Давайте рассмотрим два ключевых момента: использование qsort() и определение mycomp().

Использование функции qsort()

Функция qsort() сортирует массив объектов данных. Ее прототип ANSI имеет следующий вид:

void qsort (void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *11;

Первый аргумент — это указатель на начало сортируемого массива. В программе применяется фактический аргумент vals, представляющий собой имя массива типа double; следовательно, он является указателем на первый элемент массива. В прототипе ANSI для аргумента vals предусмотрено приведение к типу указателя на void. Причина в том, что стандарт ANSI С разрешает приводить любой тип указателя на данные к типу указателя на void, тем самым позволяя первому фактическому аргументу в qsort() ссылаться на массив любого вида.

Во втором аргументе задается количество элементов, предназначенных для сортировки. В листинге 16.17 это N, т.е. число элементов массива. Прототип преобразует это значение в тип size t.

Третий аргумент — это размер каждого элемен та, в данном случае sizeof (double).

Последним аргументом, mycomp, является адрес функции, которая должна использоваться для сравнения элементов.

Определение функции mycomp()

Как упоминалось ранее, прототип qsort() устанавливает форму функции сравнения:

int (*compar) (const void *, const void *)

Здесь видно, что последний аргумент является указателем на функцию, которая возвращает значение int и принимает два аргумента. Каждый из этих аргументов представляет собой указатель на тип const void. Мы привели в соответствие с ним прототип функции mycomp():

int mycomp(const void * p1, const void * p2);

Препроцессор и библиотека С 703

Вспомните, что имя функции, передаваемое в качестве аргумента, выступает как указатель на нее, поэтому mycomp совпадает с прототипом compar.

Функция qsort() передает в функцию сравнения адреса двух сравниваемых элементов. В этой программе переменным p1 и р2 присваиваются адреса двух значений типа double, предназначенных для сравнения. Обратите внимание, что первый аргумент в qsort() ссылается на массив в целом, а два аргумента функции сравнения ссылаются на два элемента в массиве. Здесь возникает проблема. Чтобы сравнить значения, для которых доступны только указатели, эти указатели необходимо разыменовать. Так как значения имеют тип double, указатели должны быть разыменованы в тип double. Однако функции qsort() требуются указатели на тип void. Обойти проблему можно, объявив указатели нужного типа внутри функции и инициализировав их значениями, которые передаются в аргументах:

/* сортировка по возрастанию */

int mycomp (const void * p1, const void * p2)

{

/* для доступа к значениям необходимо использовать указатели на double */ const double * al = (const double *) p1; const double * a2 = (const double *) p2;

if (*al < *a2) return -1; else if (*al == *a2) return 0; else

return 1;

}

Короче говоря, в целях универсальности в qsort() и в функции сравнения применяются указатели на void. Как следствие, функции qsort() придется явно сообщить размер каждого элемента массива, а внутри определения функции сравнения преобразовать аргументы типа указателей на void в указатели на подходящий тип данных.

На заметку! void * в С и C++

В языках С и C++ указатели на void трактуются по-разному. В обоих языках вы можете присваивать переменной типа void * указатель любого типа. Например, при вызове функции qsort() в листинге 16.17 выполняется присваивание типа double * указателю на тип void *. Но язык C++ требует приведения типа, когда осуществляется присваивание указателя void * указателю другого типа, в то время как в С такое требование отсутствует. Например, функция mycomp() из листинга 16.17 содержит это приведение типа для указателя p1 типа void *:

const double * al = (const double *) p1;

В языке С подобное приведение типа необязательно; в языке C++ оно обязательно. Поскольку версия с приведением типа работает в обоих языках, имеет смысл использовать его всегда. Впоследствии при переводе программы на язык C++ вам не придется помнить о необходимости изменения этой части кода.

Давайте взглянем на еще один пример функции сравнения. Предположим, что имеются следующие объявления:

struct names {

char first[40]; char last [40];

};

struct names staff[100];

704 глава 16

Как должен выглядеть вызов qsort() ? Следуя модели, реализованной в листинге 16.17, вызов мог бы иметь следующий вид:

qsortfstaff, 100, sizeof(struct names), comp);

Здесь comp представляет собой имя функции сравнения. На что должна быть похожа эта функция? Пусть необходимо выполнить сортировку по фамилии, а затем по имени. Можно было бы написать следующую функцию: