ом, если 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 она бы сортировала строки ввода численно, а не лексикографически. Сортировка часто состоит из трех частей - сравнения, ко- торое определяет упорядочивание любой пары объектов, перес- тановки, изменяющей их порядок, и алгоритма сортировки, осу- ществляющего сравнения и перестановки до тех пор, пока объекты не расположатся в нужном порядке. Алгоритм сортиров- ки не зависит от операций сравнения и перестановки, так что, передавая в него различные функции сравнения и перестановки, мы можем организовать сортировку по различным критериям. Именно такой подход используется в нашей новой программе сортировки. Как и прежде, лексикографическое сравнение двух строк осуществляется функцией STRCMP, а перестановка функцией SWAP; нам нужна еще функция NUMCMP, сравнивающая две строки на основе численного значения и возвращающая условное указа- ние того же вида, что и STRCMP. Эти три функции описываются в MAIN и указатели на них передаются в SORT. В свою очередь функция SORT обращается к этим функциям через их указатели. мы урезали обработку ошибок в аргументах с тем, чтобы сосре- доточиться на главных вопросах. #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]); \) \) Здесь следует обратить определенное внимание на описа- ния. Описание 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, переставляющей два указателя. Это легко сделать, непосредст- венно используя то, что мы изложили ранее в этой главе. 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 для номеров страниц).  * 6. Структуры *  Структура - это набор из одной или более переменных, возможно различных типов, сгруппированных под одним именем для удобства обработки. (В некоторых языках, самый известный из которых паскаль, структуры называются "записями"). Традиционным примером структуры является учетная карточ- ка работающего: "служащий" описывается набором атрибутов та- ких, как фамилия, имя, отчество (ф.и.о.), адрес, код соци- ального обеспечения, зарплата и т.д. Некоторые из этих атри- бутов сами могут оказаться структурами: ф.и.о. Имеет нес- колько компонент, как и адрес, и даже зарплата. Структуры оказываются полезными при организации сложных данных особенно в больших программах, поскольку во многих ситуациях они позволяют сгруппировать связанные данные таким образом, что с ними можно обращаться, как с одним целым, а не как с отдельными объектами. В этой главе мы постараемся продемонстрировать то, как используются структуры. Програм- мы, которые мы для этого будем использовать, больше, чем многие другие в этой книге, но все же достаточно умеренных размеров. 6.1. Основные сведения Давайте снова обратимся к процедурам преобразования даты из главы 5. Дата состоит из нескольких частей таких, как день, месяц, и год, и, возможно, день года и имя месяца. Эти пять переменных можно объеденить в одну структуру вида: STRUCT DATE \( INT DAY; INT MONTH; INT YEAR; INT YEARDAY; CHAR MON_NAME[4]; \); Описание структуры, состоящее из заключенного в фигурные скобки списка описаний, начинается с ключевого слова STRUCT. За словом STRUCT может следовать необязательное имя, называ- емое ярлыком структуры (здесь это DATе). Такой ярлык именует структуры этого вида и может использоваться в дальнейшем как сокращенная запись подробного описания. Элементы или переменные, упомянутые в структуре, называ- ются членами. Ярлыки и члены структур могут иметь такие же имена, что и обычные переменные (т.е. Не являющиеся членами структур), поскольку их имена всегда можно различить по кон- тексту. Конечно, обычно одинаковые имена присваивают только тесно связанным объектам. Точно так же, как в случае любого другого базисного ти- па, за правой фигурной скобкой, закрывающей список членов, может следовать список переменных. Оператор STRUCT \( ...\) X,Y,Z; синтаксически аналогичен INT X,Y,Z; в том смысле, что каждый из операторов описывает X , Y и Z в качестве переменных соотвествующих типов и приводит к выде- лению для них памяти. Описание структуры, за которым не следует списка пере- менных, не приводит к выделению какой-либо памяти; оно толь- ко определяет шаблон или форму структуры. Однако, если такое описание снабжено ярлыком, то этот ярлык может быть исполь- зован позднее при определении фактических экземпляров струк- тур. Например, если дано приведенное выше описание DATE, то STRUCT DATE D; определяет переменную D в качестве структуры типа DATE. Внешнюю или статическую структуру можно инициализировать, поместив вслед за ее определением список инициализаторов для ее компонент: STRUCT DATE D=\( 4, 7, 1776, 186, "JUL"\); Член определенной структуры может быть указан в выраже- нии с помощью конструкции вида имя структуры . Член -------------------- Операция указания члена структуры "." связывает имя структу- ры и имя члена. В качестве примера определим LEAP (признак високосности года) на основе даты, находящейся в структуре D, LEAP = D.YEAR % 4 == 0 && D.YEAR % 100 != 0 \!\! D.YEAR % 400 == 0; или проверим имя месяца IF (STRCMP(D.MON_NAME, "AUG") == 0) ... Или преобразуем первый символ имени месяца так, чтобы оно начиналось со строчной буквы D.MON_NAME[0] = LOWER(D.MON_NAME[0]); Структуры могут быть вложенными; учетная карточка служа- щего может фактически выглядеть так: STRUCT PERSON \( CHAR NAME[NAMESIZE]; CHAR ADDRESS[ADRSIZE]; LONG ZIPCODE; /* почтовый индекс */ LONG SS_NUMBER; /* код соц. Обеспечения */ DOUBLE SALARY; /* зарплата */ STRUCT DATE BIRTHDATE; /* дата рождения */ STRUCT DATE HIREDATE; /* дата поступления на работу */ \); Структура PERSON содержит две структуры типа DATE . Если мы определим EMP как STRUCT PERSON EMP; то EMP.BIRTHDATE.MONTH будет ссылаться на месяц рождения. Операция указания члена структуры "." ассоциируется слева направо. 6.2. Структуры и функции В языке "C" существует ряд ограничений на использование структур. Обязательные правила заключаются в том, что единс- твенные операции, которые вы можете проводить со структура- ми, состоят в определении ее адреса с помощью операции & и доступе к одному из ее членов. Это влечет за собой то, что структуры нельзя присваивать или копировать как целое, и что они не могут быть переданы функциям или возвращены ими. (В последующих версиях эти ограничения будут сняты). На указа- тели структур эти ограничения однако не накладываются, так что структуры и функции все же могут с удобством работать совместно. И наконец, автоматические структуры, как и авто- матические массивы, не могут быть инициализированы; инициа- лизация возможна только в случае внешних или статических структур. Давайте разберем некоторые из этих вопросов, переписав с этой целью функции перобразования даты из предыдущей главы так, чтобы они использовали структуры. Так как правила зап- рещают непосредственную передачу структуры функции, то мы должны либо передавать отдельно компоненты, либо передать указатель всей структуры. Первая возможность демонстрируется на примере функции DAY_OF_YEAR, как мы ее написали в главе 5: D.YEARDAY = DAY_OF_YEAR(D.YEAR, D.MONTH, D.DAY); другой способ состоит в передаче указателя. если мы опишем HIREDATE как STRUCT DATE HIREDATE; и перепишем DAY_OF_YEAR нужным образом, мы сможем тогда на- писать HIREDATE YEARDAY = DAY_OF_YEAR(&HIREDATE); передавая указатель на HIREDATE функции DAY_OF_YEAR . Функ- ция должна быть модифицирована, потому что ее аргумент те- перь является указателем, а не списком переменных. DAY_OF_YEAR(PD) /* SET DAY OF YEAR FROM MONTH, DAY */ STRUCT DATE *PD; \( INT I, DAY, LEAP; DAY = PD->DAY; LEAP = PD->YEAR % 4 == 0 && PD->YEAR % 100 != 0 \!\! PD->YEAR % 400 == 0; FOR (I =1; I < PD->MONTH; I++) DAY += DAY_TAB[LEAP][I]; RETURN(DAY); \) Описание STRUCT DATE *PD; говорит, что PD является указателем структуры типа DATE. Запись, показанная на примере PD->YEAR является новой. Если P - указатель на структуру, то P-> член структуры ------------------ обращается к конкретному члену. (Операция -> - это знак ми- нус, за которым следует знак ">".) Так как PD указывает на структуру, то к члену YEAR можно обратиться и следующим образом (*PD).YEAR но указатели структур используются настолько часто, что за- пись -> оказывается удобным сокращением. Круглые скобки в (*PD).YEAR необходимы, потому что операция указания члена стуктуры старше , чем * . Обе операции, "->" и ".", ассоции- руются слева направо, так что конструкции слева и справа зквивалентны P->Q->MEMB (P->Q)->MEMB EMP.BIRTHDATE.MONTH (EMP.BIRTHDATE).MONTH Для полноты ниже приводится другая функция, MONTH_DAY, пере- писанная с использованием структур. MONTH_DAY(PD) /* SET MONTH AND DAY FROM DAY OF YEAR */ STRUCT DATE *PD; \( INT I, LEAP; LEAP = PD->YEAR % 4 == 0 && PD->YEAR % 100 != 0 \!\! PD->YEAR % 400 == 0; PD->DAY = PD->YEARDAY; FOR (I = 1; PD->DAY > DAY_TAB[LEAP][I]; I++) PD->DAY -= DAY_TAB[LEAP][I]; PD->MONTH = I; \) Операции работы со структурами "->" и "." наряду со () для списка аргументов и [] для индексов находятся на самом верху иерархии страшинства операций и, следовательно, связы- ваются очень крепко. Если, например, имеется описание STRUCT \( INT X; INT *Y; \) *P; то выражение ++P->X увеличивает х, а не р, так как оно эквивалентно выражению ++(P->х). Для изменения порядка выполнения операций можно использовать круглые скобки: (++P)->х увеличивает P до дос- тупа к х, а (P++)->X увеличивает P после. (круглые скобки в последнем случае необязательны. Почему ?) Совершенно аналогично *P->Y извлекает то, на что указы- вает Y; *P->Y++ увеличивает Y после обработки того, на что он указывает (точно так же, как и *S++); (*P->Y)++ увеличи- вает то, на что указывает Y; *P++->Y увеличивает P после вы- борки того, на что указывает Y. 6.3. Массивы сруктур Структуры особенно подходят для управления массивами связанных переменных. Рассмотрим, например, программу подс- чета числа вхождений каждого ключевого слова языка "C". Нам нужен массив символьных строк для хранения имен и массив це- лых для подсчета. одна из возможностей состоит в использова- нии двух параллельных массивов KEYWORD и KEYCOUNT: CHAR *KEYWORD [NKEYS]; INT KEYCOUNT [NKEYS]; Но сам факт, что массивы параллельны, указывает на возмож- ность другой организации. Каждое ключевое слово здесь по су- ществу является парой: CHAR *KEYWORD; INT KEYCOUNT; и, следовательно, имеется массив пар. Описание структуры STRUCT KEY \( CHAR *KEYWORD; INT KEYCOUNT; \) KEYTAB [NKEYS]; оперделяет массив KEYTAB структур такого типа и отводит для них память. Каждый элемент массива является структурой. Это можно было бы записать и так: STRUCT KEY \( CHAR *KEYWORD; INT KEYCOUNT; \); STRUCT KEY KEYTAB [NKEYS]; Так как структура KEYTAB фактически содержит постоянный набор имен, то легче всего инициализировать ее один раз и для всех членов при определении. Инициализация структур вполне аналогична предыдущим инициализациям - за определени- ем следует заключенный в фигурные скобки список инициализа- торов: STRUCT KEY \( CHAR *KEYWORD; INT KEYCOUNT; \) KEYTAB[] =\( "BREAK", 0, "CASE", 0, "CHAR", 0, "CONTINUE", 0, "DEFAULT", 0, /* ... */ "UNSIGNED", 0, "WHILE", 0 \); Инициализаторы перечисляются парами соответственно членам структуры. Было бы более точно заключать в фигурные скобки инициализаторы для каждой "строки" или структуры следующим образом: \( "BREAK", 0 \), \( "CASE", 0 \), . . . Но когда инициализаторы являются простыми переменными или символьными строками и все они присутствуют, то во внутрен- них фигурных скобках нет необходимости. Как обычно, компиля- тор сам вычислит число элементов массива KEYTAB, если иници- ализаторы присутствуют, а скобки [] оставлены пустыми. Программа подсчета ключевых слов начинается с определе- ния массива KEYTAB. ведущая программа читает свой файл вво- да, последовательно обращаясь к функции GETWORD, которая из- влекает из ввода по одному слову за обращение. Каждое слово ищется в массиве KEYTAB с помощью варианта функции бинарного поиска, написанной нами в главе 3. (Конечно, чтобы эта функ- ция работала, список ключевых слов должен быть расположен в порядке возрастания). #DEFINE MAXWORD 20 MAIN() /* COUNT "C" KEYWORDS */ \( INT N, T; CHAR WORD[MAXWORD]; WHILE ((T = GETWORD(WORD,MAXWORD)) != EOF) IF (T == LETTER) IF((N = BINARY(WORD,KEYTAB,NKEYS)) >= 0) KEYTAB[N].KEYCOUNT++; FOR (N =0; N < NKEYS; N++) IF (KEYTAB[N].KEYCOUNT > 0) PRINTF("%4D %S\N", KEYTAB[N].KEYCOUNT, KEYTAB[N].KEYWORD); \) BINARY(WORD, TAB, N) /* FIND WORD IN TAB[0]...TAB[N-1] */ CHAR *WORD; STRUCT KEY TAB[]; INT N; \( INT LOW, HIGH, MID, COND; LOW = 0; HIGH = N - 1; WHILE (LOW <= HIGH) \( MID = (LOW+HIGH) / 2; IF((COND = STRCMP(WORD, TAB[MID].KEYWORD)) < 0) HIGH = MID - 1; ELSE IF (COND > 0) LOW = MID + 1; ELSE RETURN (MID); \) RETURN(-1); \) Мы вскоре приведем функцию GETWORD; пока достаточно сказать, что она возвращает LETTER каждый раз, как она находит слово, и копирует это слово в свой первый аргумент. Величина NKEYS - это количество ключевых слов в массиве KEYTAB . Хотя мы можем сосчитать это число вручную, гораздо легче и надежнее поручить это машине, особенно в том случае, если список ключевых слов подвержен изменениям. Одной из возможностей было бы закончить список инициализаторов указа- нием на нуль и затем пройти в цикле сквозь массив KEYTAB, пока не найдется конец. Но, поскольку размер этого массива полностью определен к моменту компиляции, здесь имеется более простая возможность. Число элементов просто есть SIZE OF KEYTAB / SIZE OF STRUCT KEY дело в том, что в языке "C" предусмотрена унарная операция SIZEOF, выполняемая во время компиляции, которая позволяет вычислить размер любого объекта. Выражение SIZEOF(OBJECT) выдает целое, равное размеру указанного объекта. (Размер оп- ределяется в неспецифицированных единицах, называемых "бай- тами", которые имеют тот же размер, что и переменные типа CHAR). Объект может быть фактической переменной, массивом и структурой, или именем основного типа, как INT или DOUBLE, или именем производного типа, как структура. В нашем случае число ключевых слов равно размеру массива, деленному на раз- мер одного элемента массива. Это вычисление используется в утверждении #DEFINE для установления значения NKEYS: #DEFINE NKEYS (SIZEOF(KEYTAB) / SIZEOF(STRUCT KEY)) Теперь перейдем к функции GETWORD. Мы фактически написа- ли более общий вариант функции GETWORD, чем необходимо для этой программы, но он не на много более сложен. Функция GETWORD возвращает следующее "слово" из ввода, где словом считается либо строка букв и цифр, начинающихся с буквы, ли- бо отдельный символ. Тип объекта возвращается в качетве зна- чения функции; это - LETTER, если найдено слово, EOF для конца файла и сам символ, если он не буквенный. GETWORD(W, LIM) /* GET NEXT WORD FROM INPUT */ CHAR *W; INT LIM; \( INT C, T; IF (TYPE(C=*W++=GETCH()) !=LETTER) \( *W='\0'; RETURN(C); \) WHILE (--LIM > 0) \( T = TYPE(C = *W++ = GETCH()); IF (T ! = LETTER && T ! = DIGIT) \( UNGETCH(C); BREAK; \) \) *(W-1) - '\0'; RETURN(LETTER); \) Функция GETWORD использует функции GETCH и UNGETCH, которые мы написали в главе 4: когда набор алфавитных символов пре- рывается, функция GETWORD получает один лишний символ. В ре- зультате вызова UNGETCH этот символ помещается назад во ввод для следующего обращения. Функция GETWORD обращается к функции TYPE для определе- ния типа каждого отдельного символа из файла ввода. Вот ва- риант, справедливый только для алфавита ASCII. TYPE(C) /* RETURN TYPE OF ASCII CHARACTER */ INT C; \( IF (C>= 'A' && C<= 'Z' \!\! C>= 'A' && C<= 'Z') RETURN(LETTER); ELSE IF (C>= '0' && C<= '9') RETURN(DIGIT); ELSE RETURN(C); \) Символические константы LETTER и DIGIT могут иметь любые значения, лишь бы они не вступали в конфликт с символами, отличными от буквенно-цифровых, и с EOF; очевидно возможен следующий выбор #DEFINE LETTER 'A' #DEFINE DIGIT '0' функция GETWORD могла бы работать быстрее, если бы обращения к функции TYPE были заменены обращениями к соответствующему массиву TYPE[ ]. В стандартной библиотеке языка "C" предус- мотрены макросы ISALPHA и ISDIGIT, действующие необходимым образом. Упражнение 6-1 -------------- Сделайте такую модификацию функции GETWORD и оцените, как изменится скорость работы программы. Упражнение 6-2 -------------- Напишите вариант функции TYPE, не зависящий от конкрет- ного наборасимволов. Упражнение 6-3 -------------- Напишите вариант программы подсчета ключевых слов, кото- рый бы не учитывал появления этих слов в заключенных в ка- вычки строках. 6.4. Указатели на структуры Чтобы проиллюстрировать некоторые соображения, связанные с использованием указателей и массивов структур, давайте снова составим программу подсчета ключевых строк, используя на этот раз указатели, а не индексы массивов. Внешнее описание массива KEYTAB не нужно изменять, но функции MAIN и BINARY требуют модификации. MAIN() /* COUNT C KEYWORD; POINTER VERSION */ \( INT T; CHAR WORD[MAXWORD]; STRUCT KEY *BINARY(), *P; WHILE ((T = GETWORD(WORD, MAXWORD;) !=EOF) IF (T==LETTER) IF ((P=BINARY(WORD,KEYTAB,NKEYS)) !=NULL) P->KEYCOUNT++; FOR (P=KEYTAB; P>KEYTAB + NKEYS; P++) IF (P->KEYCOUNT > 0) PRINTF("%4D %S/N", P->KEYCOUNT, P->KEYWORD); \) STRUCT KEY *BINARY(WORD, TAB, N) /* FIND WORD */ CHAR *WORD /* IN TAB[0]...TAB[N-1] */ STRUCT KEY TAB []; INT N; \( INT COND; STRUCT KEY *LOW = &TAB[0]; STRUCT KEY *HIGH = &TAB[N-1]; STRUCT KEY *MID; WHILE (LOW <= HIGH) \( MID = LOW + (HIGH-LOW) / 2; IF ((COND = STRCMP(WORD, MID->KEYWORD)) < 0) HIGH = MID - 1; ELSE IF (COND > 0) LOW = MID + 1; ELSE RETURN(MID); \) RETURN(NULL); \) Здесь имеется несколько моментов, которые стоит отме- тить. Во-первых, описание функции BINARI должно указывать, что она возвращает указатель на структуру типа KEY, а не на целое; это объявляется как в функции MAIN, так и в BINARY. Если функция BINARI находит слово, то она возвращает указа- тель на него; если же нет, она возвращает NULL. Во-вторых, все обращения к элементам массива KEYTAB осу- ществляются через указатели. Это влечет за собой одно сущес- твенное изменение в функции BINARY: средний элемент больше нельзя вычислять просто по формуле MID = (LOW + HIGH) / 2 потому что сложение двух указателей не дает какого-нибудь полезного результата (даже после деления на 2) и в действи- тельности является незаконным. эту формулу надо заменить на MID = LOW + (HIGH-LOW) / 2 в результате которой MID становится указателем на элемент, расположенный посередине между LOW и HIGH. Вам также следует разобраться в инициализации LOW и HIGH. указатель можно инициализировать адресом ранее опреде- ленного объекта; именно как мы здесь и поступили. В функции MAIN мы написали FOR (P=KEYTAB; P < KEYTAB + NKEYS; P++) Если P является указателем структуры, то любая арифметика с P учитывает фактический размер данной структуры, так что P++ увеличивает P на нужную величину, в результате чего P указы- вает на следующий элемент массива структур. Но не считайте, что размер структуры равен сумме размеров ее членов, - из-за требований выравнивания для различных объектов в структуре могут возникать "дыры". И, наконец, несколько второстепенный вопрос о форме за- писи программы. Если возвращаемая функцией величина имеет тип, как, например, в STRUCT KEY *BINARY(WORD, TAB, N) Tо может оказаться, что имя функции трудно выделить среди текста. В связи с этим иногда используется другой стиль за- писи: STRUCT KEY * BINARY(WORD, TAB, N) Это главным образом дело вкуса; выберите ту форму, которая вам нравится, и придерживайтесь ее. 6.5. Структуры, ссылающиеся на себя Предположим, что нам надо справиться с более общей зада- чей, состоящей в подсчете числа появлений всех слов в неко- тором файле ввода. Так как список слов заранее не известен, мы не можем их упорядочить удобным образом и использовать бинарный поиск. Мы даже не можем осуществлять последователь- ный просмотр при поступлении каждого слова, с тем чтобы ус- тановить, не встречалось ли оно ранее; такая программа будет работать вечно. (Более точно, ожидаемое время работы растет как квадрат числа вводимых слов). Как же нам организовать программу, чтобы справиться со списком произвольных слов? Одно из решений состоит в том, чтобы все время хранить массив поступающих до сих пор слов в упорядоченном виде, по- мещая каждое слово в нужное место по мере их поступления. OДнако это не следует делать, перемещая слова в линейном массиве, - это также потребует слишком много времени. Вместо этого мы используем структуру данных, называемую доичным де- ревом. Каждому новому слову соответствует один "узел" дерева; каждый узел содержит: указатель текста слова ---------------------- счетчик числа появлений ----------------------- указатель узла левого потомка ----------------------------- указатель узла правого потомка ------------------------------ Никакой узел не может иметь более двух детей; возможно от- сутсвие детей или наличие только одного потомка. Узлы создаются таким образом, что левое поддерево каждо- го узла содержит только те слова, которые меньше слова в этом узле, а правое поддерево только те слова, которые боль- ше. Чтобы определить, находится ли новое слово уже в дереве, начинают с корня и сравнивают новое слово со словом, храня- щимся в этом узле. Если слова совпадают, то вопрос решается утвердительно. Если новое слово меньше слова в дереве, то переходят к рассмотрению левого потомка; в противном случае исследуется правый потомок. Если в нужном направлении пото- мок отсутствует, то значит новое слово не находится в дереве и место этого недостающего потомка как раз и является мес- том, куда следует поместить новое слово. Поскольку поиск из любого узла приводит к поиску одного из его потомков, то сам процесс поиска по существу является рекурсивным. В соответс- твии с этим наиболее естественно использовать рекурсивные процедуры ввода и вывода. Возвращаясь назад к описанию узла, ясно, что это будет структура с четырьмя компонентами: STRUCT TNODE \( /* THE BASIC NODE */ CHAR *WORD; /* POINTS TO THE TEXT */ INT COUNT; /* NUMBER OF OCCURRENCES */ STRUCT TNODE *LEFT; /* LEFT CHILD */ STRUCT TNODE *RIGHT; /* RIGHT CHILD */ \); Это "рекурсивное" описание узла может показаться рискован- ным, но на самом деле оно вполне корректно. Структура не имеет права содержать ссылку на саму себя, но STRUCT TNODE *LEFT; описывает LEFT как указатель на узел, а не как сам узел. Текст самой программы оказывается удивительно маленьким, если, конечно, иметь в распоряжении набор написанных нами ранее процедур, обеспечивающих нужные действия. Мы имеем в виду функцию GETWORD для извлечения каждого слова из файла ввода и функцию ALLOC для выделения места для хранения слов. Ведущая программа просто считывает слова с помощью функ- ции GETWORD и помещает их в дерево, используя функцию TREE. #DEFINE MAXWORD 20 MAIN() /* WORD FREGUENCY COUNT */ \( STRUCT TNODE *ROOT, *TREE(); CHAR WORD[MAXWORD]; INT T; ROOT = NULL; WHILE ((T = GETWORD(WORD, MAXWORD)) \! = EOF) IF (T == LETTER) ROOT = TREE(ROOT, WORD); TREEPRINT(ROOT); \) Функция TREE сама по себе проста. Слово передается функ- цией MAIN к верхнему уровню (корню) дерева. На каждом этапе это слово сравнивается со словом, уже хранящимся в этом уз- ле, и с помощью рекурсивного обращения к TREE просачивается вниз либо к левому, либо к правому поддереву. В конце концов это слово либо совпадает с каким-то словом, уже находящимся в дереве (в этом случае счетчик увеличивается на единицу), либо программа натолкнется на нулевой указатель, свидетель- ствующий о необходимости создания и добавления к дереву но- вого узла. В случае создания нового узла функция TREE возв- ращает указатель этого узла, который помещается в родитель- ский узел. STRUCT TNODE *TREE(P, W) /* INSTALL W AT OR BELOW P */ STRUCT TNODE *P; CHAR *W; \( STRUCT TNODE *TALLOC(); CHAR *STRSAVE(); INT COND; IF (P == NULL) \( /* A NEW WORD HAS ARRIVED */ P == TALLOC(); /* MAKE A NEW NODE */ P->WORD = STRSAVE(W); P->COUNT = 1; P->LEFT = P->RIGHT = NULL; \) ELSE IF ((COND = STRCMP(W, P->WORD)) == 0) P->COUNT++; /* REPEATED WORD */ ELSE IF (COND < 0)/* LOWER GOES INTO LEFT SUBTREE */ P->LEFT = TREE(P->LEFT, W); ELSE /* GREATER INTO RIGHT SUBTREE */ P->RIGHT = TREE(P->RIGHT, W); RETURN(P); \) Память для нового узла выделяется функцией TALLOC, явля- ющейся адаптацией для данного случая функции ALLOC, написан- ной нами ранее. Она возвращает указатель свободного прост- ранства, пригодного для хранения нового узла дерева. (Мы вскоре обсудим это подробнее). Новое слово копируется функ- цией STRSAVE в скрытое место, счетчик инициализируется еди- ницей, и указатели обоих потомков полагаются равными нулю. Эта часть программы выполняется только при добавлении нового узла к ребру дерева. Мы здесь опустили проверку на ошибки возвращаемых функций STRSAVE и TALLOC значений (что неразум- но для практически работающей программы). Функция TREEPRINT печатает дерево, начиная с левого под- дерева; в каждом узле сначала печатается левое поддерево (все слова, которые младше этого слова), затем само слово, а затем правое поддерево (все слова, которые старше). Если вы неуверенно оперируете с рекурсией, нарисуйте дерево сами и напечатайте его с помощью функции TREEPRINT ; это одна из наиболее ясных рекурсивных процедур, которую можно найти. TREEPRINT (P) /* PRINT TREE P RECURSIVELY */ STRUCT TNODE *P; \( IF (P != NULL) \( TREEPRINT (P->LEFT); PRINTF("%4D %S\N", P->COUNT, P->WORD); TREEPRINT (P->RIGHT); \) \) Практическое замечание: если дерево становится "несба- лансированным" из-за того, что слова поступают не в случай- ном порядке, то время работы программы может расти слишком быстро. В худшем случае, когда поступающие слова уже упоря- дочены, настоящая программа осуществляет дорогостоящую ими- тацию линейного поиска. Существуют различные обобщения дво- ичного дерева, особенно 2-3 деревья и AVL деревья, которые не ведут себя так "в худших случаях", но мы не будем здесь на них останавливаться. Прежде чем расстаться с этим примером, уместно сделать небольшое отступление в связи с вопросом о распределении па- мяти. Ясно, что в программе желательно иметь только один распределитель памяти, даже если ему приходится размещать различные виды объектов. Но если мы хотим использовать один распределитель памяти для обработки запросов на выделение памяти для указателей на переменные типа CHAR и для указате- лей на STRUCT TNODE, то при этом возникают два вопроса. Пер- вый: как выполнить то существующее на большинстве реальных машин ограничение, что объекты определенных типов должны удовлетворять требованиям выравнивания (например, часто це- лые должны размещаться в четных адресах)? Второй: как орга- низовать описания, чтобы справиться с тем, что функция ALLOC должна возвращать различные виды указателей ? Вообще говоря, требования выравнивания легко выполнить за счет выделения некоторого лишнего пространства, просто обеспечив то, чтобы распределитель памяти всегда возвращал указатель, удовлетворяющий всем ограничениям выравнивания. Например, на PDP-11 достаточно, чтобы функция ALLOC всегда возвращала четный указатель, поскольку в четный адрес можно поместить любой тип объекта. единственный расход при этом - лишний символ при запросе на нечетную длину. Аналогичные действия предпринимаются на других машинах. Таким образом, реализация ALLOC может не оказаться переносимой, но ее ис- пользование будет переносимым. Функция ALLOC из главы 5 не предусматривает никакого определенного выравнивания; в главе 8 мы продемонстрируем, как правильно выполнить эту задачу. Вопрос описания типа функции ALLOC является мучительным для любого языка, который серьезно относится к проверке ти- пов. Лучший способ в языке "C" - объявить, что ALLOC возвра- щает указатель на переменную типа CHAR, а затем явно преоб- разовать этот указатель к желаемому типу с помощью операции перевода типов. Таким образом, если описать P в виде CHAR *P; то (STRUCT TNODE *) P преобразует его в выражениях в указатель на структуру типа TNODE . Следовательно, функцию TALLOC можно записать в виде: STRUCT TNODE *TALLOC() \( CHAR *ALLOC(); RETURN ((STRUCT TNODE *) ALLOC(SIZEOF(STRUCT TNODE))); \) это более чем достаточно для работающих в настоящее время компиляторов, но это и самый безопасный путь с учетом будую- щего. Упражнение 6-4 ---------------- Напишите программу, которая читает "C"-программу и печа- тает в алфавитном порядке каждую группу имен переменных, ко- торые совпадают в первых семи символах, но отличаются где-то дальше. (Сделайте так, чтобы 7 было параметром). Упражнение 6-5 ---------------- Напишите программу выдачи перекрестных ссылок, т.е. Программу, которая печатает список всех слов документа и для каждого из этих слов печатает список номеров строк, в кото- рые это слово входит. Упражнение 6-6 ---------------- Напишите программу, которая печатает слова из своего файла ввода, расположенные в порядке убывания частоты их по- явления. Перед каждым словом напечатайте число его появле- ний. 6.6. Поиск в таблице Для иллюстрации дальнейших аспектов использования струк- тур в этом разделе мы напишем программу, представляющую со- бой содержимое пакета поиска в таблице. Эта программа явля- ется типичным представителем подпрограмм управления символь- ными таблицами макропроцессора или компилятора. Рассмотрим, например, оператор #DEFINE языка "C". Когда встречается строка вида #DEFINE YES 1 то имя YES и заменяющий текст 1 помещаются в таблицу. Позд- нее, когда имя YES появляется в операторе вида INWORD = YES; Oно должно быть замещено на 1. Имеются две основные процедуры, которые управляют имена- ми и заменяющими их текстами. Функция INSTALL(S,T) записыва- ет имя S и заменяющий текст T в таблицу; здесь S и T просто символьные строки. Функция LOOKUP(S) ищет имя S в таблице и возвращает либо указатель того места, где это имя найдено, либо NULL, если этого имени в таблице не оказалось. При этом используется поиск по алгоритму хеширования - поступающее имя преобразуется в маленькое положительное чис- ло, которое затем используется для индексации массива указа- телей. Элемент массива указывает на начало цепочных блоков, описывающих имена, которые имеют это значение хеширования. Если никакие имена при хешировании не получают этого значе- ния, то элементом массива будет NULL. Блоком цепи является структура, содержащая указатели на соответствующее имя, на заменяющий текст и на следующий блок в цепи. Нулевой указатель следующего блока служит признаком конца данной цепи. STRUCT NLIST \( /* BASIC TABLE ENTRY */ CHAR *NAME; CHAR *DEF; STRUCT NLIST *NEXT; /* NEXT ENTRY IN CHAIN */ \); Массив указателей это просто DEFINE HASHSIZE 100 TATIC STRUCT NLIST *HASHTAB[HASHSIZE] /* POINTER TABLE */ Значение функции хеширования, используемой обеими функ- циями LOOKUP и INSTALL , получается просто как остаток от деления суммы символьных значений строки на размер массива. (Это не самый лучший возможный алгоритм, но его достоинство состоит в исключительной простоте). HASH(S) /* FORM HASH VALUE FOR STRING */ CHAR *S; \( INT HASHVAL; FOR (HASHVAL = 0; *S != '\0'; ) HASHVAL += *S++; RETURN(HASHVAL % HASHSIZE); \) В результате процесса хеширования выдается начальный ин- декс в массиве HASHTAB ; если данная строка может быть где-то найдена, то именно в цепи блоков, начало которой ука- зано там. Поиск осуществляется функцией LOOKUP. Если функция LOOKUP находит, что данный элемент уже присутствует, то она возвращает указатель на него; если нет, то она возвращает NULL. STRUCT NLIST *LOOKUP(S) /* LOOK FOR S IN HASHTAB */ CHAR *S; \( STRUCT NLIST *NP; FOR (NP = HASHTAB[HASH(S)]; NP != NULL;NP=NP->NEXT) IF (STRCMP(S, NP->NAME) == 0) RETURN(NP); /* FOUND IT */ RETURN(NULL); /* NOT FOUND */ Функция INSTALL использует функцию LOOKUP для определе- ния, не присутствует ли уже вводимое в данный момент имя; если это так, то новое определение должно вытеснить старое. В противном случае создается совершенно новый элемент. Если по какой-либо причине для нового элемента больше нет места, то функция INSTALL возвращает NULL. STRUCT NLIST *INSTALL(NAME, DEF) /* PUT (NAME, DEF) */ CHAR *NAME, *DEF; \( STRUCT NLIST *NP, *LOOKUP(); CHAR *STRSAVE(), *ALLOC(); INT HASHVAL; IF((NP = LOOKUP(NAME)) == NULL) \( /* NOT FOUND */ NP = (STRUCT NLIST *) ALLOC(SIZEOF(*NP)); IF (NP == NULL) RETURN(NULL); IF ((NP->NAME = STRSAVE(NAME)) == NULL) RETURN(NULL); HASHVAL = HASH(NP->NAME); NP->NEXT = HASHTAB[HASHVAL]; HASHTAB[HASHVAL] = NP; \) ELSE /* ALREADY THERE */ FREE((NP->DEF);/* FREE PREVIOUS DEFINITION */ IF ((NP->DEF = STRSAVE(DEF)) == NULL) RETURN (NULL); RETURN(NP); \) Функция STRSAVE просто копирует строку, указанную в ка- честве аргумента, в место хранения, полученное в результате обращения к функции ALLOC. Мы уже привели эту функцию в гла- ве 5. Так как обращение к функции ALLOC и FREE могут проис- ходить в любом порядке и в связи с проблемой выравнивания, простой вариант функции ALLOC из главы 5 нам больше не под- ходит; смотрите главы 7 и 8. Упражнение 6-7 --------------- Напишите процедуру, которая будет удалять имя и опреде- ление из таблицы, управляемой функциями LOOKUP и INSTALL. Упражнение 6-8 --------------- Разработайте простую, основанную на функциях этого раз- дела, версию процессора для обработки конструкций #DEFINE , пригодную для использования с "C"-программами. Вам могут также оказаться полезными функции GETCHAR и UNGETCH. 6.7. Поля Когда вопрос экономии памяти становится очень существен- ным, то может оказаться необходимым помещать в одно машинное слово несколько различных объектов; одно из особенно расп- росраненных употреблений - набор однобитовых признаков в применениях, подобных символьным таблицам компилятора. внеш- не обусловленные форматы данных, такие как интерфейсы аппа- ратных средств также зачастую предполагают возможность полу- чения слова по частям. Представьте себе фрагмент компилятора, который работает с символьной таблицей. С каждым идентификатором программы связана определенная информация, например, является он или нет ключевым словом, является ли он или нет внешним и/или статическим и т.д. Самый компактный способ закодировать та- кую информацию - поместить набор однобитовых признаков в от- дельную переменную типа CHAR или INT. Обычный способ, которым это делается, состоит в опреде- лении набора "масок", отвечающих соответствущим битовым по- зициям, как в #DEFINE KEYWORD 01 #DEFINE EXTERNAL 02 #DEFINE STATIC 04 (числа должны быть степенями двойки). Тогда обработка битов сведется к "жонглированию битами" с помощью операций сдвига, маскирования и дополнения, описанных нами в главе 2. Некоторые часто встречающиеся идиомы: FLAGS \!= EXTERNAL \! STATIC; включает биты EXTERNAL и STATIC в FLAGS, в то время как FLAGS &= \^(еXTERNAL \! STATIC); их выключает, а IF ((FLAGS & (EXTERNAL \! STATIC)) == 0) ... истинно, если оба бита выключены. Хотя этими идиомами легко овладеть, язык "C" в качестве альтернативы предлагает возможность определения и обработки полей внутри слова непосредственно, а не посредством побито- вых логических операций. Поле - это набор смежных битов внутри одной переменной типа INT. Синтаксис определения и обработки полей основывается на структурах. Например, сим- вольную таблицу конструкций #DEFINE, приведенную выше, можно бы было заменить определением трех полей: STRUCT \( UNSIGNED IS_KEYWORD : 1; UNSIGNED IS_EXTERN : 1; UNSIGNED IS_STATIC : 1; \) FLAGS; Здесь определяется переменная с именем FLAGS, которая содер- жит три 1-битовых поля. Следующее за двоеточием число задает ширину поля в битах. Поля описаны как UNSIGNED, чтобы под- черкнуть, что они действительно будут величинами без знака. На отдельные поля можно ссылаться, как FLAGS.IS_STATIE, FLAGS. IS_EXTERN, FLAGS.IS_KEYWORD И т.д., то есть точно так же, как на другие члены структуры. Поля ведут себя подобно небольшим целым без знака и могут участвовать в арифметичес- ких выражениях точно так же, как и другие целые. Таким обра- зом, предыдущие примеры более естественно переписать так: FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 1; для включения битов; FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 0; для выключения битов; IF (FLAGS.IS_EXTERN == 0 &&FLAGS.IS_STATIC == 0)... для их проверки. Поле не может перекрывать границу INT; если указанная ширина такова, что это должно случиться, то поле выравнива- ется по границе следующего INT. Полям можно не присваивать имена; неименованные поля (только двоеточие и ширина) ис- пользуются для заполнения свободного места. Чтобы вынудить выравнивание на границу следующего INT, можно использовать специальную ширину 0. При работе с полями имеется ряд моментов, на которые следует обратить внимание. По-видимому наиболее существенным является то, что отражая природу различных аппаратных сред- ств, распределение полей на некоторых машинах осуществляется слева направо, а на некоторых справа налево. Это означает, что хотя поля очень полезны для работы с внутренне опреде- ленными структурами данных, при разделении внешне определяе- мых данных следует тщательно рассматривать вопрос о том, ка- кой конец поступает первым. Другие ограничения, которые следует иметь в виду: поля не имеют знака; они могут храниться только в переменных типа INT (или, что эквивалентно, типа UNSIGNED); они не являются массивами; они не имеют адресов, так что к ним не применима операция &. 6.8. Объединения Oбъединения - это переменная, которая в различные момен- ты времени может содержать объекты разных типов и размеров, причем компилятор берет на себя отслеживание размера и тре- бований выравнивания. Объединения представляют возможность работать с различными видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой информации. В качестве примера, снова из символьной таблицы компиля- тора, предположим, что константы могут быть типа INT , FLOAT или быть указателями на символы. значение каждой конкретной константы должно храниться в переменной соотвествующего ти- па, но все же для управления таблицей самым удобным было бы, если это значение занимало бы один и тот же объем памяти и хранилось в том же самом месте независимо от его типа. это и является назначением объединения - выделить отдельную пере- менную, в которой можно законно хранить любую одну из пере- менных нескольких типов. Как и в случае полей, синтаксис ос- новывается на структурах. UNION U_TAG \( INT IVAL; FLOAT FVAL; CHAR *PVAL; \) UVAL; Переменная UVAL будет иметь достаточно большой размер,чтобы хранить наибольший из трех типов, независимо от машины, на которой осуществляется компиляция, - программа не будет за- висить от характеристик аппаратных средств. Любой из этих трех типов может быть присвоен UVAR и затем использован в выражениях, пока такое использование совместимо: извлекаемый тип должен совпадать с последним помещенным типом. Дело программиста - следить за тем, какой тип хранится в объеди- нении в данный момент; если что-либо хранится как один тип, а извлекается как другой, то результаты будут зависеть от используемой машины. Синтаксически доступ к членам объединения осуществляется следующим образом: имя объединения.член -------------------- или указатель объединения ->член ---------------------------- то есть точно так же, как и в случае структур. если для отс- леживания типа, хранимого в данный момент в UVAL, использу- ется переменная UTYPE, то можно встретить такой участок программы: IF (UTYPE == INT) PRINTF("%D\N", UVAL.IVAL); ELSE IF (UTYPE == FLOAT) PRINTF("%F\N", UVAL.FVAL); ELSE IF (UTYPE == STRING) PRINTF("%S\N", UVAL.PVAL); ELSE PRINTF("BAD TYPE %D IN UTYPE\N", UTYPE); Объединения могут появляться внутри структур и массивов и наоборот. Запись для обращения к члену объединения в структуре (или наоборот) совершенно идентична той, которая используется во вложенных структурах. например, в массиве структур, определенным следующим образом STRUCT \( CHAR *NAME; INT FLAGS; INT UTYPE; UNION \( INT IVAL; FLOAT FVAL; CHAR *PVAL; \) UVAL; \) SYMTAB[NSYM]; на переменную IVAL можно сослаться как SYMTAB[I].UVAL.IVAL а на первый символ строки PVAL как *SYMTAB[I].UVAL.PVAL В сущности объединение является структурой, в которой все члены имеют нулевое смещение. Сама структура достаточно ве- лика, чтобы хранить "самый широкий" член, и выравнивание пригодно для всех типов, входящих в объединение. Как и в случае структур, единственными операциями, которые в настоя- щее время можно проводить с объединениями, являются доступ к члену и извлечение адреса; объединения не могут быть присво- ены, переданы функциям или возвращены ими. указатели объеди- нений можно использовать в точно такой же манере, как и ука- затели структур. Программа распределения памяти, приводимая в главе 8 , показывает, как можно использовать объединение, чтобы сде- лать некоторую переменную выровненной по определенному виду границы памяти. 6.9. Определение типа В языке "C" предусмотрена возможность, называемая TYPEDEF для введения новых имен для типов данных. Например, описание TYPEDEF INT LENGTH; делает имя LENGTH синонимом для INT. "Тип" LENGTH может быть использован в описаниях, переводов типов и т.д. Точно таким же образом, как и тип INT: LENGTH LEN, MAXLEN; LENGTH *LENGTHS[]; Аналогично описанию TYPEDEF CHAR *STRING; делает STRING синонимом для CHAR*, то есть для указателя на символы, что затем можно использовать в описаниях вида STRING P, LINEPTR[LINES], ALLOC(); Обратите внимание, что объявляемый в конструкции TYPEDEF тип появляется в позиции имени переменной, а не сразу за словом TYPEDEF. Синтаксически конструкция TYPEDEF подобна описаниям класса памяти EXTERN, STATIC и т. Д. мы также ис- пользовали прописные буквы, чтобы яснее выделить имена. В качестве более сложного примера мы используем конст- рукцию TYPEDEF для описания узлов дерева, рассмотренных ра- нее в этой главе: TYPEDEF STRUCT TNODE \( /* THE BASIC NODE */ CHAR *WORD; /* POINTS TO THE TEXT */ INT COUNT; /* NUMBER OF OCCURRENCES */ STRUCT TNODE *LEFT; /* LEFT CHILD */ STRUCT TNODE *RIGHT; /* RIGHT CHILD */ \) TREENODE, *TREEPTR; В результате получаем два новых ключевых слова: TREENODE (структура) и TREEPTR (указатель на структуру). Тогда функ- цию TALLOC можно записать в виде TREEPTR TALLOC() \( CHAR *ALLOC(); RETURN((TREEPTR) ALLOC(SIZEOF(TREENODE))); \) Необходимо подчеркнуть, что описание TYPEDEF не приводит к созданию нового в каком-либо смысле типа; оно только до- бавляет новое имя для некоторого существующего типа. при этом не возникает и никакой новой семантики: описанные таким способом переменные обладают точно теми же свойствами, что и переменные, описанные явным образом. По существу конструкция TYPEDEF сходна с #DEFINE за исключением того, что она интер- претируется компилятором и потому может осуществлять подста- новки текста, которые выходят за пределы возможностей мак- ропроцессора языка "C". Например, TYPEDEF INT (*PFI) (); создает тип PFI для "указателя функции, возвращающей значе- ние типа INT", который затем можно было бы использовать в программе сортировки из главы 5 в контексте вида PFI STRCMP, NUMCMP, SWAP; Имеются две основные причины применения описаний TYPEDEF. Первая причина связана с параметризацией программы, чтобы облегчить решение проблемы переносимости. Если для ти- пов данных, которые могут быть машинно-зависимыми, использо- вать описание TYPEDEF, то при переносе программы на другую машину придется изменить только эти описания. Одна из типич- ных ситуаций состоит в использовании определяемых с помощью TYPEDEF имен для различных целых величин и в последующем подходящем выборе типов SHORT, INT и LONG для каждой имею- щейся машины. Второе назначение TYPEDEF состоит в обеспечении лучшей доку- ментации для программы - тип с именем TREEPTR может оказать- ся более удобным для восприятия, чем тип, который описан только как указатель сложной структуры. И наконец, всегда существует вероятность, что в будущем ком- пилятор или некоторая другая программа, такая как LINT, смо- жет использовать содержащуюся в описаниях TYPEDEF информацию для проведения некоторой дополнительной проверки программы.  * 7. Ввод и вывод *  Средства ввода/вывода не являются составной частью языка "с", так что мы не выделяли их в нашем предыдущем изложении. Однако реальные программы взаимодействуют со своей окружаю- щей средой гораздо более сложным образом, чем мы видели до сих пор. В этой главе будет описана "стандартная библиотека ввода/вывода", то есть набор функций, разработанных для обеспечения стандартной системы ввода/вывода для "с"- прог- рамм. Эти функции предназначены для удобства программного интерфейса, и все же отражают только те операции, которые могут быть обеспечены на большинстве современных операцион- ных систем. Процедуры достаточно эффективны для того, чтобы пользователи редко чувствовали необходимость обойти их "ради эффективности", как бы ни была важна конкретная задача. И, наконец, эти процедуры задуманы быть "переносимыми" в том смысле, что они должны существовать в совместимом виде на любой системе, где имеется язык "с", и что программы, кото- рые ограничивают свои взаимодействия с системой возможностя- ми, предоставляемыми стандартной библиотекой, можно будет переносить с одной системы на другую по существу без измене- ний. Мы здесь не будем пытаться описать всю библиотеку вво- да/вывода; мы более заинтересованы в том, чтобы продемонст- рировать сущность написания "с"-программ, которые взаимодей- ствуют со своей операционной средой. 7.1. Обращение к стандартной библиотеке Каждый исходный файл, который обращается к функции из стандартной библиотеки, должен вблизи начала содержать стро- ку #INCLUDE <STDIO.H> в файле STDIO.H определяются некоторые макросы и переменные, используемые библиотекой ввода/вывода. Использование угловых скобок вместо обычных двойных кавычек - указание компилятору искать этот файл в справочнике, содержащем заголовки стан- дартной информации (на системе UNIX обычно LUSRLINELUDE). Кроме того, при загрузке программы может оказаться необ- ходимым указать библиотеку явно; на системе PDP-11 UNIX, например, команда компиляции программы имела бы вид: CC исходные файлы и т.д. -LS где -LS указывает на загрузку из стандартной библиотеки. 7.2. Стандартный ввод и вывод - функции GETCHAR и PUTCHAR Самый простой механизм ввода заключается в чтении по од- ному символу за раз из "стандартного ввода", обычно с терми- нала пользователя, с помощью функции GETCHAR. Функция GETCHAR() при каждом к ней обращении возвращает следующий вводимый символ. В большинстве сред, которые поддерживают язык "с", терминал может быть заменен некоторым файлом с по- мощью обозначения < : если некоторая программа PROG исполь- зует функцию GETCHAR то командная строка PROG<INFILE приведет к тому, что PROG будет читать из файла INFILE, а не с терминала. Переключение ввода делается таким образом, что сама программа PROG не замечает изменения; в частности стро- ка"<INFILE" не включается в командную строку аргументов в ARGV. Переключение ввода оказывается незаметным и в том слу- чае, когда вывод поступает из другой программы посредством поточного (PIPE) механизма; командная строка OTHERPROG \! PROG прогоняет две программы, OTHERPROG и PROG, и организует так, что стандартным вводом для PROG служит стандартный вывод OTHERPROG. Функция GETCHAR возвращает значение EOF, когда она попа- дает на конец файла, какой бы ввод она при этом не считыва- ла. Стандартная библиотека полагает символическую константу EOF равной -1 (посредством #DEFINE в файле STDIO.H), но про- верки следует писать в терминах EOF, а не -1, чтобы избежать зависимости от конкретного значения. Вывод можно осуществлять с помощью функции PUTCHAR(C), помещающей символ 'с' в "стандартный ввод", который по умол- чанию является терминалом. Вывод можно направить в некоторый файл с помощью обозначения > : если PROG использует PUTCHAR, то командная строка PROG>OUTFILE приведет к записи стандартного вывода в файл OUTFILE, а не на терминал. На системе UNIX можно также использовать поточ- ный механизм. Строка PROG \! ANOTHERPROG помещает стандартный вывод PROG в стандартный ввод ANOTHERPROG. И опять PROG не будет осведомлена об изменении направления. Вывод, осуществляемый функцией PRINTF, также поступает в стандартный вывод, и обращения к PUTCHAR и PRINTF могут пе- ремежаться. Поразительное количество программ читает только из одно- го входного потока и пишет только в один выходной поток; для таких программ ввод и вывод с помощью функций GETCHAR, PUTCHAR и PRINTF может оказаться вполне адекватным и для на- чала определенно достаточным. Это особенно справедливо тог- да, когда имеется возможность указания файлов для ввода и вывода и поточный механизм для связи вывода одной программы с вводом другой. Рассмотрим, например, программу LOWER, ко- торая преобразует прописные буквы из своего ввода в строч- ные: #INCLUDE <STDIO.H> MAIN() /* CONVERT INPUT TO LOWER CASE */ \( INT C; WHILE ((C = GETCHAR()) != EOF) PUTCHAR(ISUPPER(C) ? TOLOWER(C) : C); \) "Функции" ISUPPER и TOLOWER на самом деле являются макроса- ми, определенными в STDIO.H . Макрос ISUPPER проверяет, яв- ляется ли его аргумент буквой из верхнего регистра, и возв- ращает ненулевое значение, если это так, и нуль в противном случае. Макрос TOLOWER преобразует букву из верхнего регист- ра в ту же букву нижнего регистра. Независимо от того, как эти функции реализованы на конкретной машине, их внешнее по- ведение совершенно одинаково, так что использующие их прог- раммы избавлены от знания символьного набора. Если требуется преобразовать несколько файлов, то можно собрать эти файлы с помощью программы, подобной утилите CAT системы UNIX, CAT FILE1 FILE2 ... \! LOWER>OUTPUT и избежать тем самым вопроса о том, как обратиться к этим файлам из программы. (Программа CAT приводится позже в этой главе). Кроме того отметим, что в стандартной библиотеке вво- да/вывода "функции" GETCHAR и PUTCHAR на самом деле могут быть макросами. Это позволяет избежать накладных расходов на обращение к функции для обработки каждого символа. В главе 8 мы продемонстрируем, как это делается. 7.3. Форматный вывод - функция PRINTF Две функции: PRINTF для вывода и SCANF для ввода (следу- ющий раздел) позволяют преобразовывать численные величины в символьное представлEние и обратно. Они также позволяют ге- нерировать и интерпретировать форматные строки. Мы уже всюду в предыдущих главах неформально использовали функцию PRINTF; здесь приводится более полное и точное описание. Функция PRINTF(CONTROL, ARG1, ARG2, ...) преобразует, определяет формат и печатает свои аргументы в стандартный вывод под управлением строки CONTROL. Управляю- щая строка содержит два типа объектов: обычные символы, ко- торые просто копируются в выходной поток, и спецификации преобразований, каждая из которых вызывает преобразование и печать очередного аргумента PRINTF. Каждая спецификация преобразования начинается с символа % и заканчивается символом преобразования. Между % и симво- лом преобразования могут находиться: - знак минус, который указывает о выравнивании преобразован- ного аргумента по левому краю его поля. - Строка цифр, задающая минимальную ширину поля. Преобразо- ванное число будет напечатано в поле по крайней мере этой ширины, а если необходимо, то и в более широком. Если пре- образованный аргумент имеет меньше символов, чем указанная ширина поля, то он будет дополнен слева (или справа, если было указано выравнивание по левому краю)заполняющими сим- волами до этой ширины. Заполняющим символом обычно являет- ся пробел, а если ширина поля указывается с лидирующим ну- лем, то этим символом будет нуль (лидирующий нуль в данном случае не означает восьмеричной ширины поля). - Точка, которая отделяет ширину поля от следующей строки цифр. - Строка цифр (точность), которая указывает максимальное число символов строки, которые должны быть напечатаны, или число печатаемых справа от десятичной точки цифр для пере- менных типа FLOAT или DOUBLE. - Модификатор длины L, который указывает, что соответствую- щий элемент данных имеет тип LONG, а не INT. Ниже приводятся символы преобразования и их смысл: D - аргумент преобразуется к десятичному виду. O - Аргумент преобразуется в беззнаковую восьмеричную форму (без лидирующего нуля). X - Аргумент преобразуется в беззнаковую шестнадцатеричную форму (без лидирующих 0X). U - Аргумент преобразуется в беззнаковую десятичную форму. C - Аргумент рассматривается как отдельный символ. S - Аргумент является строкой: символы строки печатаются до тех пор, пока не будет достигнут нулевой символ или не бу- дет напечатано количество символов, указанное в специфика- ции точности. E - Аргумент, рассматриваемый как переменная типа FLOAT или DOUBLE, преобразуется в десятичную форму в виде [-]M.NNNNNNE[+-]XX, где длина строки из N определяется указанной точностью. Точность по умолчанию равна 6. F - Аргумент, рассматриваемый как переменная типа FLOAT или DOUBLE, преобразуется в десятичную форму в виде [-]MMM.NNNNN, где длина строки из N определяется указанной точностью. Точность по умолчанию равна 6. отметим, что эта точность не определяет количество печатаемых в формате F значащих цифр. G - Используется или формат %E или %F, какой короче; незна- чащие нули не печатаются. Если идущий за % символ не является символом преобразования, то печатается сам этот символ; следовательно,символ % можно напечатать, указав %%. Большинство из форматных преобразований очевидно и было проиллюстрировано в предыдущих главах. Единственным исключе- нием является то, как точность взаимодействует со строками. Следующая таблица демонстрирует влияние задания различных спецификаций на печать "HELLO, WORLD" (12 символов). Мы по- местили двоеточия вокруг каждого поля для того, чтобы вы могли видеть его протяженность. :%10S: :HELLO, WORLD: :%10-S: :HELLO, WORLD: :%20S: : HELLO, WORLD: :%-20S: :HELLO, WORLD : :%20.10S: : HELLO, WOR: :%-20.10S: :HELLO, WOR : :%.10S: :HELLO, WOR: Предостережение: PRINTF использует свой первый аргумент для определения числа последующих аргументов и их типов. Ес- ли количество аргументов окажется недостаточным или они бу- дут иметь несоответственные типы, то возникнет путаница и вы получите бессмысленные результаты. Упражнение 7-1 -------------- Напишите программу, которая будет печатать разумным об- разом произвольный ввод. Как минимум она должна печатать неграфические символы в восьмеричном или шестнадцатеричном виде (в соответствии с принятыми у вас обычаями) и склады- вать длинные строки. 7.4. Форматный ввод - функция SCANF Осуществляющая ввод функция SCANF является аналогом PRINTF и позволяет проводить в обратном направлении многие из тех же самых преобразований. Функция SCANF(CONTROL, ARG1, ARG2, ...) читает символы из стандартного ввода, интерпретирует их в соответствии с форматом, указанном в аргументе CONTROL, и помещает результаты в остальные аргументы. Управляющий аргу- мент описывается ниже; другие аргументы, каждый из которых должен быть указателем, определяют, куда следует поместить соответствующим образом преобразованный ввод. Управляющая строка обычно содержит спецификации преобра- зования, которые используются для непосредственной интерпре- тации входных последовательностей. Управляющая строка может содержать: - пробелы, табуляции или символы новой строки ("символы пус- тых промежутков"), которые игнорируются. - Обычные символы (не %), которые предполагаются совпадающи- ми со следующими отличными от символов пустых промежутков символами входного потока. - Спецификации преобразования, состоящие из символа %, нео- бязательного символа подавления присваивания *, необяза- тельного числа, задающего максимальную ширину поля и сим- вола преобразования. Спецификация преобразования управляет преобразованием следующего поля ввода. нормально результат помещается в пе- ременную, которая указывается соответствующим аргументом. Если, однако , с помощью символа * указано подавление прис- ваивания, то это поле ввода просто пропускается и никакого присваивания не производится. Поле ввода определяется как строка символов, которые отличны от символов простых проме- жутков; оно продолжается либо до следующего символа пустого промежутка, либо пока не будет исчерпана ширина поля, если она указана. Отсюда следует, что при поиске нужного ей вво- да, функция SCANF будет пересекать границы строк, поскольку символ новой строки входит в число пустых промежутков. Символ преобразования определяет интерпретацию поля вво- да; согласно требованиям основанной на вызове по значению семантики языка "с" соответствующий аргумент должен быть указателем. Допускаются следующие символы преобразования