Язык программирования Си. Издание 3-е, исправленное

#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("Bведено слишком много строк\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– это указатель на функцию, которая имеет два аргумента- указателя и выдает результат типа 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. Модифицируйте программу сортировки, чтобы она реагировала на параметр – r, указывающий, что объекты нужно сортировать в обратном порядке, т. е. в порядке убывания. Обеспечьте, чтобы – r работал и вместе с – n.

Упражнение 5.15. Введите в программу необязательный параметр – f, задание которого делало бы неразличимыми символы нижнего и верхнего регистров (например, a и A должны оказаться при сравнении равными).

Упражнение 5.16. Предусмотрите в программе необязательный параметр – d, который заставит программу при сравнении учитывать только буквы, цифры и пробелы. Организуйте программу таким образом, чтобы этот параметр мог работать вместе с параметром – f.