обращается к конкретному члену. (Операция -> - это знак ми-
нус, за которым следует знак “>”.)
Так как PD указывает на структуру, то к члену YEAR можно
обратиться и следующим образом
(*PD).YEAR
но указатели структур используются настолько часто, что за-
пись -> оказывается удобным сокращением. Круглые скобки в
(*PD).YEAR необходимы, потому что операция указания члена
· 132 -
стуктуры старше , чем * . Обе операции, “->” и “.”, ассоции-
руются слева направо, так что конструкции слева и справа
зквивалентны
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.
· 133 -
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 \),
. . .
· 134 -
Но когда инициализаторы являются простыми переменными или
символьными строками и все они присутствуют, то во внутрен-
них фигурных скобках нет необходимости. Как обычно, компиля-
тор сам вычислит число элементов массива 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 каждый раз, как она находит слово,
и копирует это слово в свой первый аргумент.
·
135 -
Величина 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©;
\)
· 136 -
WHILE (--LIM > 0) \(
T = TYPE(C = *W++ = GETCH());
IF (T ! = LETTER && T ! = DIGIT) \(
UNGETCH©;
BREAK;
\)
\)
*(W-1) - '\0';
RETURN(LETTER);
\)
Функция GETWORD использует функции GETCH и UNGETCH, которые
мы написали в главе 4: когда набор алфавитных символов пре-
рывается, функция GETWORD получает один лишний символ. В ре-
зультате вызова UNGETCH этот символ помещается назад во ввод
для следующего обращения.
Функция GETWORD обращается к функции TYPE для определе-
ния типа каждого отдельного символа из файла ввода. Вот ва-
риант, справедливый только для алфавита ASCII.
TYPE© /* 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©;
\)
Символические константы LETTER и DIGIT могут иметь любые
значения, лишь бы они не вступали в конфликт с символами,
отличными от буквенно-цифровых, и с EOF; очевидно возможен
следующий выбор
#DEFINE LETTER 'A'
#DEFINE DIGIT '0'
функция GETWORD могла бы работать быстрее, если бы обращения
к функции TYPE были заменены обращениями к соответствующему
массиву TYPE[ ]. В стандартной библиотеке языка “C” предус-
мотрены макросы ISALPHA и ISDIGIT, действующие необходимым
образом.
Упражнение 6-1.
Сделайте такую модификацию функции GETWORD и оцените,
как изменится скорость работы программы.
Упражнение 6-2.
Напишите вариант функции TYPE, не зависящий от конкрет-
ного наборасимволов.
·
137 -
Упражнение 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.
· 138 -
Во-вторых, все обращения к элементам массива KEYTAB осу-
ществляются через указатели. Это влечет за собой одно сущес-
твенное изменение в функции BINARY: средний элемент больше