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