сное выражение типа
(1-2)*(4+5)=
записывается в виде
12-45+*=
круглые скобки при этом не нужны
Реализация оказывается весьма простой.каждый операнд по-
мещается в стек; когда поступает знак операции,нужное число
операндов (два для бинарных операций) вынимается,к ним при-
меняется операция и результат направляется обратно в
стек.так в приведенном выше примере 1 и 2 помещаются в стек
и затем заменяются их разностью, -1.после этого 4 и 5 вво-
дятся в стек и затем заменяются своей суммой,9.далее числа
-1 и 9 заменяются в стеке на их произведение,равное -9.опе-
рация = печатает верхний элемент стека, не удаляя его (так
что промежуточные вычисления могут быть проверены).
Сами операции помещения чисел в стек и их извлечения
очень просты,но, в связи с включением в настоящую программу
обнаружения ошибок и восстановления,они оказываются доста-
точно длинными. Поэтому лучше оформить их в виде отдельных
функций,чем повторять соответствующий текст повсюду в прог-
рамме. Кроме того, нужна отдельная функция для выборки из
ввода следующей операции или операнда. Таким образом, струк-
тура программы имеет вид:
WHILE( поступает операция или операнд, а не конец
IF ( число )
поместить его в стек
еLSE IF ( операция )
вынуть операнды из стека
выполнить операцию
поместить результат в стек
ELSE
ошибка
Основной вопрос, который еще не был обсужден, заключает-
ся в том,где поместить стек, т. Е. Какие процедуры смогут
обращаться к нему непосредственно. Одна из таких возможнос-
тей состоит в помещении стека в MAIN и передачи самого стека
и текущей позиции в стеке функциям, работающим со стеком. Но
функции MAIN нет необходимости иметь дело с переменными, уп-
равляющими стеком; ей естественно рассуждать в терминах по-
мещения чисел в стек и извлечения их оттуда. В силу этого мы
решили сделать стек и связанную с ним информацию внешними
переменными , доступными функциям PUSH (помещение в стек) и
POP (извлечение из стека), но не MAIN.
Перевод этой схемы в программу достаточно прост. Ведущая
программа является по существу большим переключателем по ти-
пу операции или операнду; это, по-видимому, более характер-
ное применеие переключателя, чем то, которое было продемонс-
трировано в главе 3.
#DEFINE MAXOP 20 /* MAX SIZE OF OPERAND, OPERАTOR *
#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;
/)
Команда C очищает стек с помощью функции CLEAR, которая
также используется в случае ошибки функциями PUSH и POP. к
функции GETOP мы очень скоро вернемся.
Как уже говорилось в главе 1, переменная является внеш-
ней, если она определена вне тела какой бы то ни было функ-
ции. Поэтому стек и указатель стека, которые должны исполь-
зоваться функциями PUSH, POP и CLEAR, определены вне этих
трех функций. Но сама функция MAIN не ссылается ни к стеку,
ни к указателю стека - их участие тщательно замаскировано. В
силу этого часть программы, соответствующая операции = , ис-
пользует конструкцию
PUSH(POP());
для того, чтобы проанализировать верхний элемент стека, не
изменяя его.
Отметим также, что так как операции + и * коммутативны,
порядок, в котором объединяются извлеченные операнды, несу-
щественен, но в случае операций - и / необходимо различать
левый и правый операнды.
Упражнение 4-3
---------------
Приведенная основная схема допускает непосредственное
расширение возможностей калькулятора. Включите операцию де-
ления по модулю /%/ и унарный минус. Включите команду "сте-
реть", которая удаляет верхний элемент стека. Введите коман-
ды для работы с переменными. /Это просто, если имена пере-
менных будут состоять из одной буквы из имеющихся двадцати
шести букв/.
Функции и внешние переменные, входящие в состав
"C"-программы, не обязаны компилироваться одновременно;
программа на исходном языке может располагаться в нескольких
файлах, и ранее скомпилированные процедуры могут загружаться
из библиотек. Два вопроса представляют интерес:
Как следует составлять описания, чтобы переменные пра-
вильно воспринимались во время компиляции ?
Как следует составлять описания, чтобы обеспечить пра-
вильную связь частей программы при загрузке ?
Областью действия имени является та часть программы, в
которой это имя определено. Для автоматической переменной,
описанной в начале функции, областью действия является та
функция, в которой описано имя этой переменной, а переменные
из разных функций, имеющие одинаковое имя, считаются не от-
носящимися друг к другу. Это же справедливо и для аргументов
функций.
Область действия внешней переменной простирается от точ-
ки, в которой она объявлена в исходном файле, до конца этого
файла. Например, если VAL, SP, PUSH, POP и 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, POP и 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,
POP и 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;
...
}
То появление X внутри функции F относится к внутренней пере-
менной типа DOUBLE, а вне F - к внешней целой переменной.
это же справедливо в отношении имен формальных параметров:
INT X;
F(X)
DOUBLE X;
{
...
}
Внутри функции F имя X относится к формальному параметру, а
не к внешней переменной.
Мы до сих пор уже много раз упоминали инициализацию, но
всегда мимоходом , среди других вопросов. Теперь, после того
как мы обсудили различные классы памяти, мы в этом разделе
просуммируем некоторые правила, относящиеся к инициализации.
Если явная инициализация отсутствует, то внешним и ста-
тическим переменным присваивается значение нуль; автомати-
ческие и регистровые переменные имеют в этом случае неопре-
деленные значения (мусор).
Простые переменные (не массивы или структуры) можно ини-
циализировать при их описании, добавляя вслед за именем знак
равенства и константное выражение:
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.
Рекурсия обычно не дает никакой экономиии памяти, пос-
кольку приходится где-то создавать стек для обрабатываемых
значений. Не приводит она и к созданию более быстрых прог-
рамм. Но рекурсивные программы более компактны, и они зачас-
тую становятся более легкими для понимания и написания. Ре-
курсия особенно удобна при работе с рекурсивно определяемыми
структурами данных, например, с деревьями; хороший пример
будет приведен в главе 6.
Упражнение 4-7
--------------
Приспособьте идеи, использованные в PRINTD для рекурсив-
ного написания ITOA; т.е. Преобразуйте целое в строку с по-
мощью рекурсивной процедуры.
Упражнение 4-8
--------------
Напишите рекурсивный вариант функции REVERSE(S), которая
располагает в обратном порядке строку S.
В языке "с" предусмотрены определенные расширения языка
с помощью простого макропредпроцессора. одним из самых расп-
ространенных таких расширений, которое мы уже использовали,
является конструкция #DEFINE; другим расширением является
возможность включать во время компиляции содержимое других
файлов.
Для облегчения работы с наборами конструкций #DEFINE и
описаний (среди прочих средств) в языке "с" предусмотрена
возможность включения файлов. Любая строка вида
#INCLUDE "FILENAME"
заменяется содержимым файла с именем FILENAME. (Кавычки обя-
зательны). Часто одна или две строки такого вида появляются
в начале каждого исходного файла, для того чтобы включить
общие конструкции #DEFINE и описания EXTERN для глобальных
переменных. Допускается вложенность конструкций #INCLUDE.
Конструкция #INCLUDE является предпочтительным способом
связи описаний в больших программах. Этот способ гарантиру-
ет, что все исходные файлы будут снабжены одинаковыми опре-
делениями и описаниями переменных, и, следовательно, исклю-
чает особенно неприятный сорт ошибок. Естественно, когда ка-
кой-TO включаемый файл изменяется, все зависящие от него
файлы должны быть перекомпилированы.
Определение вида
#DEFINE TES 1
приводит к макроподстановке самого простого вида - замене
имени на строку символов. Имена в #DEFINE имеют ту же самую
форму, что и идентификаторы в "с"; заменяющий текст совер-
шенно произволен. Нормально заменяющим текстом является ос-
тальная часть строки; длинное определение можно продолжить,
поместив \ в конец продолжаемой строки. "Область действия"
имени, определенного в #DEFINE, простирается от точки опре-
деления до конца исходного файла. имена могут быть переопре-
делены, и определения могут использовать определения, сде-
ланные ранее. Внутри заключенных в кавычки строк подстановки
не производятся, так что если, например, YES - определенное
имя, то в PRINTF("YES") не будет сделано никакой подстанов-
ки.
Так как реализация #DEFINE является частью работы
маKропредпроцессора, а не собственно компилятора, имеется
очень мало грамматических ограничений на то, что может быть
определено. Так, например, любители алгола могут объявить
#DEFINE THEN
#DEFINE BEGIN {
#DEFINE END ;}
и затем написать
IF (I > 0) THEN
BEGIN
A = 1;
B = 2
END
Имеется также возможность определения макроса с аргумен-
тами, так что заменяющий текст будет зависеть от вида обра-
щения к макросу. Определим, например, макрос с именем MAX
следующим образом:
#DEFINE MAX(A, B) ((A) > (B) ? (A) : (B))
когда строка
X = MAX(P+Q, R+S);
будет заменена строкой
X = ((P+Q) > (R+S) ? (P+Q) : (R+S));
Такая возможность обеспечивает "функцию максимума", которая
расширяется в последовательный код, а не в обращение к функ-
ции. При правильном обращении с аргументами такой макрос бу-
дет работать с любыми типами данных; здесь нет необходимости
в различных видах MAX для данных разных типов, как это было
бы с функциями.
Конечно, если вы тщательно рассмотрите приведенное выше
(1-2)*(4+5)=
записывается в виде
12-45+*=
круглые скобки при этом не нужны
Реализация оказывается весьма простой.каждый операнд по-
мещается в стек; когда поступает знак операции,нужное число
операндов (два для бинарных операций) вынимается,к ним при-
меняется операция и результат направляется обратно в
стек.так в приведенном выше примере 1 и 2 помещаются в стек
и затем заменяются их разностью, -1.после этого 4 и 5 вво-
дятся в стек и затем заменяются своей суммой,9.далее числа
-1 и 9 заменяются в стеке на их произведение,равное -9.опе-
рация = печатает верхний элемент стека, не удаляя его (так
что промежуточные вычисления могут быть проверены).
Сами операции помещения чисел в стек и их извлечения
очень просты,но, в связи с включением в настоящую программу
обнаружения ошибок и восстановления,они оказываются доста-
точно длинными. Поэтому лучше оформить их в виде отдельных
функций,чем повторять соответствующий текст повсюду в прог-
рамме. Кроме того, нужна отдельная функция для выборки из
ввода следующей операции или операнда. Таким образом, струк-
тура программы имеет вид:
WHILE( поступает операция или операнд, а не конец
IF ( число )
поместить его в стек
еLSE IF ( операция )
вынуть операнды из стека
выполнить операцию
поместить результат в стек
ELSE
ошибка
Основной вопрос, который еще не был обсужден, заключает-
ся в том,где поместить стек, т. Е. Какие процедуры смогут
обращаться к нему непосредственно. Одна из таких возможнос-
тей состоит в помещении стека в MAIN и передачи самого стека
и текущей позиции в стеке функциям, работающим со стеком. Но
функции MAIN нет необходимости иметь дело с переменными, уп-
равляющими стеком; ей естественно рассуждать в терминах по-
мещения чисел в стек и извлечения их оттуда. В силу этого мы
решили сделать стек и связанную с ним информацию внешними
переменными , доступными функциям PUSH (помещение в стек) и
POP (извлечение из стека), но не MAIN.
Перевод этой схемы в программу достаточно прост. Ведущая
программа является по существу большим переключателем по ти-
пу операции или операнду; это, по-видимому, более характер-
ное применеие переключателя, чем то, которое было продемонс-
трировано в главе 3.
#DEFINE MAXOP 20 /* MAX SIZE OF OPERAND, OPERАTOR *
#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;
/)
Команда C очищает стек с помощью функции CLEAR, которая
также используется в случае ошибки функциями PUSH и POP. к
функции GETOP мы очень скоро вернемся.
Как уже говорилось в главе 1, переменная является внеш-
ней, если она определена вне тела какой бы то ни было функ-
ции. Поэтому стек и указатель стека, которые должны исполь-
зоваться функциями PUSH, POP и CLEAR, определены вне этих
трех функций. Но сама функция MAIN не ссылается ни к стеку,
ни к указателю стека - их участие тщательно замаскировано. В
силу этого часть программы, соответствующая операции = , ис-
пользует конструкцию
PUSH(POP());
для того, чтобы проанализировать верхний элемент стека, не
изменяя его.
Отметим также, что так как операции + и * коммутативны,
порядок, в котором объединяются извлеченные операнды, несу-
щественен, но в случае операций - и / необходимо различать
левый и правый операнды.
Упражнение 4-3
---------------
Приведенная основная схема допускает непосредственное
расширение возможностей калькулятора. Включите операцию де-
ления по модулю /%/ и унарный минус. Включите команду "сте-
реть", которая удаляет верхний элемент стека. Введите коман-
ды для работы с переменными. /Это просто, если имена пере-
менных будут состоять из одной буквы из имеющихся двадцати
шести букв/.
Функции и внешние переменные, входящие в состав
"C"-программы, не обязаны компилироваться одновременно;
программа на исходном языке может располагаться в нескольких
файлах, и ранее скомпилированные процедуры могут загружаться
из библиотек. Два вопроса представляют интерес:
Как следует составлять описания, чтобы переменные пра-
вильно воспринимались во время компиляции ?
Как следует составлять описания, чтобы обеспечить пра-
вильную связь частей программы при загрузке ?
Областью действия имени является та часть программы, в
которой это имя определено. Для автоматической переменной,
описанной в начале функции, областью действия является та
функция, в которой описано имя этой переменной, а переменные
из разных функций, имеющие одинаковое имя, считаются не от-
носящимися друг к другу. Это же справедливо и для аргументов
функций.
Область действия внешней переменной простирается от точ-
ки, в которой она объявлена в исходном файле, до конца этого
файла. Например, если VAL, SP, PUSH, POP и 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, POP и 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,
POP и 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;
...
}
То появление X внутри функции F относится к внутренней пере-
менной типа DOUBLE, а вне F - к внешней целой переменной.
это же справедливо в отношении имен формальных параметров:
INT X;
F(X)
DOUBLE X;
{
...
}
Внутри функции F имя X относится к формальному параметру, а
не к внешней переменной.
Мы до сих пор уже много раз упоминали инициализацию, но
всегда мимоходом , среди других вопросов. Теперь, после того
как мы обсудили различные классы памяти, мы в этом разделе
просуммируем некоторые правила, относящиеся к инициализации.
Если явная инициализация отсутствует, то внешним и ста-
тическим переменным присваивается значение нуль; автомати-
ческие и регистровые переменные имеют в этом случае неопре-
деленные значения (мусор).
Простые переменные (не массивы или структуры) можно ини-
циализировать при их описании, добавляя вслед за именем знак
равенства и константное выражение:
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.
Рекурсия обычно не дает никакой экономиии памяти, пос-
кольку приходится где-то создавать стек для обрабатываемых
значений. Не приводит она и к созданию более быстрых прог-
рамм. Но рекурсивные программы более компактны, и они зачас-
тую становятся более легкими для понимания и написания. Ре-
курсия особенно удобна при работе с рекурсивно определяемыми
структурами данных, например, с деревьями; хороший пример
будет приведен в главе 6.
Упражнение 4-7
--------------
Приспособьте идеи, использованные в PRINTD для рекурсив-
ного написания ITOA; т.е. Преобразуйте целое в строку с по-
мощью рекурсивной процедуры.
Упражнение 4-8
--------------
Напишите рекурсивный вариант функции REVERSE(S), которая
располагает в обратном порядке строку S.
В языке "с" предусмотрены определенные расширения языка
с помощью простого макропредпроцессора. одним из самых расп-
ространенных таких расширений, которое мы уже использовали,
является конструкция #DEFINE; другим расширением является
возможность включать во время компиляции содержимое других
файлов.
Для облегчения работы с наборами конструкций #DEFINE и
описаний (среди прочих средств) в языке "с" предусмотрена
возможность включения файлов. Любая строка вида
#INCLUDE "FILENAME"
заменяется содержимым файла с именем FILENAME. (Кавычки обя-
зательны). Часто одна или две строки такого вида появляются
в начале каждого исходного файла, для того чтобы включить
общие конструкции #DEFINE и описания EXTERN для глобальных
переменных. Допускается вложенность конструкций #INCLUDE.
Конструкция #INCLUDE является предпочтительным способом
связи описаний в больших программах. Этот способ гарантиру-
ет, что все исходные файлы будут снабжены одинаковыми опре-
делениями и описаниями переменных, и, следовательно, исклю-
чает особенно неприятный сорт ошибок. Естественно, когда ка-
кой-TO включаемый файл изменяется, все зависящие от него
файлы должны быть перекомпилированы.
Определение вида
#DEFINE TES 1
приводит к макроподстановке самого простого вида - замене
имени на строку символов. Имена в #DEFINE имеют ту же самую
форму, что и идентификаторы в "с"; заменяющий текст совер-
шенно произволен. Нормально заменяющим текстом является ос-
тальная часть строки; длинное определение можно продолжить,
поместив \ в конец продолжаемой строки. "Область действия"
имени, определенного в #DEFINE, простирается от точки опре-
деления до конца исходного файла. имена могут быть переопре-
делены, и определения могут использовать определения, сде-
ланные ранее. Внутри заключенных в кавычки строк подстановки
не производятся, так что если, например, YES - определенное
имя, то в PRINTF("YES") не будет сделано никакой подстанов-
ки.
Так как реализация #DEFINE является частью работы
маKропредпроцессора, а не собственно компилятора, имеется
очень мало грамматических ограничений на то, что может быть
определено. Так, например, любители алгола могут объявить
#DEFINE THEN
#DEFINE BEGIN {
#DEFINE END ;}
и затем написать
IF (I > 0) THEN
BEGIN
A = 1;
B = 2
END
Имеется также возможность определения макроса с аргумен-
тами, так что заменяющий текст будет зависеть от вида обра-
щения к макросу. Определим, например, макрос с именем MAX
следующим образом:
#DEFINE MAX(A, B) ((A) > (B) ? (A) : (B))
когда строка
X = MAX(P+Q, R+S);
будет заменена строкой
X = ((P+Q) > (R+S) ? (P+Q) : (R+S));
Такая возможность обеспечивает "функцию максимума", которая
расширяется в последовательный код, а не в обращение к функ-
ции. При правильном обращении с аргументами такой макрос бу-
дет работать с любыми типами данных; здесь нет необходимости
в различных видах MAX для данных разных типов, как это было
бы с функциями.
Конечно, если вы тщательно рассмотрите приведенное выше