Kernighan, B. W. and Ritchie, D. M. "The 'C' Programming Language"; Chapter 4

# Функции и структура программ.

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

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

Большинство программистов хорошо знакомы с "библиотечными" функциями для ввода и вывода /getchar, putchar/ и для численных расчетов /sin, cos, sqrt/. В этой главе мы сообщим больше о написании новых функций.

#### Содержание

4.1. Основные сведения.
4.2. Функции, возвращающие нецелые значения.
4.3. Еще об аргументах функций
4.4. Внешние переменные.
4.5. Правила, определяющие область действия.
4.6. Статические переменные.
4.7. Регистровые переменные.
4.8. Блочная структура.
4.9. Инициализация.
4.10. Рекурсия.
4.11. Препроцессор языка 'C'
  4.11.1. Включение файлов
  4.11.2. Макроподстановка

## Основные сведения.

Для начала давайте разработаем и составим программу печати каждой строки ввода, которая содержит определенную комбинацию символов. (Это - специальный случай утилиты grep системы "UNIX"). Например, при поиске комбинации "the" в наборе строк

    now is the time
    for all good
    men to come to the aid
    of their party

в качестве выхода получим

    now is the time
    men to come to the aid
    of their party

Основная схема выполнения задания четко разделяется на три части:

    while (имеется еще строка)
    	if (строка содержит нужную комбинацию)
    		вывод этой строки

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

"Пока имеется еще строка" - это getline, функция, которую мы запрограммировали в главе 1, а "вывод этой строки" - это функция printf, которую уже кто-то подготовил для нас. Это значит, что нам осталось только написать процедуру для определения, содержит ли строка данную комбинацию символов или нет. Мы можем решить эту проблему, позаимствовав разработку из pl/1: функция index(s,t) возвращает позицию, или индекс, строки s, где начинается строка t, и -1, если s не содержит t. В качестве начальной позиции мы используем 0, а не 1, потому что в языке "C" массивы начинаются с позиции нуль. Когда нам в дальнейшем понадобится проверять на совпадение более сложные конструкции, нам придется заменить только функцию index; остальная часть программы останется той же самой.

После того, как мы потратили столько усилий на разработку, написание программы в деталях не представляет затруднений. Ниже приводится целиком вся программа, так что вы можете видеть, как соединяются вместе отдельные части. Комбинация символов, по которой производится поиск, выступает пока в качестве символьной строки в аргументе функции index, что не является самым общим механизмом. Мы скоро вернемся к обсуждению вопроса об инициализации символьных массивов и в главе 5 покажем, как сделать комбинацию символов параметром, которому присваивается значение в ходе выполнения программы. Программа также содержит новый вариант функции getline; вам может оказаться полезным сравнить его с вариантом из главы 1.

    #define maxline 1000
    main()
    {				/* find all lines
    				 * matching a pattern */
    	char            line[maxline];
    	while (getline(line, maxline) > 0)
    		if (index(line, "the") >= 0)
    			printf("%s", line);
    }

    getline(s, lim)			/* get line into s,
    				 * return length */
    char            s[];
    int             lim;
    {
    	int             c, i;
    	i = 0;
            while (--lim > 0 && (c = getchar()) != EOF
                   && c != '\n')
    		s[i++] = c;
    	if (c == '\n')
    		s[i++] = c;
    	s[i] = '\0';
    	return (i);
    }

    index(s, t)			/* return index of t in
    				 * s,-1 if none */
    char            s[], t[];
    {
    	int             i, j, k;
    	for (i = 0; s[i] != '\0'; i++) {
    		for (j = i, k = 0;
    			t[k] != '\0' && s[j] == t[k]; j++; k++);
    		if (t[k] == '\0')
    			return (i);
    	}
    	return (-1);
    }

каждая функция имеет вид

    имя (список аргументов, если они имеются)
    описания аргументов, если они имеются
    {
    	описания и операторы, если они имеются
    }

Как и указывается, некоторые части могут отсутствовать; минимальной функцией является

    dummy () { }

которая не совершает никаких действий.

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

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

Оператор return служит механизмом для возвращения значения из вызванной функции в функцию, которая к ней обратилась. За return может следовать любое выражение:

    return (выражение)

