45940 (665245), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

ошибке адресации, поскольку 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©;

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 != '\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 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; 1^ST VERSION */

INT ARGC;

CHAR *ARGV[];

\(

INT I;

FOR (I = 1; I < ARGC; I++)

PRINTF(“%S%C”, ARGV[I], (I

\)

Поскольку ARGV является указателем на массив указателей, то

существует несколько способов написания этой программы, ис-

пользующих работу с указателем, а не с индексацией массива.

Мы продемонстрируем два варианта.

MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 2^ND VERSION */

INT ARGC;

CHAR *ARGV[];

\(

WHILE (--ARGC > 0)

PRINTF(“%S%C”,*++ARGV, (ARGC > 1) ? ' ' : '\N');

\)

• 121 -

Так как ARGV является указателем на начало массива строк-ар-

гументов, то, увеличив его на 1 (++ARGV), мы вынуждаем его

указывать на подлинный аргумент ARGV[1], а не на ARGV[0].

Каждое последующее увеличение передвигает его на следующий

аргумент; при этом *ARGV становится указателем на этот аргу-

мент. одновременно величина ARGC уменьшается; когда она об-

ратится в нуль, все аргументы будут уже напечатаны.

Другой вариант:

MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 3^RD 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 она бы сортировала строки ввода

численно, а не лексикографически.

Сортировка часто состоит из трех частей - сравнения, ко-

торое определяет упорядочивание любой пары объектов, перес-

тановки, изменяющей их порядок, и алгоритма сортировки, осу-

ществляющего сравнения и перестановки до тех пор, пока

объекты не расположатся в нужном порядке. Алгоритм сортиров-

Характеристики

Список файлов реферата