Язык С
IF (C == '+' !! C == '-') { /* RECORD
SIGN */
SIGN = (C == '+') ? 1 : -1;
C = GETCH();
}
FOR (*PN = 0; C >= '0' && C <= '9'; C = GETCH())
*PN = 10 * *PN + C - '0';
*PN *= SIGN;
IF (C != EOF)
UNGETCH©;
RETURN©;
}
Выражение *PN используется всюду в GETINT как обычная пере-
менная типа INT. Мы также использовали функции GETCH и
UNGETCH (описанные в главе 4) , так что один лишний символ,
кототрый приходится считывать, может быть помещен обратно во
ввод.
Упражнение 5-1.
Напишите функцию GETFLOAT, аналог GETINT для чисел с
плавающей точкой. Какой тип должна возвращать GETFLOAT в ка-
честве значения функции?
5.3. Указатели и массивы
В языке “C” существует сильная взаимосвязь между указа-
телями и массивами , настолько сильная, что указатели и мас-
сивы действительно следует рассматривать одновременно. Любую
операцию, которую можно выполнить с помощью индексов масси-
ва, можно сделать и с помощью указателей. вариант с указате-
лями обычно оказывается более быстрым, но и несколько более
трудным для непосредственного понимания, по крайней мере для
начинающего. описание
INT A[10]
определяет массив размера 10, т.е. Набор из 10 последова-
тельных объектов, называемых A[0], A[1], ..., A[9]. Запись
A[I] соответствует элементу массива через I позиций от нача-
ла. Если PA - указатель целого, описанный как
103 -
INT *PA
то присваивание
PA = &A[0]
приводит к тому, что PA указывает на нулевой элемент массива
A; это означает, что PA содержит адрес элемента A[0]. Теперь
присваивание
X = *PA
будет копировать содержимое A[0] в X.
Если PA указывает на некоторый определенный элемент мас-
сива A, то по определению PA+1 указывает на следующий эле-
мент, и вообще PA-I указывает на элемент, стоящий на I пози-
ций до элемента, указываемого PA, а PA+I на элемент, стоящий
на I позиций после. Таким образом, если PA указывает на
A[0], то
*(PA+1)
ссылается на содержимое A[1], PA+I - адрес A[I], а *(PA+I) -
содержимое A[I].
Эти замечания справедливы независимо от типа переменных
в массиве A. Суть определения “добавления 1 к указателю”, а
также его распространения на всю арифметику указателей, сос-
тоит в том, что приращение масштабируется размером памяти,
занимаемой объектом, на который указывает указатель. Таким
образом, I в PA+I перед прибавлением умножается на размер
объектов, на которые указывает PA.
Очевидно существует очень тесное соответствие между ин-
дексацией и арифметикой указателей. в действительности ком-
пилятор преобразует ссылку на массив в указатель на начало
массива. В результате этого имя массива является указатель-
ным выражением. Отсюда вытекает несколько весьма полезных
следствий. Так как имя массива является синонимом местополо-
жения его нулевого элемента, то присваивание PA=&A[0] можно
записать как
PA = A
Еще более удивительным, по крайней мере на первый взг-
ляд, кажется тот факт, что ссылку на A[I] можно записать в
виде *(A+I). При анализировании выражения A[I] в языке “C”
оно немедленно преобразуется к виду *(A+I); эти две формы
совершенно эквивалентны. Если применить операцию & к обеим
частям такого соотношения эквивалентности, то мы получим,
что &A[I] и A+I тоже идентичны: A+I - адрес I-го элемента от
начала A. С другой стороны, если PA является указателем, то
в выражениях его можно использовать с индексом: PA[I] иден-
тично *(PA+I). Короче, любое выражение, включающее массивы и
индексы, может быть записано через указатели и смещения и
наоборот, причем даже в одном и том же утверждении.
104 -
Имеется одно различие между именем массива и указателем,
которое необходимо иметь в виду. указатель является перемен-
ной, так что операции PA=A и PA++ имеют смысл. Но имя масси-
ва является константой, а не переменной: конструкции типа
A=PA или A++,или P=&A будут незаконными.
Когда имя массива передается функции, то на самом деле
ей передается местоположение начала этого массива. Внутри
вызванной функции такой аргумент является точно такой же пе-
ременной, как и любая другая, так что имя массива в качестве
аргумента действительно является указателем, т.е. Перемен-
ной, содержащей адрес. мы можем использовать это обстоятель-
ство для написания нового варианта функции STRLEN, вычисляю-
щей длину строки.
STRLEN(S) /* RETURN LENGTH OF STRING S */
CHAR *S;
{
INT N;
FOR (N = 0; *S != ' '; S++)
N++;
RETURN(N);
}
Операция увеличения S совершенно законна, поскольку эта
переменная является указателем; S++ никак не влияет на сим-
вольную строку в обратившейся к STRLEN функции, а только
увеличивает локальную для функции STRLEN копию адреса. Опи-
сания формальных параметров в определении функции в виде
CHAR S[];
CHAR *S;
совершенно эквивалентны; какой вид описания следует предпо-
честь, определяется в значительной степени тем, какие выра-
жения будут использованы при написании функции. Если функции
передается имя массива, то в зависимости от того, что удоб-
нее, можно полагать, что функция оперирует либо с массивом,
либо с указателем, и действовать далее соответвующим обра-
зом. Можно даже использовать оба вида операций, если это ка-
жется уместным и ясным.
Можно передать функции часть массива, если задать в ка-
честве аргумента указатель начала подмассива. Например, если
A - массив, то как
F(&A[2])
как и
F(A+2)
105 -
передают функции F адрес элемента A[2], потому что и &A[2],
и A+2 являются указательными выражениями, ссылающимися на
третий элемент A. внутри функции F описания аргументов могут
присутствовать в виде:
F(ARR)
INT ARR[];
{
...
}
или
F(ARR)
INT *ARR;
{
...
}
Что касается функции F, то тот факт, что ее аргумент в дейс-
твительности ссылается к части большего массива,не имеет для
нее никаких последствий.
5.4. Адресная арифметика
Если P является указателем, то каков бы ни был сорт
объекта, на который он указывает, операция P++ увеличивает P
так, что он указывает на следующий элемент набора этих
объектов, а операция P +=I увеличивает P так, чтобы он ука-
зывал на элемент, отстоящий на I элементов от текущего эле-
мента.эти и аналогичные конструкции представляют собой самые
простые и самые распространенные формы арифметики указателей
или адресной арифметики.
Язык “C” последователен и постоянен в своем подходе к
адресной арифметике; объединение в одно целое указателей,
массивов и адресной арифметики является одной из наиболее
сильных сторон языка. Давайте проиллюстрируем некоторые из
соответствующих возможностей языка на примере элементарной
(но полезной, несмотря на свою простоту) программы распреде-
ления памяти. Имеются две функции: функция ALLOC(N) возвра-
щает в качестве своего значения указатель P, который указы-
вает на первую из N последовательных символьных позиций, ко-
торые могут быть использованы вызывающей функцию ALLOC прог-
раммой для хранения символов; функция FREE(P) освобождает
приобретенную таким образом память, так что ее в дальнейшем
можно снова использовать. программа является “элементарной”,
потому что обращения к FREE должны производиться в порядке,
обратном тому, в котором производились обращения к ALLOC.
Таким образом, управляемая функциями ALLOC и FREE память яв-
ляется стеком или списком, в котором последний вводимый эле-
мент извлекается первым. Стандартная библиотека языка “C”
содержит аналогичные функции, не имеющие таких ограничений,
106 -
и, кроме того, в главе 8 мы приведем улучшенные варианты.
Между тем, однако, для многих приложений нужна только триви-
альная функция ALLOC для распределения небольших участков
памяти неизвестных заранее размеров в непредсказуемые момен-
ты времени.
Простейшая реализация состоит в том, чтобы функция раз-
давала отрезки большого символьного массива, которому мы
присвоили имя ALLOCBUF. Этот массив является собственностью
функций ALLOC и FREE. Так как они работают с указателями, а
не с индексами массива, никакой другой функции не нужно
знать имя этого массива. Он может быть описан как внешний
статический, т.е. Он будет локальным по отношению к исходно-
му файлу, содержащему ALLOC и FREE, и невидимым за его пре-
делами. При практической реализации этот массив может даже
не иметь имени; вместо этого он может быть получен в резуль-
тате запроса к операционной системе на указатель некоторого
неименованного блока памяти.
Другой необходимой информацией является то, какая часть
массива ALLOCBUF уже использована. Мы пользуемся указателем
первого свободного элемента, названным ALLOCP. Когда к функ-
ции ALLOC обращаются за выделением N символов, то она прове-
ряет, достаточно ли осталось для этого места в ALLOCBUF. Ес-
ли достаточно, то ALLOC возвращает текущее значение ALLOCP
(т.е. Начало свободного блока), затем увеличивает его на N,
с тем чтобы он указывал на следующую свободную область. Фун-
кция FREE(P) просто полагает ALLOCP равным P при условии,
что P указывает на позицию внутри ALLOCBUF.
DEFINE NULL 0 /* POINTER VALUE FOR ERROR REPORT */
DEFINE ALLOCSIZE 1000 /* SIZE OF AVAILABLE SPACE */
TATIC CHAR ALLOCBUF[ALLOCSIZE];/* STORAGE FOR ALLOC */
TATIC CHAR ALLOCP = ALLOCBUF; / NEXT FREE POSITION */
HAR ALLOC(N) / RETURN POINTER TO N CHARACTERS */ INT N;
(
IF (ALLOCP + N <= ALLOCBUF + ALLOCSIZE) {
ALLOCP += N;
RETURN(ALLOCP - N); /* OLD P */
} ELSE /* NOT ENOUGH ROOM */
RETURN(NULL);
)
REE(P) /* FREE STORAGE POINTED BY P */
HAR *P;
(
IF (P >= ALLOCBUF && P < ALLOCBUF + ALLOCSIZE)
ALLOCP = P;
)
107 -
Дадим некоторые пояснения. Вообще говоря, указатель мо-
жет быть инициализирован точно так же, как и любая другая
переменная, хотя обычно единственными осмысленными значения-
ми являются NULL (это обсуждается ниже) или выражение, вклю-
чающее адреса ранее определенных данных соответствующего ти-
па. Описание
STATIC CHAR *ALLOCP = ALLOCBUF;
определяет ALLOCP как указатель на символы и инициализирует
его так, чтобы он указывал на ALLOCBUF, т.е. На первую сво-
бодную позицию при начале работы программы. Так как имя мас-
сива является адресом его нулевого элемента, то это можно
было бы записать в виде
STATIC CHAR *ALLOCP = &ALLOCBUF[0];
используйте ту запись, которая вам кажется более естествен-
ной. С помощью проверки
IF (ALLOCP + N <= ALLOCBUF + ALLOCSIZE)
выясняется, осталось ли достаточно места, чтобы удовлетво-
рить запрос на N символов. Если достаточно, то новое значе-
ние ALLOCP не будет указывать дальше, чем на последнюю пози-
цию ALLOCBUF. Если запрос может быть удовлетворен, то ALLOC
возвращает обычный указатель (обратите внимание на описание
самой функции). Если же нет, то ALLOC должна вернуть некото-
рый признак, говорящий о том, что больше места не осталось.
В языке “C” гарантируется, что ни один правильный указатель
данных не может иметь значение нуль, так что возвращение ну-
ля может служить в качестве сигнала о ненормальном событии,
в данном случае об отсутствии места. Мы, однако, вместо нуля
пишем NULL, с тем чтобы более ясно показать, что это специ-
альное значение указателя. Вообще говоря, целые не могут ос-
мысленно присваиваться указателям, а нуль - это особый слу-
чай.
Проверки вида
IF (ALLOCP + N <= ALLOCBUF + ALOOCSIZE)
и
IF (P >= ALLOCBUF && P < ALLOCBUF + ALLOCSIZE)
демонстрируют несколько важных аспектов арифметики указате-
лей. Во-первых , при определенных условиях указатели можно
сравнивать. Если P и Q указывают на элементы одного и того
же массива, то такие отношения, как <, >= и т.д., работают
надлежащим образом. Например,
P < Q
108 -
истинно, если P указывает на более ранний элемент массива,
чем Q. Отношения == и != тоже работают. Любой указатель мож-
но осмысленным образом сравнить на равенство или неравенство
с NULL. Но ни за что нельзя ручаться, если вы используете
сравнения при работе с указателями, указывающими на разные
массивы. Если вам повезет, то на всех машинах вы получите
очевидную бессмыслицу. Если же нет, то ваша программа будет
правильно работать на одной машине и давать непостижимые ре-
зультаты на другой.
Во-вторых, как мы уже видели, указатель и целое можно
складывать и вычитать. Конструкция
P + N
подразумевает N-ый объект за тем, на который P указывает в
настоящий момент. Это справедливо независимо от того, на ка-
кой вид объектов P должен указывать; компилятор сам масшта-
бирует N в соответствии с определяемым из описания P разме-
ром объектов, указываемых с помощью P. например, на PDP-11
масштабирующий множитель равен 1 для CHAR, 2 для INT и
SHORT, 4 для LONG и FLOAT и 8 для DOUBLE.
Вычитание указателей тоже возможно: если P и Q указывают
на элементы одного и того же массива, то P-Q - количество
элементов между P и Q. Этот факт можно использовать для на-
писания еще одного варианта функции
STRLEN:
STRLEN(S) /* RETURN LENGTH OF STRING S */
CHAR *S;
{
CHAR *P = S;
WHILE (*P != ' ')
P++;
RETURN(P-S);
}
При описании указатель P в этой функции инициализирован
посредством строки S, в результате чего он указывает на пер-
вый символ строки. В цикле WHILE по очереди проверяется каж-
дый символ до тех пор, пока не появится символ конца строки
. Так как значение равно нулю, а WHILE только выясняет,
имеет ли выражение в нем значение 0, то в данном случае яв-
ную проверку можно опустить. Такие циклы часто записывают в
виде
WHILE (*P)
P++;
Так как P указывает на символы, то оператор P++ передви-
гает P каждый раз так, чтобы он указывал на следующий сим-
вол. В результате P-S дает число просмотренных символов,
108 -
т.е. Длину строки. Арифметика указателей последовательна:
если бы мы имели дело с переменными типа FLOAT, которые за-
нимают больше памяти, чем переменные типа CHAR, и если бы P
был указателем на FLOAT, то оператор P++ передвинул бы P на
следующее FLOAT. таким образом, мы могли бы написать другой
вариант функции ALLOC, распределяющей память для FLOAT,
вместо CHAR, просто заменив всюду в ALLOC и FREE описатель
CHAR на FLOAT. Все действия с указателями автоматически учи-
тывают размер объектов, на которые они указывают, так что
больше ничего менять не надо.
За исключением упомянутых выше операций (сложение и вы-
читание указателя и целого, вычитание и сравнение двух ука-
зателей), вся остальная арифметика указателей является неза-
конной. Запрещено складывать два указателя, умножать, де-
лить, сдвигать или маскировать их, а также прибавлять к ним
переменные типа FLOAT или DOUBLE.
5.5. Указатели символов и функции
Строчная константа, как, например,
“I AM A STRING”
является массивом символов. Компилятор завершает внутреннее
представление такого массива символом , так что программы
могут находить его конец. Таким образом, длина массива в па-
мяти оказывается на единицу больше числа символов между
двойными кавычками.
По-видимому чаще всего строчные константы появляются в
качестве аргументов функций, как, например, в
PRINTF (“HELLO, WORLDN”);
когда символьная строка, подобная этой, появляется в прог-
рамме, то доступ к ней осуществляется с помощью указателя
символов; функция PRINTF фактически получает указатель сим-
вольного массива.
Конечно, символьные массивы не обязаны быть только аргу-
ментами функций. Если описать MESSAGE как
CHAR *MESSAGE;
то в результате оператора
MESSAGE = “NOW IS THE TIME”;
переменная MESSAGE станет указателем на фактический массив
символов. Это не копирование строки; здесь участвуют только
указатели. в языке “C” не предусмотрены какие-либо операции
для обработки всей строки символов как целого.
Мы проиллюстрируем другие аспекты указателей и массивов,
разбирая две полезные функции из стандартной библиотеки вво-
да-вывода, которая будет рассмотрена в главе 7.
109 -
Первая функция - это STRCPY(S,T), которая копирует стро-
ку т в строку S. Аргументы написаны именно в этом порядке по
аналогии с операцией присваивания, когда для того, чтобы
присвоить T к S обычно пишут
S = T
сначала приведем версию с массивами:
STRCPY(S, T) /* COPY T TO S */
CHAR S[], T[];
{
INT I;
I = 0;
WHILE ((S[I] = T[I]) != ' ')
I++;
}
Для сопоставления ниже дается вариант STRCPY с указате-
лями.
STRCPY(S, T) /* COPY T TO S; POINTER VERSION 1 */ CHAR *S, *T;
{
WHILE ((*S = *T) != ' ') {
S++;
T++;
}
}
Так как аргументы передаются по значению, функция STRCPY
может использовать S и T так, как она пожелает. Здесь они с
удобством полагаются указателями, которые передвигаются
вдоль массивов, по одному символу за шаг, пока не будет ско-
пирован в S завершающий в T символ .
На практике функция STRCPY была бы записана не так, как
мы показали выше. Вот вторая возможность:
STRCPY(S, T) /* COPY T TO S; POINTER VERSION 2 */ CHAR *S, *T;
{
WHILE ((*S++ = *T++) != ' ')
;
}
Здесь увеличение S и T внесено в проверочную часть. Зна-
чением *T++ является символ, на который указывал T до увели-
чения; постфиксная операция ++ не изменяет T, пока этот сим-
вол не будет извлечен. Точно так же этот символ помещается в
старую позицию S, до того как S будет увеличено. Конечный
результат заключается в том, что все символы, включая завер-
шающий , копируются из T в S.
110 -
И как последнее сокращение мы опять отметим, что сравне-
ние с является излишним, так что функцию можно записать в
виде
STRCPY(S, T) /* COPY T TO S; POINTER VERSION 3 */
CHAR *S, *T;
{
WHILE (*S++ = *T++)
;
}
хотя с первого взгляда эта запись может показаться загадоч-
ной, она дает значительное удобство. Этой идиомой следует
овладеть уже хотя бы потому, что вы с ней будете часто вст-
речаться в “C”-программах.
Вторая функция - STRCMP(S, T), которая сравнивает сим-
вольные строки S и т, возвращая отрицательное, нулевое или
положительное значение в соответствии с тем, меньше, равно
или больше лексикографически S, чем T. Возвращаемое значение
получается в результате вычитания символов из первой пози-
ции, в которой S и T не совпадают.
STRCMP(S, T) /* RETURN <0 IF S
CHAR S[], T[];
{
INT I;
I = 0;
WHILE (S[I] == T[I])
IF (S[I++] == ' ')
RETURN(0);
RETURN(S[I]-T[I]);
}
Вот версия STRCMP с указателями:
STRCMP(S, T) /* RETURN <0 IF S
{
FOR ( ; *S == *T; S++, T++)
IF (*S == ' ')
RETURN(0);
RETURN(*S-*T);
}
так как ++ и—могут быть как постфиксными, так и
префиксными операциями, встречаются другие комбинации * и
++ и --, хотя и менее часто.
Например
*++P
111 -
увеличивает P до извлечения символа, на который указывает
P, а
*--P
сначала уменьшает P.
Упражнение 5-2.
Напишите вариант с указателями функции STRCAT из главы
2: STRCAT(S, T) копирует строку T в конец S.
Упражнение 5-3.
Напишите макрос для STRCPY.
Упражнение 5-4.
Перепишите подходящие программы из предыдущих глав и уп-
ражнений, используя указатели вместо индексации массивов.
Хорошие возможности для этого предоставляют функции GETLINE
/главы 1 и 4/, ATOI, ITOA и их варианты /главы 2, 3 и 4/,
REVERSE /глава 3/, INDEX и GETOP /глава 4/.
5.6. Указатели - не целые.
Вы, возможно, обратили внимание в предыдущих “с”-прог-
раммах на довольно непринужденное отношение к копированию
указателей. В общем это верно, что на большинстве машин ука-
затель можно присвоить целому и передать его обратно, не из-
менив его; при этом не происходит никакого масштабирования
или преобразования и ни один бит не теряется. к сожалению,
это ведет к вольному обращению с функциями, возвращающими
указатели, которые затем просто передаются другим функциям,
необходимые описания указателей часто опускаются. Рассмот-
рим, например, функцию STRSAVE(S), которая копирует строку S
в некоторое место для хранения, выделяемое посредством обра-
щения к функции ALLOC, и возвращает указатель на это место.
Правильно она должна быть записана так:
CHAR STRSAVE(S) / SAVE STRING S SOMEWHERE */ CHAR *S;
{
CHAR *P, *ALLOC();
IF ((P = ALLOC(STRLEN(S)+1)) != NULL)
STRCPY(P, S);
RETURN(P);
}
на практике существует сильное стремление опускать описания:
112 -
STRSAVE(S) / SAVE STRING S SOMEWHERE */
{
CHAR *P;
IF ((P = ALLOC(STRLEN(S)+1)) != NULL)
STRCPY(P, S);
RETURN(P);
}
Эта программа будет правильно работать на многих маши-
нах, потому что по умолчанию функции и аргументы имеют тип
INT, а указатель и целое обычно можно безопасно пересылать
туда и обратно. Однако такой стиль программирования в своем
существе является рискованным, поскольку зависит от деталей
реализации и архитектуры машины и может привести к непра-
вильным результатам на конкретном используемом вами компиля-
торе. Разумнее всюду использовать полные описания. (Отладоч-
ная программа LINT предупредит о таких конструкциях, если
они по неосторожности все же появятся).
5.7. Многомерные массивы.
В языке “C” предусмотрены прямоугольные многомерные мас-
сивы, хотя на практике существует тенденция к их значительно
более редкому использованию по сравнению с массивами указа-
телей. В этом разделе мы рассмотрим некоторые их свойства.
Рассмотрим задачу преобразования дня месяца в день года
и наоборот. Например, 1-ое марта является 60-м днем невисо-
косного года и 61-м днем високосного года. Давайте введем
две функции для выполнения этих преобразований: DAY_OF_YEAR
преобразует месяц и день в день года, а MONTH_DAY преобразу-
ет день года в месяц и день. Так как эта последняя функция
возвращает два значения, то аргументы месяца и дня должны
быть указателями:
MONTH_DAY(1977, 60, &M, &D)
Полагает M равным 3 и D равным 1 (1-ое марта).
Обе эти функции нуждаются в одной и той же информацион-
ной таблице, указывающей число дней в каждом месяце. Так как
число дней в месяце в високосном и в невисокосном году отли-
чается, то проще представить их в виде двух строк двумерного
массива, чем пытаться прослеживать во время вычислений, что
именно происходит в феврале. Вот этот массив и выполняющие
эти преобразования функции:
STATIC INT DAY_TAB[2][13] =