Вызывающая функция может игнорировать возвращаемое значение, если она этого пожелает. Более того, после return может не быть вообще никакого выражения; в этом случае в вызывающую программу не передается никакого значения. Управление также возвращется в вызывающую программу без передачи какого-либо значения и в том случае, когда при выполнении мы "проваливаемся" на конец функции, достигая закрывающейся правой фигурной скобки. Если функция возвращает значение из одного места и не возвращает никакого значения из другого места, это не является незаконным, но может быть признаком каких-то неприятностей. В любом случае "значением" функции, которая не возвращает значения, несомненно будет мусор. Отладочная программа lint проверяет такие ошибки.

Механика компиляции и загрузки "C"-программ, расположенных в нескольких исходных файлах, меняется от системы к системе. В системе "UNIX", например, эту работу выполняет команда 'cc', упомянутая в главе 1. Предположим, что три функции находятся в трех различных файлах с именами main.c, getline.c и index.c . Тогда команда

    cc main.c getline.c index.c

компилирует эти три файла, помещает полученный настраиваемый об'ектный код в файлы main.o, getline.o и index.o и загружает их всех в выполняемый файл, называемый a.out .

Если имеется какая-то ошибка, скажем в main.c, то этот файл можно перекомпилировать отдельно и загрузить вместе с предыдущими об'ектными файлами по команде

    cc main.c getlin.o index.o

Команда 'cc' использует соглашение о наименовании c ".c" и ".o" для того, чтобы отличить исходные файлы от об'ектных.

Упражнение 4-1.
  Составьте программу для функции rindex(s,t), которая возвращает позицию самого правого вхождения t в s и -1, если s не содержит t.

## Функции, возвращающие нецелые значения.

До сих пор ни одна из наших программ не содержала какого-либо описания типа функции. Дело в том, что по умолчанию функция неявно описывается своим появлением в выражении или операторе, как, например, в

    while (getline(line, maxline) > 0)

Если некоторое имя, которое не было описано ранее, появляется в выражении и за ним следует левая круглая скобка, то оно по контексту считается именем некоторой функции. Кроме того, по умолчанию предполагается, что эта функция возвращает значение типа int. Так как в выражениях char преобразуется в int, то нет необходимости описывать функции, возвращающие char. Эти предположения покрывают большинство случаев, включая все приведенные до сих пор примеры.

Но что происходит, если функция должна возвратить значение какого-то другого типа ? Многие численные функции, такие как sqrt, sin и cos возвращают double; другие специальные функции возвращают значения других типов. Чтобы показать, как поступать в этом случае, давайте напишем и используем функцию atof(s), которая преобразует строку s в эквивалентное ей плавающее число двойной точности. Функция atof является расширением atoi, варианты которой мы написали в главах 2 и 3; она обрабатывает необязательно знак и десятичную точку, а также целую и дробную часть, каждая из которых может как присутствовать, так и отсутствовать./эта процедура преобразования ввода не очень высокого качества; иначе она бы заняла больше места, чем нам хотелось бы/.

Во-первых, сама atof должна описывать тип возвращаемого ею значения, поскольку он отличен от int. Так как в выражениях тип float преобразуется в double, то нет никакого смысла в том, чтобы atof возвращала float; мы можем с равным успехом воспользоваться дополнительной точностью, так что мы полагаем, что возвращаемое значение типа double. Имя типа должно стоять перед именем функции, как показывается ниже:

    double
    atof(s)				/* convert string s tо
    				 * double */
    	char            s[];
    {
    	double          val, power;
    	int             i, sign;
    	/* skip white space */
    	for (i = 0;
    	     s[i] == ' ' || s[i] == '\n' || s[i] == '\t';
    	     i++);
    	sign = 1;
    	if (s[i] == '+' || s[i] == '-')	/* sign */
    		sign = (s[i++] == '+') ? 1 : -1;
    	for (val = 0; s[i] >= '0' && s[i] <= '9'; i++)
    		val = 10 * val + s[i] - '0';
    	if (s[i] == '.')
    		i++;
    	for (power = 1; s[i] >= '0' && s[i] <= '9'; i++) {
    		val = 10 * val + s[i] - '0';
    		power *= 10;
    	}
    	return (sign * val / power);
    }

Вторым, но столь же важным, является то, что вызывающая функция должна об'явить о том, что atof возвращает значение, отличное от int типа. Такое об'явление демонстрируется на примере следующего примитивного настольного калькулятора /едва пригодного для подведения баланса в чековой книжке/, который считывает по одному числу на строку, причем это число может иметь знак, и складывает все числа, печатая сумму после каждого ввода.

    #define maxline 100
    main()
    {				/* rudimentary desk
    				 * calkulator */
    	double          sum, atof();
    	char            line[maxline];
    	sum = 0;
    	while (getline(line, maxline) > 0)
    		printf("\t%.2f\n", sum += atof(line));
    }

