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