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

 for(i = left+1; i ‹= right; i++) /* деление на части */
 if (v[i] ‹ v[left])
 swap(v, ++last, i);
 swap(v, left, last); /* перезапоминаем делящий элемент */
 qsort(v, left, last-1);
 qsort(v, last+1, right);
}

В нашей программе операция перестановки оформлена в виде отдельной функции (swap), поскольку встречается в qsort трижды.

/* swap: поменять местами v[i] и v[j] */
void swap(int v[], int i, int j)
{
 int temp;
 temp = v[i];
 v[i] = v[j];
 v[j] = temp;
}

Стандартная библиотека имеет функцию qsort, позволяющую сортировать объекты любого типа.

Рекурсивная программа не обеспечивает ни экономии памяти, поскольку требуется где-то поддерживать стек значений, подлежащих обработке, ни быстродействия; но по сравнению со своим нерекурсивным эквивалентом она часто короче, а часто намного легче для написания и понимания. Такого рода программы особенно удобны для обработки рекурсивно определяемых структур данных вроде деревьев; с хорошим примером на эту тему вы познакомитесь в параграфе 6.5.

Упражнение 4.12. Примените идеи, которые мы использовали в printd, для написания рекурсивной версии функции itoa; иначе говоря, преобразуйте целое число в строку цифр с помощью рекурсивной программы.

Упражнение 4.13. Напишите рекурсивную версию функции reverse(s), переставляющую элементы строки в ту же строку в обратном порядке.

4.11 Препроцессор языка Си

Некоторые возможности языка Си обеспечиваются препроцессором, который работает на первом шаге компиляции. Наиболее часто используются две возможности: #include, вставляющая содержимое некоторого файла во время компиляции, и #define, заменяющая одни текстовые последовательности на другие. В этом параграфе обсуждаются условная компиляция и макроподстановка с аргументами.

4.11.1 Включение файла

Средство #include позволяет, в частности, легко манипулировать наборами #define и объявлений. Любая строка вида

#include "имя-файла"

или

#include ‹имя-файла›

заменяется содержимым файла с именем имя-файла. Если имя-файла заключено в двойные кавычки, то, как правило, файл ищется среди исходных файлов программы; если такового не оказалось или имя-файла заключено в угловые скобки ‹ и ›, то поиск осуществляется по определенным в реализации правилам. Включаемый файл сам может содержать в себе строки #include.

Часто исходные файлы начинаются с нескольких строк #include, ссылающихся на общие инструкции #define и объявления extern или прототипы нужных библиотечных функций из заголовочных файлов вроде ‹stdio.h›. (Строго говоря, эти включения не обязательно являются файлами; технические детали того, как осуществляется доступ к заголовкам, зависят от конкретной реализации.)

Средство #include– хороший способ собрать вместе объявления большой программы. Он гарантирует, что все исходные файлы будут пользоваться одними и теми же определениями и объявлениями переменных, благодаря чему предотвращаются особенно неприятные ошибки. Естественно, при внесении изменений во включаемый файл все зависимые от него файлы должны перекомпилироваться.

4.11.2 Макроподстановка

Определение макроподстановки имеет вид:

#define имя замещающий-текст

Макроподстановка используется для простейшей замены: во всех местах, где встречается лексема имя, вместо нее будет помещен замещающий-текст. Имена в #define задаются по тем же правилам, что и имена обычных переменных. Замещающий текст может быть произвольным. Обычно замещающий текст завершает строку, в которой расположено слово #define, но в длинных определениях его можно продолжить на следующих строках, поставив в конце каждой продолжаемой строки обратную наклонную черту \. Область видимости имени, определенного в #define, простирается от данного определения до конца файла. В определении макроподстановки могут фигурировать более ранние #define– определения. Подстановка осуществляется только для тех имен, которые расположены вне текстов, заключенных в кавычки. Например, если YES определено с помощью #define, то никакой подстановки в printf("YES") или в YESMAN выполнено не будет.

Любое имя можно определить с произвольным замещающим текстом. Например:

#define forever for(;;) /* бесконечный цикл */

определяет новое слово forever для бесконечного цикла.

Макроподстановку можно определить с аргументами, вследствие чего замещающий текст будет варьироваться в зависимости от задаваемых параметров. Например, определим max следующим образом:

#define max(A, B) ((A) › (B) ? (A) : (B))

Хотя обращения к max выглядят как обычные обращения к функции, они будут вызывать только текстовую замену. Каждый формальный параметр (в данном случае A и B) будет заменяться соответствующим ему аргументом. Так, строка

x = max(p+q, r+s);

будет заменена на строку

x = ((p+q) › (r+s) ? (p+q) : (r+s));

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

Если вы внимательно проанализируете работу max, то обнаружите некоторые подводные камни. Выражения вычисляются дважды, и если они вызывают побочный эффект (из-за инкрементных операций или функций ввода-вывода), это может привести к нежелательным последствиям. Например,

max(i++, j++) /* НЕВЕРНО */

вызовет увеличение i и j дважды. Кроме того, следует позаботиться о скобках, чтобы обеспечить нужный порядок вычислений. Задумайтесь, что случится, если при определении

#define square(x) x*x /* НЕВЕРНО */

вызвать square (z+1).

Тем не менее макросредства имеют свои достоинства. Практическим примером их использования является частое применение getchar и putchar из ‹stdio.h›, реализованных с помощью макросов, чтобы из6ежать расходов времени от вызова функции на каждый обрабатываемый символ. Функции в ‹ctype.h› обычно также реализуются с помощью макросов. Действие #define можно отменить с помощью #undef:

#undef getchar
int getchar(void) {…}

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

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