У мові C, самі функції не являються змінними, але існує можливість створення покажчиків на функції, які можна присвоїти, розмістити в масиві, передати іншим функціям, бути поверненими іншими функціями тощо. Ми проілюструємо це шляхом модифікації функції сортування, написаної раніше в цьому розділі, в такий спосіб, що якщо задано опцію -n, це сортуватиме ввідні рядки за числовим значенням замість лексикографічного.
Процес сортування часто складається з трьох частин: порівнювання — яке визначає порядок пар об'єктів, обмін — що змінює їхню послідовність, і алгоритм сортування — що здійснює порівнювання і обміни до тих пір, доки об'єкти буде упорядковано. Алгоритм сортування повинен бути незалежним від операцій порівнювання і обміну, щоб через передачу йому різноманітних функцій порівнювання і обміну, ми могли добитися сортування за різними критеріями. Саме цей підхід застосовується у нашій новій сортувальній програмі.
Лексикографічне порівняння двох рядків здійснюватиметься strcmp, так як і раніше; нам також знадобиться нова функція numcmp, яка би порівнювала два рядки на основі числового значення і повертала такий самий вказівник стану, як це робить strcmp. Ці функції оголошено попередуmain і покажчик до відповідної передаватиметься qsort. Ми занедбали обробку помилок для аргументів, щоб зосередитись на основних питаннях.
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000 /* максимальна кількість рядків для *
* сортування */
char *lineptr[MAXLINES]; /* покажчики на текст рядків */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(void *lineptr[], int left, int right,
int (*comp)(void *, void *));
int numcmp(char *, char *);
/* сортує рядки вводу */
main(int argc, char *argv[])
{
int nlines; /* кількість прочитаних рядків вводу */
int numeric = 0; /* 1, якщо сортування за числовим *
* значенням */
if (argc > 1 && strcmp(argv[1], "-n") == 0)
numeric = 1;
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
qsort((void**) lineptr, 0, nlines-1,
(int (*)(void*,void*))(numeric ? numcmp : strcmp));
writelines(lineptr, nlines);
return 0;
} else {
printf("input too big to sort\n");
return 1;
}
}
У виклику qsort, strcmp і numcmp — це адреси функцій. Оскільки відомо, що це функції, оператор & необов'язковий, так само як його не потрібно перед назвою масиву.
Ми написали qsort, таким чином, що вона могла обробляти будь-який тип даних, а не тільки символьні ланцюжки. Як вказує прототипом функції, qsort очікує масиву покажчиків, два цілих і функцію з двома покажчиковими аргументами. Для останніх використовується загальний тип покажчика void *. Будь-який покажчик можна звести до void * і назад, без втрати інформації, тож ми можемо викликати qsort через зведення аргументів до void *. Складне зведення аргуметів функції зводить також аргументи порівнювальної функції. Це, загалом, не матиме жодного ефекту на дійсному представленні, зате запевнить компілятор, що все гаразд.
/* qsort: сортує v[left]...v[right] у зростаючій послідовності */
void qsort(void *v[], int left, int right,
int (*comp)(void *, void *))
{
int i, last;
void swap(void *v[], int, int);
if (left >= right) /* не робить нічого, якщо масив містить */
return; /* менше ніж два елементи */
swap(v, left, (left + right)/2);
last = left;
for (i = left+1; i <= right; i++)
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
qsort(v, left, last-1, comp);
qsort(v, last+1, right, comp);
}
Оголошення варте вивчення. Четвертим параметром qsort є
int (*comp)(void *, void *)
яке вказує, що comp — це покажчик на функцію, яка має два аргументи типу void * і повертаєint.
Використання comp у рядку
if ((*comp)(v[i], v[left]) < 0)
узгоджується з оголошенням — comp є покажчиком на функцію, *comp - це сама функція і
(*comp)(v[i], v[left])
— це її виклик. Дужки потрібні, щоб складові було приєднано належним чином; без них
int *comp(void *, void *) /* НЕПРАВИЛЬНО */
вказує на те, що comp — це функція, яка повертає покажчик на int, що являється зовсім не тим, що потрібно. Ми вже продемонстрували функцію strcmp, яка порівнює два ланцюжки. Ось інша, numcmp, що порівнює ланцюжки за початковим числовим значенням, обчисленого викликом atof:
#include <stdlib.h>
/* numcmp: порівнює s1 і s2 за числовим значенням */
int numcmp(char *s1, char *s2)
{
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
Функція swap, яка порівнює два покажчики, є тотожною тій, що ми представили раніше в цьому розділі за винятком того, що оголошення змінено на void *.
void swap(void *v[], int i, int j;)
{
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
Можна також додати багато інших опцій до програми сортування, деякі можуть виявитись цікавими вправами.
Вправа 5-14. Змініть програму sort так, щоб вона брала прапорець -r, який вказував би сортування в оберненій (спадаючій) послідовності. Впевніться, що -r працює разом із -n.
Вправа 5-15. Додайте опцію -f для вирівнювання верхнього і нижнього регістрів, тож під час сортування не існуватиме регістрової відмінності; наприклад, a із A вважатимуться рівнозначними при порівнянні.
Вправа 5-16. Додайте опцію -d («directory order»), яка би здійснювала порівнювання тільки літер, чисел і пробілів. Впевніться, що вона працює разом із -f.
Вправа 5-17. Додайте можливість пошуку по ділянці, тож сортування можна здійснювати в окремих ділянках всередині рядків, кожне поле сортоване у відповідності з окремим набором опцій. (Індекс цієї книжки було сортовано за допомогою опцій -df для індексної категорії і опції-n для номерів сторінок.)
