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

last = left; /* переносится в v[0] */

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) , переставляющую элементы строки в ту же строку в обратном порядке.

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

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

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

или

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

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

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

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

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

#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) {…}

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

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