м, если 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). Короче, любое выражение, включающее массивы и индексы, может быть записано через указатели и смещения и наоборот, причем даже в одном и том же утверждении. Имеется одно различие между именем массива и указателем, которое необходимо иметь в виду. указатель является перемен- ной, так что операции 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) передают функции 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" содержит аналогичные функции, не имеющие таких ограничений, и, кроме того, в главе 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; ) Дадим некоторые пояснения. Вообще говоря, указатель мо- жет быть инициализирован точно так же, как и любая другая переменная, хотя обычно единственными осмысленными значения- ми являются 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 истинно, если 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 дает число просмотренных символов, т.е. Длину строки. Арифметика указателей последовательна: если бы мы имели дело с переменными типа 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. Первая функция - это 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. И как последнее сокращение мы опять отметим, что сравне- ние с \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 S<T, 0 IF S==T, >0 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 S<T, 0 IF S==T, >0 IF S>T */ CHAR *S, *T; { FOR ( ; *S == *T; S++, T++) IF (*S == '\0') RETURN(0); RETURN(*S-*T); } так как ++ и -- могут быть как постфиксными, так и префиксными операциями, встречаются другие комбинации * и ++ и --, хотя и менее часто. Например *++P увеличивает 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); } на практике существует сильное стремление опускать описания: *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) }; 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. Так как за экономию памяти у нас пока не награждают, такой способ проще, чем подгонка индек- сов. Если двумерный массив передается функции, то описание соответствующего аргумента функции должно содержать количес- тво столбцов; количество строк несущественно, поскольку, как и прежде, фактически передается указатель. В нашем конкрет- ном случае это указатель объектов, являющихся массивами из 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. Если две расположенные в неправильном порядке строки должны быть переставлены, то фактически переставляются указатели в массиве указателей, а не сами тексты строк. Этим исключаются сразу две связанные проблемы: сложного управления памятью и больших дополнительных затрат на фактическую перестановку строк. Процесс сортировки включает три шага: чтение всех строк ввода их сортировка вывод их в правильном порядке Как обычно, лучше разделить программу на несколько функций в соответствии с естественным делением задачи и выделить веду- щую функцию, управляющую работой всей программы. Давайте отложим на некоторое время рассмотрение шага сорти- ровки и сосредоточимся на структуре данных и вводе-выводе. Функция, осуществляющая ввод, должна извлечь символы каждой строки, запомнить их и построить массив указателей строк. Она должна также подсчитать число строк во вводе, так как эта информация необходима при сортировке и выводе. так как функция ввода в состоянии справиться только с конечным чис- лом вводимых строк, в случае слишком большого их числа она может возвращать некоторое число, отличное от возможного числа строк, например -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 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, с ним можно обращаться как с указате- лем точно таким же образом, как в наших более ранних приме- рах. Тогда последнюю функцию можно переписать в виде: 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, а затем в скрытое место с помощью фун- кции 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]); \) Описание массива указателей на символы 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, используя вместо индексации указатели. 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<ARGC-1) ? ' ' : '\N'); \) Поскольку ARGV является указателем на массив указателей, то существует несколько способов написания этой программы, ис- пользующих работу с указателем, а не с индексацией массива. Мы продемонстрируем два варианта. MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 2ND VERSION */ INT ARGC; CHAR *ARGV[]; \( WHILE (--ARGC > 0) PRINTF("%S%C",*++ARGV, (ARGC > 1) ? ' ' : '\N'); \) Так как 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); \) Теперь может быть развита основная модель, иллюстрирую- щая дальнейшее использование указателей. Предположим, что нам надо предусмотреть два необязательных аргумента. Один утверждает: "напечатать все строки за исключением тех, кото- рые содержат данную комбинацию", второй гласит: "перед каж- дой выводимой строкой должен печататься ее номер". Общепринятым соглашением в "с"-программах является то, что аргумент, начинающийся со знака минус, вводит необяза- тельный признак или параметр. Если мы, для того, чтобы сооб- щить об инверсии, выберем -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; 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 означающую табуляционные остановки через каждые N столбцов, начиная со столбца M. Выберите удобное (для пользователя) поведение функции по умолчанию. Упражнение 5-10 --------------- Напишите программу для функции TAIL, печатающей послед- ние N строк из своего файла ввода. Пусть по умолчанию N рав- но 10, но это число может быть изменено с помощью необяза- тельного аргумента, так что TAIL -N печатает последние N строк. программа должна действовать ра- ционально, какими бы неразумными ни были бы ввод или значе- ние N. Составьте программу так, чтобы она оптимальным обра- зом использовала доступную память: строки должны храниться, как в функции SORT, а не в двумерном массиве фиксированного размера. 5.12. Указатели на функции В языке "с" сами функции не являются переменными, но имеется возможность определить указатель на функцию, который можно обрабатывать, передавать другим функциям, помещать в массивы и т.д. Мы проиллюстрируем это, проведя модификацию написанной ранее программы сортировки так, чтобы при задании необязательного аргумента -N она бы сортировала строки ввода численно, а не лексикографически. Сортировка часто состоит из трех частей - сравнения, ко- торое определяет упорядочивание любой пары объектов, перес- тановки, изменяющей их порядок, и алгоритма сортировки, осу- ществляющего сравнения и перестановки до тех пор, пока объекты не расположатся в нужном порядке. Алгоритм сортиров- ки не зависит от операций сравнения и перестановки, так что, передавая в него различные фу