Указатели и многомерные массивы

Начинающие изучать язык "с" иногда становятся в тупикперед вопросом о различии между двумерным массивом и масси-вом указателей, таким как 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, используявместо индексации указатели.

Командная строка аргументов

Системные средства, на которые опирается реализация язы-ка "с", позволяют передавать командную строку аргументов илипараметров начинающей выполняться программе. Когда функцияMAIN вызывается к исполнению, она вызывается с двумя аргу-ментами. Первый аргумент (условно называемый ARGC) указываетчисло аргументов в командной строке, с которыми происходитобращение к программе; второй аргумент (ARGV) является ука-зателем на массив символьных строк, содержащих эти аргумен-ты, по одному в строке. Работа с такими строками - это обыч-ное использование многоуровневых указателей. Самую простую иллюстрацию этой возможности и необходимыхпри этом описаний дает программа ECHO, которая просто печа-тает в одну строку аргументы командной строки, разделяя ихпробелами. Таким образом, если дана команда ECHO HELLO, WORLD то выходом будет HELLO, WORLD по соглашению ARGV[0] является именем, по которому вызывает-ся программа, так что ARGC по меньшей мере равен 1. В приве-денном выше примере ARGC равен 3, а ARGV[0], ARGV[1] иARGV[2] равны соответственно "ECHO", "HELLO," и "WORLD".Первым фактическим агументом является ARGV[1], а последним -ARGV[ARGC-1]. Если ARGC равен 1, то за именем программы неследует никакой командной строки аргументов. Все это показа-но в ECHO: MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 1ST VERSION */INT ARGC;CHAR *ARGV[];\(INT I; FOR (I = 1; I < ARGC; I++) PRINTF("%S%C", ARGV[I], (I 0) PRINTF("%S%C",*++ARGV, (ARGC > 1)? ' ': '\N');\) Так как 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, а не в двумерном массиве фиксированногоразмера.

Указатели на функции

В языке "с" сами функции не являются переменными, ноимеется возможность определить указатель на функцию, которыйможно обрабатывать, передавать другим функциям, помещать вмассивы и т.д. Мы проиллюстрируем это, проведя модификациюнаписанной ранее программы сортировки так, чтобы при заданиинеобязательного аргумента -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. Структуры *

Структура - это набор из одной или более переменных,возможно различных типов, сгруппированных под одним именемдля удобства обработки. (В некоторых языках, самый известныйиз которых паскаль, структуры называются "записями"). Традиционным примером структуры является учетная карточ-ка работающего: "служащий" описывается набором атрибутов та-ких, как фамилия, имя, отчество (ф.и.о.), адрес, код соци-ального обеспечения, зарплата и т.д. Некоторые из этих атри-бутов сами могут оказаться структурами: ф.и.о. Имеет нес-колько компонент, как и адрес, и даже зарплата. Структуры оказываются полезными при организации сложныхданных особенно в больших программах, поскольку во многихситуациях они позволяют сгруппировать связанные данные такимобразом, что с ними можно обращаться, как с одним целым, ане как с отдельными объектами. В этой главе мы постараемсяпродемонстрировать то, как используются структуры. Програм-мы, которые мы для этого будем использовать, больше, чеммногие другие в этой книге, но все же достаточно умеренныхразмеров.

Основные сведения

Давайте снова обратимся к процедурам преобразования датыиз главы 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 будет ссылаться на месяц рождения. Операция указания членаструктуры "." ассоциируется слева направо.

Структуры и функции

В языке "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.

Массивы сруктур

Структуры особенно подходят для управления массивамисвязанных переменных. Рассмотрим, например, программу подс-чета числа вхождений каждого ключевого слова языка "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 -------------- Напишите вариант программы подсчета ключевых слов, кото-рый бы не учитывал появления этих слов в заключенных в ка-вычки строках.

Указатели на структуры

Чтобы проиллюстрировать некоторые соображения, связанныес использованием указателей и массивов структур, давайтеснова составим программу подсчета ключевых строк, используяна этот раз указатели, а не индексы массивов. Внешнее описание массива 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) Это главным образом дело вкуса; выберите ту форму, котораявам нравится, и придерживайтесь ее.