Васин Д.Ю. - Язык программирования Си. Курс лекций - 2003. Руководство для начинающих. М. Мир, 1988г. 512 с. Трой Д. Программирование на языке Си для персонального компьютера ibm pc Пер с англ. М. Радио и связь, 1991г. 432 с
 Скачать 1.1 Mb.
|
4.14. РекурсияВ Си допускается рекурсивное обращение к функциям, т. е. функция может обращаться сама к себе, прямо или косвенно. n = -n; } Хороший пример рекурсии - это быстрая сортировка, предложенная Ч.А.Р. Хоаром в 1962 г. Для заданного массива выбирается один элемент, который разбивает остальные элементы на два подмножества - те, что меньше, и те, что не меньше него. Та же процедура рекурсивно применяется и к двум полученным подмножествам. Если в подмножестве менее двух элементов, то сортировать нечего, и рекурсия завершается. Наша версия быстрой сортировки, разумеется, не самая быстрая среди всех возможных, но зато одна из самых простых. В качестве делящего элемента мы используем серединный элемент. /* qsort: сортирует v[left]...v[right] по возрастанию */ void qsort(int *v, int left, int right) { int i, last; void swap(int *v, int i, int j); if (left >= right) /* ничего не делается, если */ return; /* в массиве менее двух элементов */ swap(v, left, (left + right)/2); /* делящий элемент */ 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, позволяющую сортировать объекты любого типа. Рекурсивная программа не обеспечивает ни экономии памяти, поскольку требуется где-то поддерживать стек значений, подлежащих обработке, ни быстродействия; но по сравнению со своим нерекурсивным эквивалентом она часто короче, а часто намного легче для написания и понимания. Такого рода программы особенно удобны для обработки рекурсивно определяемых структур данных вроде деревьев; с хорошим примером на эту тему вы познакомитесь позже. 4.15. Препроцессор языка СиНекоторые возможности языка Си обеспечиваются препроцессором, который работает на первом шаге компиляции. Наиболее часто используются две возможности: #include, вставляющая содержимое некоторого файла во время компиляции, и #define, заменяющая одни текстовые последовательности на другие. Здесь обсудим условную компиляцию и макроподстановки с аргументами. 4.15.1. Включение файлаСредство #include позволяет, в частности, легко манипулировать наборами #define и объявлений. Любая строка вида #include "имя-файла" или #include <имя-файла> заменяется содержимым файла с именем имя-файла. Если имя-файла заключено в двойные кавычки, то, как правило, файл ищется среди исходных файлов программы; если такового не оказалось или имя-файла заключено в угловые скобки < и >, то поиск осуществляется по определенным в реализации правилам. Включаемый файл сам может содержать в себе строки #include. Часто исходные файлы начинаются с нескольких строк #include, ссылающихся на общие инструкции #define и объявления extern или прототипы нужных библиотечных функций из заголовочных файлов вроде Средство #include - хороший способ собрать вместе объявления большой программы. Он гарантирует, что все исходные файлы будут пользоваться одними и теми же определениями и объявлениями переменных, благодаря чему предотвращаются особенно неприятные ошибки. Естественно, при внесении изменений во включаемый файл все зависимые от него файлы должны перекомпилироваться. 4.15.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 из #undef getchar int getchar(void) {...} Как правило, это делается, чтобы заменить макроопределение настоящей функцией с тем же именем. Имена формальных параметров не заменяются, если встречаются в заключенных в кавычки строках. Однако, если в замещающем тексте перед формальным параметром стоит знак #, этот параметр будет заменен на аргумент, заключенный в кавычки. Это может сочетаться с конкатенацией (склеиванием) строк, например, чтобы создать макрос отладочного вывода: #define dprint(expr) printf(#expr " = %g\n", expr) Обращение к dprint(x/y); развернется в printf("x/y" " = %g\n", x/y); а в результате конкатенации двух соседних строк получим printf("x/y=%g\n", x/y); Внутри фактического аргумента каждый знак " заменяется на \", а каждая \ на \\, так что результат подстановки приводит к правильной символьной константе. Оператор ## позволяет в макрорасширениях конкатенировать аргументы. Если в замещающем тексте параметр соседствует с ##, то он заменяется соответствующим ему аргументом, а оператор ## и окружающие его символы-разделители выбрасываются. Например, в макроопределении paste конкатенируются два аргумента #define paste(front, back) front ## back так что paste(name, 1) сгенерирует имя name1. Правила вложенных использований оператора ## не определены. 4.15.3. Условная компиляцияСамим ходом препроцессирования можно управлять с помощью условных инструкций. Они представляют собой средство для выборочного включения того или иного текста программы в зависимости от значения условия, вычисляемого вовремя компиляции. Вычисляется константное целое выражение, заданное в строке #if. Это выражение не должно содержать ни одного оператора sizeof или приведения к типу и ни одной enum-константы. Если оно имеет ненулевое значение, то будут включены все последующие строки вплоть до #endif, или #elif, или #else. (Инструкция препроцессора #elif похожа на else if.) Выражение defined(имя) в #if есть 1, если имя было определено, и 0 в противном случае. Например, чтобы застраховаться от повторного включения заголовочного файла hdr.h, его можно оформить следующим образом: #if !defined(HDR) #define HDR /* здесь содержимое hdr.h */ #endif При первом включении файла hdr.h будет определено имя HDR, а при последующих включениях препроцессор обнаружит, что имя HDR уже определено, и перескочит сразу на #endif. Этот прием может оказаться полезным, когда нужно избежать многократного включения одного и того же файла. Если им пользоваться систематически, то в результате каждый заголовочный файл будет сам включать заголовочные файлы, от которых он зависит, освободив от этого занятия пользователя. Вот пример цепочки проверок имени SYSTEM, позволяющей выбрать нужный файл для включения: #if SYSTEM == SYSV #define HDR "sysv.h" #elif SYSTEM == BSD #define HDR "bsd.h" #elif SYSTEM == MSDOS #define HDR "msdos.h" #else #define HDR "default.h" #endif #include HDR Инструкции #ifdef и #ifndef специально предназначены для проверки того, определено или нет заданное в них имя. И следовательно, первый пример, приведенный выше для иллюстрации #if, можно записать и в таком виде: #ifndef HDR #define HDR /* здесь содержимое hdr.h */ #endif |