Описание

    double          sum, atof();

говорит, что sum является переменной типа double, и что atof является функцией, возвращающей значение типа double . Эта мнемоника означает, что значениями как sum, так и atof(...) являются плавающие числа двойной точности.

Если функция atof не будет описана явно в обоих местах, то в "C" предполагается, что она возвращает целое значение, и вы получите бессмысленный ответ. Если сама atof и обращение к ней в main имеют несовместимые типы и находятся в одном и том же файле, то это будет обнаружено компилятором. Но если atof была скомпилирована отдельно /что более вероятно/, то это несоответствие не будет зафиксировано, так что atof будет возвращать значения типа double, с которым main будет обращаться, как с int, что приведет к бессмысленным результатам. /Программа lint вылавливает эту ошибку/.

Имея atof, мы, в принципе, могли бы с ее помощью написать atoi (преобразование строки в int):

    atoi(s)				/* convert string s to
    				 * integer */
    	khar            s[];
    {
    	double          atof();
    	return (atof(s));
    }

Обратите внимание на структуру описаний и оператор return. Значение выражения в

    return (выражение);

всегда преобразуется к типу функции перед выполнением самого возвращения. Поэтому при появлении в операторе return значение функции atof, имеющее тип double, автоматически преобразуется в int, поскольку функция atoi возвращает int. (как обсуждалось в главе 2, преобразование значения с плавающей точкой к типу int осуществляется посредством отбрасывания дробной части).

Упражнение 4-2.
  Расширьте atof таким образом, чтобы она могла работать с числами вида

      123.45e-6

  где за числом с плавающей точкой может следовать 'e' и показатель экспоненты, возможно со знаком.

## Еще об аргументах функций

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

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

Между прочим, несуществует полностью удовлетворительного способа написания переносимой функции с переменным числом аргументов. Дело в том, что нет переносимого способа, с помощью которого вызванная функция могла бы определить, сколько аргументов было фактически передано ей в данном обращении. Таким образом, вы, например, не можете написать действительно переносимую функцию, которая будет вычислять максимум от произвольного числа аргументов, как делают встроенные функции мах в фортране и pl/1.

Обычно со случаем переменного числа аргументов безопасно иметь дело, если вызванная функция не использует аргументов, которые ей на самом деле не были переданы, и если типы согласуются. Самая распространенная в языке "C" функция с переменным числом - printf . Она получает из первого аргумента информацию, позволяющую определить количество остальных аргументов и их типы. Функция printf работает совершенно неправильно, если вызывающая функция передает ей недостаточное количество аргументов, или если их типы не согласуются с типами, указанными в первом аргументе. Эта функция не является переносимой и должна модифицироваться при использовании в различных условиях.

Если же типы аргументов известны, то конец списка аргументов можно отметить, используя какоe-то соглашение; например, считая, что некоторое специальное значение аргумента (часто нуль) является признаком конца аргументов.

## Внешние переменные.

Программа на языке "C" состоит из набора внешних об'ектов, которые являются либо переменными, либо функциями. Термин "внешний" используется главным образом в противопоставление термину "внутренний", которым описываются аргументы и автоматические переменные, определенные внурти функций. Внешние переменные определены вне какой-либо функции и, таким образом, потенциально доступны для многих функций. Сами функции всегда являются внешними, потому что правила языка "C" не разрешают определять одни функции внутри других. По умолчанию внешние переменные являются также и "глобальными", так что все ссылки на такую переменную, использующие одно и то же имя (даже из функций, скомпилированных независимо), будут ссылками на одно и то же. В этом смысле внешние переменные аналогичны переменным common в фортране и external в pl/1. Позднее мы покажем, как определить внешние переменные и функции таким образом, чтобы они были доступны не глобально, а только в пределах одного исходного файла.

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

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

Вторая причина использования внешних переменных связана с инициализацией. В частности, внешние массивы могут быть инициализированы а автоматические нет. Мы рассмотрим вопрос об инициализации в конце этой главы.

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

Давайте продолжим обсуждение этого вопроса на большом примере. Задача будет состоять в написании другой программы для калькулятора, лучшей,чем предыдущая. Здесь допускаются операции +,-,*,/ и знак = (для выдачи ответа).вместо Инфиксного представления калькулятор будет использовать обратную польскую нотацию,поскольку ее несколько легче реализовать. Обратной польской нотации знак следует за операндами; инфиксное выражение типа

    (1 - 2) * (4 + 5) =

