Часть 5
- 98 -
5.Указатели и массивы
Указатель - это переменная, содержащая адрес другой пе-
ременной. указатели очень широко используются в языке "C".
Это происходит отчасти потому, что иногда они дают единст-
венную возможность выразить нужное действие, а отчасти пото-
му, что они обычно ведут к более компактным и эффективным
программам, чем те, которые могут быть получены другими спо-
собами.
Указатели обычно смешивают в одну кучу с операторами
GOTO, характеризуя их как чудесный способ написания прог-
рамм, которые невозможно понять. Это безусловно спрAведливо,
если указатели используются беззаботно; очень просто ввести
указатели, которые указывают на что-то совершенно неожидан-
ное. Однако, при определенной дисциплине, использование ука-
зателей помогает достичь ясности и простоты. Именно этот ас-
пект мы попытаемся здесь проиллюстрировать.
5.1. Указатели и адреса
Так как указатель содержит адрес объекта, это дает воз-
можность "косвенного" доступа к этому объекту через указа-
тель. Предположим, что х - переменная, например, типа INT, а
рх - указатель, созданный неким еще не указанным способом.
Унарная операция & выдает адрес объекта, так что оператор
рх = &х;
присваивает адрес х переменной рх; говорят, что рх "ука-
зывает" на х. Операция & применима только к переменным и
элементам массива, конструкции вида &(х-1) и &3 являются не-
законными. Нельзя также получить адрес регистровой перемен-
ной.
Унарная операция * рассматривает свой операнд как адрес
конечной цели и обращается по этому адресу, чтобы извлечь
содержимое. Следовательно, если Y тоже имеет тип INT, то
Y = *рх;
присваивает Y содержимое того, на что указывает рх. Так пос-
ледовательность
рх = &х;
Y = *рх;
присваивает Y то же самое значение, что и оператор
Y = X;
Переменные, участвующие во всем этом необходимо описать:
INT X, Y;
INT *PX;
- 99 -
с описанием для X и Y мы уже неодонократно встречались.
Описание указателя
INT *PX;
является новым и должно рассматриваться как мнемоническое;
оно говорит, что комбинация *PX имеет тип INT. Это означает,
что если PX появляется в контексте *PX, то это эквивалентно
переменной типа INT. Фактически синтаксис описания перемен-
ной имитирует синтаксис выражений, в которых эта переменная
может появляться. Это замечание полезно во всех случаях,
связанных со сложными описаниями. Например,
DOUBLE ATOF(), *DP;
говорит, что ATOF() и *DP имеют в выражениях значения типа
DOUBLE.
Вы должны также заметить, что из этого описания следу-
ет, что указатель может указывать только на определенный вид
объектов.
Указатели могут входить в выражения. Например, если PX
указывает на целое X, то *PX может появляться в любом кон-
тексте, где может встретиться X. Так оператор
Y = *PX + 1
присваивает Y значение, на 1 большее значения X;
PRINTF("%D\N", *PX)
печатает текущее значение X;
D = SQRT((DOUBLE) *PX)
получает в D квадратный корень из X, причем до передачи фун-
кции SQRT значение X преобразуется к типу DOUBLE. (Смотри
главу 2).
В выражениях вида
Y = *PX + 1
унарные операции * и & связаны со своим операндом более
крепко, чем арифметические операции, так что такое выражение
берет то значение, на которое указывает PX, прибавляет 1 и
присваивает результат переменной Y. Мы вскоре вернемся к то-
му, что может означать выражение
Y = *(PX + 1)
Ссылки на указатели могут появляться и в левой части
присваиваний. Если PX указывает на X, то
*PX = 0
- 100 -
полагает X равным нулю, а
*PX += 1
увеличивает его на единицу, как и выражение
(*PX)++
Круглые скобки в последнем примере необходимы; если их опус-
тить, то поскольку унарные операции, подобные * и ++, выпол-
няются справа налево, это выражение увеличит PX, а не ту пе-
ременную, на которую он указывает.
И наконец, так как указатели являются переменными, то с
ними можно обращаться, как и с остальными переменными. Если
PY - другой указатель на переменную типа INT, то
PY = PX
копирует содержимое PX в PY, в результате чего PY указывает
на то же, что и PX.
5.2. Указатели и аргументы функций
Так как в "с" передача аргументов функциям осуществляет-
ся "по значению", вызванная процедура не имеет непосредст-
венной возможности изменить переменную из вызывающей прог-
раммы. Что же делать, если вам действительно надо изменить
аргумент? например, программа сортировки захотела бы поме-
нять два нарушающих порядок элемента с помощью функции с
именем SWAP. Для этого недостаточно написать
SWAP(A, B);
определив функцию SWAP при этом следующим образом:
SWAP(X, Y) /* WRONG */
INT X, Y;
{
INT TEMP;
TEMP = X;
X = Y;
Y = TEMP;
}
из-за вызова по значению SWAP не может воздействовать на
агументы A и B в вызывающей функции.
К счастью, все же имеется возможность получить желаемый
эффект. Вызывающая программа передает указатели подлежащих
изменению значений:
SWAP(&A, &B);
- 101 -
так как операция & выдает адрес переменной, то &A является
указателем на A. В самой SWAP аргументы описываются как ука-
затели и доступ к фактическим операндам осуществляется через
них.
SWAP(PX, PY) /* INTERCHANGE *PX AND *PY */
INT *PX, *PY;
{
INT TEMP;
TEMP = *PX;
*PX = *PY;
*PY = TEMP;
}
Указатели в качестве аргументов обычно используются в
функциях, которые должны возвращать более одного значения.
(Можно сказать, что SWAP вOзвращает два значения, новые зна-
чения ее аргументов). В качестве примера рассмотрим функцию
GETINT, которая осуществляет преобразование поступающих в
своболном формате данных, разделяя поток символов на целые
значения, по одному целому за одно обращение. Функция GETINT
должна возвращать либо найденное значение, либо признак кон-
ца файла, если входные данные полностью исчерпаны. Эти зна-
чения должны возвращаться как отдельные объекты, какое бы
значение ни использовалось для EOF, даже если это значение
вводимого целого.
Одно из решений, основывающееся на описываемой в главе 7
функции ввода SCANF, состоит в том, чтобы при выходе на ко-
нец файла GETINT возвращала EOF в качестве значения функции;
любое другое возвращенное значение говорит о нахождении нор-
мального целого. Численное же значение найденного целого
возвращается через аргумент, который должен быть указателем
целого. Эта организация разделяет статус конца файла и чис-
ленные значения.
Следующий цикл заполняет массив целыми с помощью обраще-
ний к функции GETINT:
INT N, V, ARRAY[SIZE];
FOR (N = 0; N < SIZE && GETINT(&V) != EOF; N++)
ARRAY[N] = V;
В результате каждого обращения V становится равным следующе-
му целому значению, найденному во входных данных. Обратите
внимание, что в качестве аргумента GETINT необходимо указать
&V а не V. Использование просто V скорее всего приведет к
ошибке адресации, поскольку GETINT полагает, что она работа-
ет именно с указателем.
- 102 -
Сама GETINT является очевидной модификацией написанной
нами ранее функции ATOI:
GETINT(PN) /* GET NEXT INTEGER FROM INPUT */
INT *PN;
{
INT C,SIGN;
WHILE ((C = GETCH()) == ' ' \!\! C == '\N'
\!\! C == '\T'); /* SKIP WHITE SPACE */
SIGN = 1;
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(C);
RETURN(C);
}
Выражение *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 != '\0'; 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 != '\0')
P++;
RETURN(P-S);
}
При описании указатель P в этой функции инициализирован
посредством строки S, в результате чего он указывает на пер-
вый символ строки. В цикле WHILE по очереди проверяется каж-
дый символ до тех пор, пока не появится символ конца строки
\0. Так как значение \0 равно нулю, а 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"
является массивом символов. Компилятор завершает внутреннее
представление такого массива символом \0, так что программы
могут находить его конец. Таким образом, длина массива в па-
мяти оказывается на единицу больше числа символов между
двойными кавычками.
По-видимому чаще всего строчные константы появляются в
качестве аргументов функций, как, например, в
PRINTF ("HELLO, WORLD\N");
когда символьная строка, подобная этой, появляется в прог-
рамме, то доступ к ней осуществляется с помощью указателя
символов; функция 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]) != '\0')
I++;
}
Для сопоставления ниже дается вариант STRCPY с указате-
лями.
STRCPY(S, T) /* COPY T TO S; POINTER VERSION 1 */
CHAR *S, *T;
{
WHILE ((*S = *T) != '\0') {
S++;
T++;
}
}
Так как аргументы передаются по значению, функция STRCPY
может использовать S и T так, как она пожелает. Здесь они с
удобством полагаются указателями, которые передвигаются
вдоль массивов, по одному символу за шаг, пока не будет ско-
пирован в S завершающий в T символ \0.
На практике функция STRCPY была бы записана не так, как
мы показали выше. Вот вторая возможность:
STRCPY(S, T) /* COPY T TO S; POINTER VERSION 2 */
CHAR *S, *T;
{
WHILE ((*S++ = *T++) != '\0')
;
}
Здесь увеличение S и T внесено в проверочную часть. Зна-
чением *T++ является символ, на который указывал T до увели-
чения; постфиксная операция ++ не изменяет T, пока этот сим-
вол не будет извлечен. Точно так же этот символ помещается в
старую позицию S, до того как S будет увеличено. Конечный
результат заключается в том, что все символы, включая завер-
шающий \0, копируются из T в S.
- 110 -
И как последнее сокращение мы опять отметим, что сравне-
ние с \0 является излишним, так что функцию можно записать в
виде
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 S0 IF S>T */
CHAR S[], T[];
{
INT I;
I = 0;
WHILE (S[I] == T[I])
IF (S[I++] == '\0')
RETURN(0);
RETURN(S[I]-T[I]);
}
Вот версия STRCMP с указателями:
STRCMP(S, T) /* RETURN <0 IF S0 IF S>T */
CHAR *S, *T;
{
FOR ( ; *S == *T; S++, T++)
IF (*S == '\0')
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] = {
(0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31),
(0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
};
- 113 -
DAY_OF_YEAR(YEAR, MONTH, DAY) /* SET DAY OF YEAR */
INT YEAR, MONTH, DAY; /* FROM MONTH & DAY */
{
INT I, LEAP;
LEAP = YEAR%4 == 0 && YEAR%100 != 0 \!\! YEAR%400 == 0;
FOR (I = 1; I < MONTH; I++)
DAY += DAY_TAB[LEAP][I];
RETURN(DAY);
{
MONTH_DAY(YEAR, YEARDAY, PMONTH, PDAY) /*SET MONTH,DAY */
INT YEAR, YEARDAY, *PMONTH, *PDAY; /* FROM DAY OF YEAR */
{
LEAP = YEAR%4 == 0 && YEAR%100 != 0 \!\! YEAR%400 == 0;
FOR (I = 1; YEARDAY > DAY_TAB[LEAP][I]; I++)
YEARDAY -= DAY_TAB[LEAP][I];
*PMONTH = I;
*PDAY = YEARDAY;
}
Массив DAY_TAB должен быть внешним как для DAY_OF_YEAR, так
и для MONTH_DAY, поскольку он используется обеими этими фун-
кциями.
Массив DAY_TAB является первым двумерным массивом, с ко-
торым мы имеем дело. По определению в "C" двумерный массив
по существу является одномерным массивом, каждый элемент ко-
торого является массивом. Поэтому индексы записываются как
DAY_TAB[I][J]
а не
DAY_TAB [I, J]
как в большинстве языков. В остальном с двумерными массивами
можно в основном обращаться таким же образом, как в других
языках. Элементы хранятся по строкам, т.е. При обращении к
элементам в порядке их размещения в памяти быстрее всего из-
меняется самый правый индекс.
Массив инициализируется с помощью списка начальных зна-
чений, заключенных в фигурные скобки; каждая строка двумер-
ного массива инициализируется соответствующим подсписком. Мы
поместили в начало массива DAY_TAB столбец из нулей для то-
го, чтобы номера месяцев изменялись естественным образом от
1 до 12, а не от 0 до 11. Так как за экономию памяти у нас
пока не награждают, такой способ проще, чем подгонка индек-
сов.
Если двумерный массив передается функции, то описание
соответствующего аргумента функции должно содержать количес-
тво столбцов; количество строк несущественно, поскольку, как
и прежде, фактически передается указатель. В нашем конкрет-
ном случае это указатель объектов, являющихся массивами из
- 114 -
13 чисел типа INT. Таким образом, если бы требовалось пере-
дать массив DAY_TAB функции F, то описание в F имело бы вид:
F(DAY_TAB)
INT DAY_TAB[2][13];
{
...
}
Так как количество строк является несущественным, то описа-
ние аргумента в F могло бы быть таким:
INT DAY_TAB[][13];
или таким
INT (*DAY_TAB)[13];
в которм говорится, что аргумент является указателем массива
из 13 целых. Круглые скобки здесь необходимы, потому что
квадратные скобки [] имеют более высокий уровень старшинст-
ва, чем *; как мы увидим в следующем разделе, без круглых
скобок
INT *DAY_TAB[13];
является описанием массива из 13 указателей на целые.
5.8. Массивы указателей; указатели указателей
Так как указатели сами являются переменными, то вы впол-
не могли бы ожидать использования массива указателей. Это
действительно так. Мы проиллюстрируем это написанием прог-
раммы сортировки в алфавитном порядке набора текстовых
строк, предельно упрощенного варианта утилиты SORT операци-
онной систем UNIX.
В главе 3 мы привели функцию сортировки по шеллу, кото-
рая упорядочивала массив целых. Этот же алгоритм будет рабо-
тать и здесь, хотя теперь мы будем иметь дело со строчками
текста различной длины, которые, в отличие от целых, нельзя
сравнивать или перемещать с помощью одной операции. Мы нуж-
даемся в таком представлении данных, которое бы позволяло
удобно и эффективно обрабатывать строки текста переменной
длины.
Здесь и возникают массивы указателей. Если подлежащие
сортировке сроки хранятся одна за другой в длинном символь-
ном массиве (управляемом, например, функцией ALLOC), то к
каждой строке можно обратиться с помощью указателя на ее
первый символ. Сами указатели можно хранить в массиве. две
строки можно сравнить, передав их указатели функции STRCMP.
- 115 -
Если две расположенные в неправильном порядке строки должны
быть переставлены, то фактически переставляются указатели в
массиве указателей, а не сами тексты строк. Этим исключаются
сразу две связанные проблемы: сложного управления памятью и
больших дополнительных затрат на фактическую перестановку
строк.
Процесс сортировки включает три шага:
чтение всех строк ввода
их сортировка
вывод их в правильном порядке
Как обычно, лучше разделить программу на несколько функций в
соответствии с естественным делением задачи и выделить веду-
щую функцию, управляющую работой всей программы.
Давайте отложим на некоторое время рассмотрение шага сорти-
ровки и сосредоточимся на структуре данных и вводе-выводе.
Функция, осуществляющая ввод, должна извлечь символы каждой
строки, запомнить их и построить массив указателей строк.
Она должна также подсчитать число строк во вводе, так как
эта информация необходима при сортировке и выводе. так как
функция ввода в состоянии справиться только с конечным чис-
лом вводимых строк, в случае слишком большого их числа она
может возвращать некоторое число, отличное от возможного
числа строк, например -1. Функция осуществляющая вывод, дол-
жна печатать строки в том порядке, в каком они появляются в
массиве указателей.
#DEFINE NULL 0
#DEFINE LINES 100 /* MAX LINES TO BE SORTED */
MAIN() /* SORT INPUT LINES */
\(
CHAR *LINEPTR[LINES]; /*POINTERS TO TEXT LINES */
INT NLINES; /* NUMBER OF INPUT LINES READ */
IF ((NLINES = READLINES(LINEPTR, LINES)) >= 0) \(
SORT(LINEPTR, NLINES);
WRITELINES(LINEPTR, NLINES);
\)
ELSE
PRINTF("INPUT TOO BIG TO SORT\N");
\)
#DEFINE MAXLEN 1000
- 116 -
READLINES(LINEPTR, MAXLINES) /* READ INPUT LINES */
CHAR *LINEPTR[]; /* FOR SORTING */
INT MAXLINES;
\(
INT LEN, NLINES;
CHAR *P, *ALLOC(), LINE[MAXLEN];
NLINES = 0;
WHILE ((LEN = GETLINE(LINE, MAXLEN)) > 0)
IF (NLINES >= MAXLINES)
RETURN(-1);
ELSE IF ((P = ALLOC(LEN)) == NULL)
RETURN (-1);
ELSE \(
LINE[LEN-1] = '\0'; /* ZAP NEWLINE */
STRCPY(P,LINE);
LINEPTR[NLINES++] = P;
\)
RETURN(NLINES);
\)
Символ новой строки в конце каждой строки удаляется, так что
он никак не будет влиять на порядок, в котором сортируются
строки.
WRITELINES(LINEPTR, NLINES) /* WRITE OUTPUT LINES */
CHAR *LINEPTR[];
INT NLINES;
\(
INT I;
FOR (I = 0; I < NLINES; I++)
PRINTF("%S\N", LINEPTR[I]);
\)
Существенно новым в этой программе является описание
CHAR *LINEPTR[LINES];
которое сообщает, что LINEPTR является массивом из LINES
элементов, каждый из которых - указатель на переменные типа
CHAR. Это означает, что LINEPTR[I] - указатель на символы, а
*LINEPTR[I] извлекает символ.
Так как сам LINEPTR является массивом, который передает-
ся функции WRITELINES, с ним можно обращаться как с указате-
лем точно таким же образом, как в наших более ранних приме-
- 117 -
рах. Тогда последнюю функцию можно переписать в виде:
WRITELINES(LINEPTR, NLINES) /* WRITE OUTPUT LINES */
CHAR *LINEPTR[];
INT NLINES;
\(
INT I;
WHILE (--NLINES >= 0)
PRINTF("%S\N", *LINEPTR++);
\)
здесь *LINEPTR сначала указывает на первую строку; каждое
увеличение передвигает указатель на следующую строку, в то
время как NLINES убывает до нуля.
Справившись с вводом и выводом, мы можем перейти к сор-
тировке. программа сортировки по шеллу из главы 3 требует
очень небольших изменений: должны быть модифицированы описа-
ния, а операция сравнения выделена в отдельную функцию. Ос-
новной алгоритм остается тем же самым, и это дает нам опре-
деленную уверенность, что он по-прежнему будет работать.
SORT(V, N) /* SORT STRINGS V[0] ... V[N-1] */
CHAR *V[]; /* INTO INCREASING ORDER */
INT N;
\(
INT GAP, I, J;
CHAR *TEMP;
FOR (GAP = N/2; GAP > 0; GAP /= 2)
FOR (I = GAP; I < N; I++)
FOR (J = I - GAP; J >= 0; J -= GAP) \(
IF (STRCMP(V[J], V[J+GAP]) <= 0)
BREAK;
TEMP = V[J];
V[J] = V[J+GAP];
V[J+GAP] = TEMP;
\)
\)
Так как каждый отдельный элемент массива V (имя формального
параметра, соответствующего LINEPTR) является указателем на
символы, то и TEMP должен быть указателем на символы, чтобы
их было можно копировать друг в друга.
Мы написали эту программу по возможности более просто с
тем, чтобы побыстрее получить работающую программу. Она мог-
ла бы работать быстрее, если, например, вводить строки не-
посредственно в массив, управляемый функцией READLINES, а не
копировать их в LINE, а затем в скрытое место с помощью фун-
- 118 -
кции ALLOC. но мы считаем, что будет разумнее первоначальный
вариант сделать более простым для понимания, а об "эффектив-
ности" позаботиться позднее. Все же, по-видимому, способ,
позволяющий добиться заметного ускорения работы программы
состоит не в исключении лишнего копирования вводимых строк.
Более вероятно, что существенной разницы можно достичь за
счет замены сортировки по шеллу на нечто лучшее, например,
на метод быстрой сортировки.
В главе 1 мы отмечали, что поскольку в циклах WHILE и
FOR проверка осуществляется до того, как тело цикла выпол-
нится хотя бы один раз, эти циклы оказываются удобными для
обеспечения правильной работы программы при граничных значе-
ниях, в частности, когда ввода вообще нет. Очень полезно
просмотреть все функции программы сортировки, разбираясь,
что происходит, если вводимый текст отсутствует.
Упражнение 5-5.
--------------
Перепишите функцию READLINES таким образом, чтобы она
помещала строки в массив, предоставляемый функцией MAIN, а
не в память, управляемую обращениями к функции ALLOC. На-
сколько быстрее стала программа?
5.9. Инициализация массивов указателей.
Рассмотрим задачу написания функции MONTH_NAME(N), кото-
рая возвращает указатель на символьную строку, содержащую
имя N-го месяца. Это идеальная задача для применения внут-
реннего статического массива. Функция MONTH_NAME содержит
локальный массив символьных строк и при обращении к ней воз-
вращает указатель нужной строки. Тема настоящего раздела -
как инициализировать этот массив имен.
CHAR *MONTH_NAME(N) /* RETURN NAME OF N-TH MONTH */
INT N;
\(
STATIC CHAR *NAME[] = \(
"ILLEGAL MONTH",
"JANUARY",
"FEBRUARY",
"MARCH",
"APRIL",
"MAY",
"JUN",
"JULY",
"AUGUST",
"SEPTEMBER",
"OCTOBER",
"NOVEMBER",
"DECEMBER"
\);
RETURN ((N < 1 \!\! N > 12) ? NAME[0] : NAME[N]);
\)
- 119 -
Описание массива указателей на символы NAME точно такое же,
как аналогичное описание LINEPTR в примере с сортировкой.
Инициализатором является просто список символьных строк;
каждая строка присваивается соответствующей позиции в масси-
ве. Более точно, символы I-ой строки помещаются в какое-то
иное место, а ее указатель хранится в NAME[I]. Поскольку
размер массива NAME не указан, компилятор сам подсчитывает
количество инициализаторов и соответственно устанавливает
правильное число.
5.10. Указатели и многомерные массивы
Начинающие изучать язык "с" иногда становятся в тупик
перед вопросом о различии между двумерным массивом и масси-
вом указателей, таким как NAME в приведенном выше примере.
Если имеются описания
INT A[10][10];
INT *B[10];
то A и B можно использовать сходным образом в том смысле,
что как A[5][5], так и B[5][5] являются законными ссылками
на отдельное число типа INT. Но A - настоящий массив: под
него отводится 100 ячеек памяти и для нахождения любого ука-
занного элемента проводятся обычные вычисления с прямоуголь-
ными индексами. Для B, однако, описание выделяет только 10
указателей; каждый указатель должен быть установлен так,
чтобы он указывал на массив целых. если предположить, что
каждый из них указывает на массив из 10 элементов, то тогда
где-то будет отведено 100 ячеек памяти плюс еще десять ячеек
для указателей. Таким образом, массив указателей использует
несколько больший объем памяти и может требовать наличие яв-
ного шага инициализации. Но при этом возникают два преиму-
щества: доступ к элементу осуществляется косвенно через ука-
затель, а не посредством умножения и сложения, и строки мас-
сива могут иметь различные длины. Это означает, что каждый
элемент B не должен обязательно указывать на вектор из 10
элементов; некоторые могут указывать на вектор из двух эле-
ментов, другие - из двадцати, а третьи могут вообще ни на
что не указывать.
Хотя мы вели это обсуждение в терминах целых, несомнен-
но, чаще всего массивы указателей используются так, как мы
продемонстрировали на функции MONTH_NAME, - для хранения
символьных строк различной длины.
Упражнение 5-6.
--------------
Перепишите функции DAY_OF_YEAR и MONTH_DAY, используя
вместо индексации указатели.
- 120 -
5.11. Командная строка аргументов
Системные средства, на которые опирается реализация язы-
ка "с", позволяют передавать командную строку аргументов или
параметров начинающей выполняться программе. Когда функция
MAIN вызывается к исполнению, она вызывается с двумя аргу-
ментами. Первый аргумент (условно называемый ARGC) указывает
число аргументов в командной строке, с которыми происходит
обращение к программе; второй аргумент (ARGV) является ука-
зателем на массив символьных строк, содержащих эти аргумен-
ты, по одному в строке. Работа с такими строками - это обыч-
ное использование многоуровневых указателей.
Самую простую иллюстрацию этой возможности и необходимых
при этом описаний дает программа ECHO, которая просто печа-
тает в одну строку аргументы командной строки, разделяя их
пробелами. Таким образом, если дана команда
ECHO HELLO, WORLD
то выходом будет
HELLO, WORLD
по соглашению ARGV[0] является именем, по которому вызывает-
ся программа, так что ARGC по меньшей мере равен 1. В приве-
денном выше примере ARGC равен 3, а ARGV[0], ARGV[1] и
ARGV[2] равны соответственно "ECHO", "HELLO," и "WORLD".
Первым фактическим агументом является ARGV[1], а последним -
ARGV[ARGC-1]. Если ARGC равен 1, то за именем программы не
следует никакой командной строки аргументов. Все это показа-
но в ECHO:
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 1ST VERSION */
INT ARGC;
CHAR *ARGV[];
\(
INT I;
FOR (I = 1; I < ARGC; I++)
PRINTF("%S%C", ARGV[I], (I 0)
PRINTF("%S%C",*++ARGV, (ARGC > 1) ? ' ' : '\N');
\)
- 121 -
Так как ARGV является указателем на начало массива строк-ар-
гументов, то, увеличив его на 1 (++ARGV), мы вынуждаем его
указывать на подлинный аргумент ARGV[1], а не на ARGV[0].
Каждое последующее увеличение передвигает его на следующий
аргумент; при этом *ARGV становится указателем на этот аргу-
мент. одновременно величина ARGC уменьшается; когда она об-
ратится в нуль, все аргументы будут уже напечатаны.
Другой вариант:
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 3RD VERSION */
INT ARGC;
CHAR *ARGV[];
\(
WHILE (--ARGC > 0)
PRINTF((ARGC > 1) ? "%S" : "%S\N", *++ARGV);
\)
Эта версия показывает, что аргумент формата функции PRINTF
может быть выражением, точно так же, как и любой другой. Та-
кое использование встречается не очень часто, но его все же
стоит запомнить.
Как второй пример, давайте внесем некоторые усовершенст-
вования в программу отыскания заданной комбинации символов
из главы 4. Если вы помните, мы поместили искомую комбинацию
глубоко внутрь программы, что очевидно является совершенно
неудовлетворительным. Следуя утилите GREP системы UNIX, да-
вайте изменим программу так, чтобы эта комбинация указыва-
лась в качестве первого аргумента строки.
#DEFINE MAXLINE 1000
MAIN(ARGC, ARGV) /* FIND PATTERN FROM FIRST ARGUMENT */
INT ARGC;
CHAR *ARGV[];
\(
CHAR LINE[MAXLINE];
IF (ARGC != 2)
PRINTF ("USAGE: FIND PATTERN\N");
ELSE
WHILE (GETLINE(LINE, MAXLINE) > 0)
IF (INDEX(LINE, ARGV[1] >= 0)
PRINTF("%S", LINE);
\)
Теперь может быть развита основная модель, иллюстрирую-
щая дальнейшее использование указателей. Предположим, что
нам надо предусмотреть два необязательных аргумента. Один
утверждает: "напечатать все строки за исключением тех, кото-
рые содержат данную комбинацию", второй гласит: "перед каж-
дой выводимой строкой должен печататься ее номер".
- 122 -
Общепринятым соглашением в "с"-программах является то,
что аргумент, начинающийся со знака минус, вводит необяза-
тельный признак или параметр. Если мы, для того, чтобы сооб-
щить об инверсии, выберем -X, а для указания о нумерации
нужных строк выберем -N("номер"), то команда
FIND -X -N THE
при входных данных
NOW IS THE TIME
FOR ALL GOOD MEN
TO COME TO THE AID
OF THEIR PARTY.
Должна выдать
2:FOR ALL GOOD MEN
Нужно, чтобы необязательные аргументы могли располагать-
ся в произвольном порядке, и чтобы остальная часть программы
не зависела от количества фактически присутствующих аргумен-
тов. в частности, вызов функции INDEX не должен содержать
ссылку на ARGV[2], когда присутствует один необязательный
аргумент, и на ARGV[1], когда его нет. Более того, для поль-
зователей удобно, чтобы необязательные аргументы можно было
объединить в виде:
FIND -NX THE
вот сама программа:
#DEFINE MAXLINE 1000
MAIN(ARGC, ARGV) /* FIND PATTERN FROM FIRST ARGUMENT */
INT ARGC;
CHAR *ARGV[];
\(
CHAR LINE[MAXLINE], *S;
LONG LINENO = 0;
INT EXCEPT = 0, NUMBER = 0;
WHILE (--ARGC > 0 && (*++ARGV)[0] == '-')
FOR (S = ARGV[0]+1; *S != '\0'; S++)
SWITCH (*S) \(
CASE 'X':
EXCEPT = 1;
BREAK;
- 123 -
CASE 'N':
NUMBER = 1;
BREAK;
DEFAULT:
PRINTF("FIND: ILLEGAL OPTION %C\N", *S);
ARGC = 0;
BREAK;
\)
IF (ARGC != 1)
PRINTF("USAGE: FIND -X -N PATTERN\N");
ELSE
WHILE (GETLINе(LINE, MAXLINE) > 0) \(
LINENO++;
IF ((INDEX(LINE, *ARGV) >= 0) != EXCEPT) \
IF (NUMBER)
PRINTF("%LD: ", LINENO);
PRINTF("%S", LINE);
\)
\)
\)
Аргумент ARGV увеличивается перед каждым необязательным
аргументом, в то время как аргумент ARGC уменьшается. если
нет ошибок, то в конце цикла величина ARGC должна равняться
1, а *ARGV должно указывать на заданную комбинацию. Обратите
внимание на то, что *++ARGV является указателем аргументной
строки; (*++ARGV)[0] - ее первый символ. Круглые скобки
здесь необходимы, потому что без них выражение бы приняло
совершенно отличный (и неправильный) вид *++(ARGV[0]). Дру-
гой правильной формой была бы **++ARGV.
Упражнение 5-7.
--------------
Напишите программу ADD, вычисляющую обратное польское
выражение из командной строки. Например,
ADD 2 3 4 + *
вычисляет 2*(3+4).
Упражнение 5-8.
--------------
Модифицируйте программы ENTAB и DETAB (указанные в ка-
честве упражнений в главе 1) так, чтобы они получали список
табуляционных остановок в качестве аргументов. Если аргумен-
ты отсутствуют, используйте стандартную установку табуляций.
Упражнение 5-9.
--------------
Расширьте ENTAB и DETAB таким образом, чтобы они воспри-
нимали сокращенную нотацию
ENTAB M +N
- 124 -
означающую табуляционные остановки через каждые N столбцов,
начиная со столбца M. Выберите удобное (для пользователя)
поведение функции по умолчанию.
Упражнение 5-10.
---------------
Напишите программу для функции TAIL, печатающей послед-
ние N строк из своего файла ввода. Пусть по умолчанию N рав-
но 10, но это число может быть изменено с помощью необяза-
тельного аргумента, так что
TAIL -N
печатает последние N строк. программа должна действовать ра-
ционально, какими бы неразумными ни были бы ввод или значе-
ние N. Составьте программу так, чтобы она оптимальным обра-
зом использовала доступную память: строки должны храниться,
как в функции SORT, а не в двумерном массиве фиксированного
размера.
5.12. Указатели на функции
В языке "с" сами функции не являются переменными, но
имеется возможность определить указатель на функцию, который
можно обрабатывать, передавать другим функциям, помещать в
массивы и т.д. Мы проиллюстрируем это, проведя модификацию
написанной ранее программы сортировки так, чтобы при задании
необязательного аргумента -N она бы сортировала строки ввода
численно, а не лексикографически.
Сортировка часто состоит из трех частей - сравнения, ко-
торое определяет упорядочивание любой пары объектов, перес-
тановки, изменяющей их порядок, и алгоритма сортировки, осу-
ществляющего сравнения и перестановки до тех пор, пока
объекты не расположатся в нужном порядке. Алгоритм сортиров-
ки не зависит от операций сравнения и перестановки, так что,
передавая в него различные функции сравнения и перестановки,
мы можем организовать сортировку по различным критериям.
Именно такой подход используется в нашей новой программе
сортировки.
Как и прежде, лексикографическое сравнение двух строк
осуществляется функцией STRCMP, а перестановка функцией
SWAP; нам нужна еще функция NUMCMP, сравнивающая две строки
на основе численного значения и возвращающая условное указа-
ние того же вида, что и STRCMP. Эти три функции описываются
в MAIN и указатели на них передаются в SORT. В свою очередь
функция SORT обращается к этим функциям через их указатели.
мы урезали обработку ошибок в аргументах с тем, чтобы сосре-
доточиться на главных вопросах.
- 125 -
#DEFINE LINES 100 /* MAX NUMBER OF LINES
TO BE SORTED */
MAIN(ARGC, ARGV) /* SORT INPUT LINES */
INT ARGC;
CHAR *ARGV[];
\(
CHAR *LINEPTR[LINES]; /* POINTERS TO TEXT LINES */
INT NLINES; /* NUMBER OF INPUT LINES READ */
INT STRCMP(), NUMCMP(); /* COMPARSION FUNCTIONS */
INT SWAP(); /* EXCHANGE FUNCTION */
INT NUMERIC = 0; /* 1 IF NUMERIC SORT */
IF(ARGC>1 && ARGV[1][0] == '-' && ARGV[1][1]=='N')
NUMERIC = 1;
IF(NLINES = READLINES(LINEPTR, LINES)) >= 0) \(
IF (NUMERIC)
SORT(LINEPTR, NLINES, NUMCMP, SWAP);
ELSE
SORT(LINEPTR, NLINES, STRCMP, SWAP);
WRITELINES(LINEPTR, NLINES);
\) ELSE
PRINTF("INPUT TOO BIG TO SORT\N");
\)
Здесь STRCMP, NIMCMP и SWAP - адреса функций; так как извес-
тно, что это функции, операция & здесь не нужна совершенно
аналогично тому, как она не нужна и перед именем массива.
Передача адресов функций организуется компилятором.
Второй шаг состоит в модификации SORT:
SORT(V, N, COMP, EXCH) /* SORT STRINGS V[0] ... V[N-1] */
CHAR *V[]; /* INTO INCREASING ORDER */
INT N;
INT (*COMP)(), (*EXCH)();
\(
INT GAP, I, J;
FOR(GAP = N/2; GAP > 0; GAP /= 2)
FOR(I = GAP; I < N; I++)
FOR(J = I-GAP; J >= 0; J -= GAP) \(
IF((*COMP)(V[J], V[J+GAP]) <= 0)
BREAK;
(*EXCH)(&V[J], &V[J+GAP]);
\)
\)
- 126 -
Здесь следует обратить определенное внимание на описа-
ния. Описание
INT (*COMP)()
говорит, что COMP является указателем на функцию, которая
возвращает значение типа INT. Первые круглые скобки здесь
необходимы; без них описание
INT *COMP()
говорило бы, что COMP является функцией, возвращающей указа-
тель на целые, что, конечно, совершенно другая вещь.
Использование COMP в строке
IF (*COMP)(V[J], V[J+GAP]) <= 0)
полностью согласуется с описанием: COMP - указатель на функ-
цию, *COMP - сама функция, а
(*COMP)(V[J], V[J+GAP])
- обращение к ней. Круглые скобки необходимы для правильного
объединения компонентов.
Мы уже приводили функцию STRCMP, сравнивающую две строки
по первому численному значению:
NUMCMP(S1, S2) /* COMPARE S1 AND S2 NUMERICALLY */
CHAR *S1, *S2;
\(
DOUBLE ATOF(), V1, V2;
V1 = ATOF(S1);
V2 = ATOF(S2);
IF(V1 < V2)
RETURN(-1);
ELSE IF(V1 > V2)
RETURN(1);
ELSE
RETURN (0);
\)
Заключительный шаг состоит в добавлении функции SWAP,
переставляющей два указателя. Это легко сделать, непосредст-
венно используя то, что мы изложили ранее в этой главе.
- 127 -
SWAP(PX, PY) /* INTERCHANGE *PX AND *PY */
CHAR *PX[], *PY[];
\(
CHAR *TEMP;
TEMP = *PX;
*PX = *PY;
*PY = TEMP;
\)
Имеется множество других необязятельных аргументов, ко-
торые могут быть включены в программу сортировки: некоторые
из них составляют интересные упражнения.
Упражнение 5-11.
---------------
Модифицируйте SORT таким образом, чтобы она работала с
меткой -R, указывающей на сортировку в обратном (убывающем)
порядке. Конечно, -R должна работать с -N.
Упражнение 5-12.
---------------
Добавьте необязательный аргумент -F, объединяющий вместе
прописные и строчные буквы, так чтобы различие регистров не
учитывалось во время сортировки: данные из верхнего и нижне-
го регистров сортируются вместе, так что буква 'а' прописное
и 'а' строчное оказываются соседними , а не разделенными це-
лым алфавитом.
Упражнение 5-13.
---------------
Добавьте необязательный аргумент -D ("словарное упорядо-
чивание"), при наличии которого сравниваются только буквы,
числа и пробелы. Позаботьтесь о том, чтобы эта функция рабо-
тала и вместе с -F.
Упражнение 5-14.
---------------
Добавьте возможность обработки полей, так чтобы можно
было сортировать поля внутри строк. Каждое поле должно сор-
тироваться в соответствии с независимым набором необязатель-
ных аргументов. (предметный указатель этой книги сортировал-
ся с помощью аргументов -DF для категории указателя и с -N
для номеров страниц).