Иллюстрированный самоучитель по практике программирования

Библиотеки

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

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

Рассмотрим реализацию функции сравнения для сортировки массива строк, случая, встречающегося довольно часто. Мы написали функцию scmp, которая – преобразует параметры к другому типу и затем вызывает strcmp для выполнения самого сравнения:

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Библиотеки

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

Мы не можем напрямую использовать strcmp как функцию сравнения, поскольку qsort передает адрес каждого элемента в массиве &stг [ i ] (типа char**), а не str[i] (типа char *), как показано на рисунке:

Иллюстрированный самоучитель по практике программирования › Алгоритмы и структуры данных › Библиотеки

Для сортировки элементов массива строк с str [0] по str [N-1 ] функция qsort должна получить массив, его длину, размер сортируемых элементов и функцию сравнения:

char *str[N];
qsort(str, N, sizeof(str[OJ), scmp);
Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.