записывается в виде

    12-45+*=

Круглые скобки при этом не нужны.

Реализация оказывается весьма простой.каждый Операнд помещается в стек; когда поступает знак операции,нужное число операндов (два для бинарных операций) вынимается,к ним применяется операция и результат направляется обратно в стек.так В приведенном выше примере 1 и 2 помещаются в стек и затем заменяются их разностью, -1.после Этого 4 и 5 вводятся в стек и затем заменяются своей суммой,9.далее Числа -1 и 9 заменяются в стеке на их произведение,равное -9.операция = печатает верхний элемент стека, не удаляя его (так что промежуточные вычисления могут быть проверены).

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

    while ( поступает операция или операнд, а не конец файла )
    	if ( число )
    		поместить его в стек
    	else if ( операция )
    		вынуть операнды из стека
    		выполнить операцию
    		поместить результат в стек
    	else
    		ошибка

Основной вопрос, который еще не был обсужден, заключается в том, где поместить стек, т. е. Какие процедуры смогут обращаться к нему непосредственно. Одна из таких возможностей состоит в помещении стека в main и передачи самого стека и текущей позиции в стеке функциям, работающим со стеком. Но функции main нет необходимости иметь дело с переменными, управляющими стеком; ей естественно рассуждать в терминах помещения чисел в стек и извлечения их оттуда. В силу этого мы решили сделать стек и связанную с ним информацию внешними переменными, доступными функциям push (помещение в стек) и рор (извлечение из стека), но не main.

Перевод этой схемы в программу достаточно прост. Ведущая программа является по существу большим переключателем по типу операции или операнду; это, по-видимому, более характерное применеие переключателя, чем то, которое было продемонстрировано в главе 3.

    #define maxop 20		/* max size of operand,
    				 * operator */
    #define number '0'		/* signal that number
    				 * found */
    #define toobig '9'		/* signal that string is
    				 * too big */
    main()
    {				/* reverse polish desk
    				 * calculator */
    	int             tupe;
    	char            s[maxop];
    	double          op2, atof(), pop(), push();

    	while ((tupe = getop(s, maxop)) != EOF)
    		switch (tupe) {
    		case number:
    			push(atof(s));
    			break;
    		case '+':
    			push(pop() + pop());
    			break;
    		case '*':
    			push(pop() * pop());
    			break;
    		case '-':
    			op2 = pop();
    			push(pop() - op2);
    			break;
    		case '/':
    			op2 = pop();
    			if (op2 != 0.0)
    				push(pop() / op2);
    			else
    				printf("zero divisor popped\n");
    			break;
    		case '=':
    			printf("\t%f\n", push(pop()));
    			break;
    		case 'c':
    			clear();
    			break;
    		case toobig:
    			printf("%.20s ... is too long\n", s);
    			break;
    		}
    }
    #define maxval 100		/* maximum depth of val
    				 * stack */
    int             sp = 0;		/* stack pointer */
    double          val[maxval];	/* value stack */
    double

    push(f)				/* push f onto value
    				 * stack */
    	double          f;
    {
    	if (sp < maxval)
    		return (val[sp++] = f);
    	else {
    		printf("error: stack full\n");
    		clear();
    		return (0);
    	}
    }

    double
    pop()
    {				/* pop top value from
    				 * steack */
    	if (sp > 0)
    		return (val[--sp]);
    	else {
    		printf("error: stack empty\n");
    		clear();
    		return (0);
    	}
    }

    clear()
    {				/* clear stack */
    	sp = 0;
    }

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

Как уже говорилось в главе 1, переменная является внешней, если она определена вне тела какой бы то ни было функции. Поэтому стек и указатель стека, которые должны использоваться функциями push, рор и clear, определены вне этих трех функций. Но сама функция main не ссылается ни к стеку, ни к указателю стека - их участие тщательно замаскировано. В силу этого часть программы, соответствующая операции =, использует конструкцию

    push(pop());

для того, чтобы проанализировать верхний элемент стека, не изменяя его.

Отметим также, что так как операции + и * коммутативны, порядок, в котором об'единяются извлеченные операнды, несущественен, но в случае операций - и / необходимо различать левый и правый операнды.

Упражнение 4-3.
  Приведенная основная схема допускает непосредственное расширение возможностей калькулятора. Включите операцию деления по модулю /%/ и унарный минус. Включите команду "стереть", которая удаляет верхний элемент стека. Введите команды для работы с переменными. /это просто, если имена переменных будут состоять из одной буквы из имеющихся двадцати шести букв/.

## Правила, определяющие область действия.

Функции и внешние переменные, входящие в состав "C"-программы, не обязаны компилироваться одновременно; программа на исходном языке может располагаться в нескольких файлах, и ранее скомпилированные процедуры могут загружаться из библиотек. Два вопроса представляют интерес:

Как следует составлять описания, чтобы переменные правильно воспринимались во время компиляции?

Как следует составлять описания, чтобы обеспечить правильную связь частей программы при загрузке?

### Область действия

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

Область действия внешней переменной простирается от точки, в которой она об'явлена в исходном файле, до конца этого файла. Например, если val, sp, push, рор и clear определены в одном файле в порядке, указанном выше, а именно:

    int             sp = 0;
    double          val[maxval];

    double
    push(f)
    {
    	...
    }

    double
    pop()
    {
    	...
    }

    clear()
    {
    	...
    }

то переменные val и sp можно использовать в push, pop и clear прямо по имени; никакие дополнительные описания не нужны.

С другой стороны, если нужно сослаться на внешнюю переменную до ее определения, или если такая переменная определена в файле, отличном от того, в котором она используется, то необходимо описание extern.

Важно различать описание внешней переменной и ее определение. Описание указывает свойства переменной /ее тип, размер и т.д./; определение же вызывает еще и отведение памяти. Если вне какой бы то ни было функции появляются строчки

    int     sp;
    double  val[maxval];

то они определяют внешние переменные sp и val, вызывают отведение памяти для них и служат в качестве описания для остальной части этого исходного файла. В то же время строчки

    extern int      sp;
    extern double   val[];

описывают в остальной части этого исходного файла переменную sp как int, а val как массив типа double /размер которого указан в другом месте/, но не создают переменных и не отводят им места в памяти.

Во всех файлах, составляющих исходную программу, должно содержаться только одно определение внешней переменной; другие файлы могут содержать описания extern для доступа к ней. /описание extern может иметься и в том файле, где находится определение/. Любая инициализация внешней переменной проводится только в определении. В определении должны указываться размеры массивов, а в описании extern этого можно не делать.

Хотя подобная организация приведенной выше программы и маловероятна, но val и sp могли бы быть определены и инициализированы в одном файле, а функция push, рор и clear определены в другом. В этом случае для связи были бы необходимы следующие определения и описания:

    в файле 1:
    ----------
    int     sp = 0;         /* stack pointer */
    double  val[maxval];    /* value stack */

    в файле 2:
    ----------
    extern int     sp;
    extern double  val[];

    double push(f) {...}
    double pop() {...}
    clear() {...}

Так как описания extern 'в файле 1' находятся выше и вне трех указанных функций, они относятся ко всем ним; одного набора описаний достаточно для всего 'файла 2'.

Для программ большого размера обсуждаемая позже в этой главе возможность включения файлов, #include, позволяет иметь во всей программе только одну копию описаний extern и вставлять ее в каждый исходный файл во время его компиляции.

Обратимся теперь к функции getop, выбирающей из файла ввода следующую операцию или операнд. Основная задача проста: пропустить пробелы, знаки табуляции и новые строки. Если следующий символ отличен от цифры и десятичной точки, то возвратить его. В противном случае собрать строку цифр /она может включать десятичную точку/ и возвратить number как сигнал о том, что выбрано число.

Процедура существенно усложняется, если стремиться правильно обрабатывать ситуацию, когда вводимое число оказывается слишком длинным. Функция getop считывает цифры подряд /возможно с десятичной точкой/ и запоминает их, пока последовательность не прерывается. Если при этом не происходит переполнения, то функция возвращает number и строку цифр. Если же число оказывается слишком длинным, то getop отбрасывает остальную часть строки из файла ввода, так что пользователь может просто перепечатать эту строку с места ошибки; функция возвращает toobig как сигнал о переполнении.

    getop(s, lim)			/* get next oprerator or
    				 * operand */
    char            s[];
    int             lim;
    {
    	int             i, c;
    	while ((c = getch()) == ' ' || c == '\t' || c == '\n');
    	if (c != '.' && (c < '0' || c > '9'))
    		return (c);
    	s[0] = c;
    	for (i = 1; (c = getchar()) >= '0' && c <= '9'; i++)
    		if (i < lim)
    			s[i] = c;
    	if (c == '.') {		/* collect fraction */
    		if (i < lim)
    			s[i] = c;
    		for (i++; (c = getchar()) >= '0' && c <= '9'; i++)
    			if (i < lim)
    				s[i] = c;
    	}
    	if (i < lim) {		/* number is ok */
    		ungetch(c);
    		s[i] = '\0';
    		return (number);

    	} else {		/* it's too big; skip
    				 * rest of line */
    		while (c != '\n' && c != EOF)
    			c = getchar();
    		s[lim - 1] = '\0';
    		return (toobig);
    	}
    }

