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 следующим образом: