Язык С
Эта проблема была бы решена, если бы было бы возможно “прочесть обратно” нежелательный символ. Тогда каждый раз, прочитав лишний символ, программа могла бы поместить его обратно в файл ввода таким образом, что остальная часть программы могла бы вести себя так, словно этот символ никогда не считывался. к счастью, такое неполучение символа легко иммитировать, написав пару действующих совместно функций. Функция 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© /* PUSH CHARACTER BACK ON INPUT */ INT C;
{ IF (BUFP > BUFSIZE) PRINTF(“UNGETCH: TOO MANY CHARACTERSN”);
ELSE BUF [BUFP++] = C;
}
Мы использовали для хранения возвращаемых символов массив, а не отдельный символ, потому что такая общность может пригодиться в дальнейшем.
Упражнение 4-4.
Напишите функцию UNGETS(S) , которая будет возвращать во ввод целую строку. Должна ли UNGETS иметь дело с BUF и BUFP или она может просто использовать UNGETCH ? Упражнение 4-5.
Предположите, что может возвращаться только один символ. Измените GETCH и UNGETCH соответствующим образом.
Упражнение 4-6.
Наши функции GETCH и UNGETCH не обеспечивают обработку возвращенного символа EOF переносимым образом. Решите, каким свойством должны обладать эти функции, если возвращается EOF, и реализуйте ваши выводы.
4.6. Статические переменные.
Статические переменные представляют собой третий класс памяти, в дополнении к автоматическим переменным и 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, POP и CLEAR формируют модуль обработки стека; VAR и SP тоже должны быть внешними статическими.
4.7. Регистровые переменные.
Четвертый и последний класс памяти называется регистровым. Описание 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 или указатель.
4.8. Блочная структура.
Язык “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;
...
}
То появление X внутри функции F относится к внутренней переменной типа DOUBLE, а вне F - к внешней целой переменной.
это же справедливо в отношении имен формальных параметров:
INT X;
F(X) DOUBLE X;
{
...
}
Внутри функции F имя X относится к формальному параметру, а не к внешней переменной.
4.9. Инициализация.
Мы до сих пор уже много раз упоминали инициализацию, но всегда мимоходом , среди других вопросов. Теперь, после того как мы обсудили различные классы памяти, мы в этом разделе просуммируем некоторые правила, относящиеся к инициализации.
Если явная инициализация отсутствует, то внешним и статическим переменным присваивается значение нуль; автоматические и регистровые переменные имеют в этом случае неопределенные значения (мусор).
Простые переменные (не массивы или структуры) можно инициализировать при их описании, добавляя вслед за именем знак равенства и константное выражение: 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', ' ' };
Если размер массива любого типа опущен, то компилятор определяет его длину, подсчитывая число начальных значений. В этом конкретном случае размер равен четырем (три символа плюс конечное ).
4.10. Рекурсия.
В языке “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.
Рекурсия обычно не дает никакой экономиии памяти, поскольку приходится где-то создавать стек для обрабатываемых значений. Не приводит она и к созданию более быстрых программ. Но рекурсивные программы более компактны, и они зачастую становятся более легкими для понимания и написания. Рекурсия особенно удобна при работе с рекурсивно определяемыми структурами данных, например, с деревьями; хороший пример будет приведен в главе 6.
Упражнение 4-7.
Приспособьте идеи, использованные в PRINTD для рекурсивного написания ITOA; т.е. Преобразуйте целое в строку с помощью рекурсивной процедуры.
Упражнение 4-8.
Напишите рекурсивный вариант функции REVERSE(S), которая располагает в обратном порядке строку S.
4.11. Препроцессор языка “C”.
В языке “с” предусмотрены определенные расширения языка с помощью простого макропредпроцессора. одним из самых распространенных таких расширений, которое мы уже использовали, является конструкция #DEFINE; другим расширением является возможность включать во время компиляции содержимое других файлов.
4.11.1. Включение файлов
Для облегчения работы с наборами конструкций #DEFINE и описаний (среди прочих средств) в языке “с” предусмотрена возможность включения файлов. Любая строка вида
#INCLUDE “FILENAME” заменяется содержимым файла с именем FILENAME. (Кавычки обязательны). Часто