Что же представляют из себя функции 'getch' и 'ungetch' ? Часто так бывает, что программа, считывающая входные данные, не может определить, что она прочла уже достаточно, пока она не прочтет слишком много. Одним из примеров является выбор символов, составляющих число: пока не появится символ, отличный от цифры, число не закончено. Но при этом программа считывает один лишний символ, символ, для которого она еще не подготовлена.

Эта проблема была бы решена, если бы было бы возможно "прочесть обратно" нежелательный символ. Тогда каждый раз, прочитав лишний символ, программа могла бы поместить его обратно в файл ввода таким образом, что остальная часть программы могла бы вести себя так, словно этот символ никогда не считывался. К счастью, такое неполучение символа легко иммитировать, написав пару действующих совместно функций. Функция getch доставляет следующий символ ввода, подлежащий рассмотрению; функция ungetch помещает символ назад во ввод, так что при следующем обращении к getch он будет возвращен.

То, как эти функции совместно работают, весьма просто. Функция ungetch помещает возвращаемые назад символы в совместно используемый буфер, являющийся символьным массивом. Функция getch читает из этого буфера, если в нем что-либо имеется; если же буфер пуст, она обращается к getchar. При этом также нужна индексирующая переменная, которая будет фиксировать позицию текущего символа в буфере.

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

    #define BUFSIZE 100
    char            buf[BUFSIZE];   /* buffer for ungetch */
    int             bufp = 0;	/* next free position in
    				 * buf */
    getch()
    {				/* get a (possibly pushed
    				 * back) character */
    	return ((bufp > 0) ? buf[--bufp] : getchar());
    }

    ungetch(c)                      /* push character back on
    				 * input */
    	int             c;
    {
            if (bufp > BUFSIZE)
    		printf("ungetch: too many characters\n");
    	else
    		buf[bufp++] = c;
    }

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

Упражнение 4-4.
  Напишите функцию ungets(s), которая будет возвращать во ввод целую строку. Должна ли ungets иметь дело с buf и bufp или она может просто использовать ungetch ?

Упражнение 4-5.
  Предположите, что может возвращаться только один символ. Измените getch и ungetch соответствующим образом.

Упражнение 4-6.
  Наши функции getch и ungetch не обеспечивают обработку возвращенного символа EOF переносимым образом. Решите, каким свойством должны обладать эти функции, если возвращается EOF, и реализуйте ваши выводы.

## Статические переменные.

Статические переменные представляют собой третий класс памяти, в дополнении к автоматическим переменным и extern, с которыми мы уже встречались.

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

Внешние статические переменные определены в остальной части того исходного файла, в котором они описаны, но не в каком-либо другом файле. Таким образом, они дают способ скрывать имена, подобные buf и bufp в комбинации getch-ungetch, которые в силу их совместного использования должны быть внешними, но все же не доступными для пользователей getch и ungetch, чтобы исключалась возможность конфликта. Если эти две функции и две переменные об'еденить в одном файле следующим образом

    static char     buf[BUFSIZE];   /* buffer for ungetch */
    static int      bufp = 0;	/* next free position in
    				 * buf */
    getch()
    {
    	...
    }

    ungetch()
    {
    	...
    }

то никакая другая функция не будет в состоянии обратиться к buf и bufp; фактически, они не будут вступать в конфликт с такими же именами из других файлов той же самой программы.

Статическая память, как внутренняя, так и внешняя, специфицируется словом static, стоящим перед обычным описанием. Переменная является внешней, если она описана вне какой бы то ни было функции, и внутренней, если она описана внутри некоторой функции.

Нормально функции являются внешними об'ектами; их имена известны глобально. Возможно, однако, об'явить функцию как static ; тогда ее имя становится неизвестным вне файла, в котором оно описано.

В языке "C" "static" отражает не только постоянство, но и степень того, что можно назвать "приватностью". Внутренние статические об'екты определены только внутри одной функции; внешние статические об'екты /переменные или функции/ определены только внутри того исходного файла, где они появляются, и их имена не вступают в конфликт с такими же именами переменных и функций из других файлов.

Внешние статические переменные и функции предоставляют способ организовывать данные и работающие с ними внутренние процедуры таким образом, что другие процедуры и данные не могут прийти с ними в конфликт даже по недоразумению. Например, функции getch и ungetch образуют "модуль" для ввода и возвращения символов; buf и bufp должны быть статическими, чтобы они не были доступны извне. Точно так же функции push, рор и clear формируют модуль обработки стека; var и sp тоже должны быть внешними статическими.

## Регистровые переменные.

Четвертый и последний класс памяти называется регистровым. Описание register указывает компилятору, что данная переменная будет часто использоваться. Когда это возможно, переменные, описанные как register, располагаются в машинных регистрах, что может привести к меньшим по размеру и более быстрым программам. Описание register выглядит как

    register int    x;
    register char   c;

и т.д.; часть int может быть опущена. Описание register можно использовать только для автоматических переменных и формальных параметров функций. В этом последнем случае описания выглядят следующим образом:

    f(c, n)
    	register int    c, n;
    {
    	register int    i;
    	...
    }

На практике возникают некоторые ограничения на регистровые переменные, отражающие реальные возможности имеющихся аппаратных средств. В регистры можно поместить только несколько переменных в каждой функции, причем только определенных типов. В случае превышения возможного числа или использования неразрешенных типов слово register игнорируется. Кроме того невозможно извлечь адрес регистровой переменной (этот вопрос обсуждается в главе 5). Эти специфические ограничения варьируются от машины к машине. Так, например, на pdp-11 эффективными являются только первые три описания register в функции, а в качестве типов допускаются int, char или указатель.

## Блочная структура.

Язык "C" не является языком с блочной структурой в смысле pl/1 или алгола; в нем нельзя описывать одни функции внутри других.

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

    if (n > 0) {
    	int             i;	/* declare a new i */
    	for (i = 0; i < n; i++)
    		...
    }

областью действия переменной i является "истинная" ветвь if; это i никак не связано ни с какими другими i в программе.

Блочная структура влияет и на область действия внешних переменных. Если даны описания

    int             x;
    f()
    {
    	double          x;
    	...
    }

то появление х внутри функции f относится к внутренней переменной типа double, а вне f - к внешней целой переменной. Это же справедливо в отношении имен формальных параметров:

    int             x;
    f(x)
    	double          x;
    {
    	...
    }

внутри функции f имя х относится к формальному параметру, а не к внешней переменной.

## Инициализация.

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

Если явная инициализация отсутствует, то внешним и статическим переменным присваивается значение нуль; автоматические и регистровые переменные имеют в этом случае неопределенные значения (мусор).

Простые переменные (не массивы или структуры) можно инициализировать при их описании, добавляя вслед за именем знак равенства и константное выражение:

    int             x = 1;
    char            squote = '`';
    long            day = 60 * 24;  /* minutes in a day */

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

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

    binary(x, v, n)
    	int             x, v[], n;
    {
    	int             low = 0;
    	int             high = n - 1;
    	int             mid;
    	...
    }

вместо

    binary(x, v, n)
    	int             x, v[], n;
    {
    	int             low, high, mid;
    	low = 0;
    	high = n - 1;
    	...
    }

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

Автоматические массивы не могут быть инициализированы. Внешние и статические массивы можно инициализировать, помещая вслед за описанием заключенный в фигурные скобки список начальных значений, разделенных запятыми. Например программа подсчета символов из главы 1, которая начиналась с

    main()
    {				/* count digits, white
    				 * space, others */
    	int             c, i, nwhite, nother;
    	int             ndigit[10];
    	nwhite = nother = 0;
    	for (i = 0; i < 10; i++)
    		ndigit[i] = 0;
    	...
    }

может быть переписана в виде

    int             nwhite = 0;
    int             nother = 0;
    int             ndigit[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    main()
    {				/* count digits, white
    				 * space, others */
    	int             c, i;
    	...
    }

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

Для символьных массивов существует специальный способ инициализации; вместо фигурных скобок и запятых можно использовать строку:

    char            pattern[] = "the";

Это сокращение более длинной, но эквивалентной записи:

    char            pattern[] = {'t', 'h', 'e', '\0'};

Если размер массива любого типа опущен, то компилятор определяет его длину, подсчитывая число начальных значений. В этом конкретном случае размер равен четырем (три символа плюс конечное \0).

## Рекурсия.

В языке "C" функции могут использоваться рекурсивно; это означает, что функция может прямо или косвенно обращаться к себе самой. Традиционным примером является печать числа в виде строки символов. Как мы уже ранее отмечали, цифры генерируются не в том порядке: цифры младших разрядов появляются раньше цифр из старших разрядов, но печататься они должны в обратном порядке.

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

    printd(n)			/* print n in decimal */
    	int             n;
    {
    	char            s[10];
    	int             i;
    	if (n < 0) {
    		putchar('-');
    		n = -n;
    	}
    	i = 0;
    	do {
    		s[i++] = n % 10 + '0';	/* get next char */
    	} while ((n /= 10) > 0);/* discard it */
    	while (--i >= 0)
    		putchar(s[i]);
    }

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

    printd(n)			/* print n in decimal
    				 * (recursive) */
    	int             n;
    {
    	int             i;
    	if (n < 0) {
    		putchar('-');
    		n = -n;
    	}
    	if ((i = n / 10) != 0)
    		printd(i);
    	putchar(n % 10 + '0');
    }

Когда функция вызывает себя рекурсивно, при каждом обращении образуется новый набор всех автоматических переменных, совершенно не зависящий от предыдущего набора. Таким образом, в printd(123) первая функция printd имеет n = 123. Она передает 12 второй printd, а когда та возвращает управление ей, печатает 3. Точно так же вторая printd передает 1 третьей (которая эту единицу печатает), а затем печатает 2.

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

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

Упражнение 4-8.
  Напишите рекурсивный вариант функции reverse(s), которая располагает в обратном порядке строку s.

## Препроцессор языка 'C'

В языке "C" предусмотрены определенные расширения языка с помощью простого макропредпроцессора. Одним из самых распространенных таких расширений, которое мы уже использовали, является конструкция #define; другим расширением является возможность включать во время компиляции содержимое других файлов.

### Включение файлов

Для облегчения работы с наборами конструкций #define и описаний (среди прочих средств) в языке "Си" предусмотрена возможность включения файлов. Любая строка вида

    #include "filename"

заменяется содержимым файла с именем filename. (кавычки обязательны). Часто одна или две строки такого вида появляются в начале каждого исходного файла, для того чтобы включить общие конструкции #define и описания extern для глобальных переменных. Допускается вложенность конструкций #include.

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

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

Определение вида

    #define yes 1

приводит к макроподстановке самого простого вида - замене имени на строку символов. Имена в #define имеют ту же самую форму, что и идентификаторы в "C"; заменяющий текст совершенно произволен. Нормально заменяющим текстом является остальная часть строки; длинное определение можно продолжить, поместив \ в конец продолжаемой строки. "область действия" имени, определенного в #define, простирается от точки определения до конца исходного файла. Имена могут быть переопределены, и определения могут использовать определения, сделанные ранее. Внутри заключенных в кавычки строк подстановки не производятся, так что если, например, yes - определенное имя, то в printf("yes") не будет сделано никакой подстановки.

Так как реализация #define является частью работы макропредпроцессора, а не собственно компилятора, имеется очень мало грамматических ограничений на то, что может быть определено. Так, например, любители алгола могут об'явить

    #define then
    #define begin   {
    #define end     }

и затем написать

    if (i > 0) then
    begin
    	a = 1;
    	b = 2;
    end

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

    #define max(a, b) ((a) > (b) ? (a) : (b))

тогда строка

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

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

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

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

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

    #define square(x) (x)*(x)

при обращении к ней, как square(z+1)). Здесь возникают даже некоторые чисто лексические проблемы: между именем макро и левой круглой скобкой, открывающей список ее аргументов, не должно быть никаких пробелов.

Тем не менее аппарат макросов является весьма ценным. Один практический пример дает описываемая в главе 7 стандартная библиотека ввода-вывода, в которой getchar и putchar определены как макросы (очевидно putchar должна иметь аргумент), что позволяет избежать затрат на обращение к функции при обработке каждого символа.

Другие возможности макропроцессора описаны в приложении А.

Упражнение 4-9.
  Определите макрос swap(x, y), который обменивает значениями два своих аргумента типа int. (в этом случае поможет блочная структура).