Уявімо собі, що нам треба написати програму, яка би рахувала кількість знайдених ключових слів C. Нам потрібен би був масив символьних ланцюжків, який би містив назви, і масив цілих для відліку. Одним з можливих варіантів було би використання двох паралельних масивівkeyword і keycount, як от
char *keyword[NKEYS];
int keycount[NKEYS];
Але самий факт того, що масиви паралельні, підказує відмінну організацію — масив структур. Кожне ключове слово складатиметься з пари:
char *word;
int cout;
і ці пари утворюватимуть масив. Оголошення структури
struct key {
char *word;
int count;
} keytab[NKEYS];
заявляє про структуру типу key, і означує масив keytab, що міститиме структури цього типу, відводячи для них місце в пам'яті. Кожен елемент масиву буде структурою. Це можна також написати як
struct key {
char *word;
int count;
};
struct key keytab[NKEYS];
Оскільки структура keytab містить сталий набір імен, найлегшим буде зробити її зовнішньою змінною й ініціювати раз і назавжди під час її означення. Ініціалізація структури аналогічна попереднім — за визначенням слідує список ініціалізаторів, включених у фігурні дужки:
struct key {
char *word;
int count;
} keytab[] = {
"auto", 0,
"break", 0,
"case", 0,
"char", 0,
"const", 0,
"continue", 0,
"default", 0,
/* ... */
"unsigned", 0,
"void", 0,
"volatile", 0,
"while", 0
};
Ініціалізатори перелічено парами, згідно елементів структури. Було би точніше включити ініціалізатори кожного «рядка» структури у фігурні дужки, як от
{ "auto", 0 },
{ "break", 0 },
{ "case", 0 },
...
але внутрішні дужки необов'язкові, якщо ініціалізатори складаються з простих змінних або символьних ланцюжків, і коли всі присутні. Зазвичай, кількість елементів масиву keytabобчислюється автоматично, при наявності ініціалізаторів і порожньому []. Програма відліку ключових слів почнеться з означення keytab. Функція main читатиме ввід шляхом повторного виклику getword, яка добуватиме по одному слову за раз. Кожне слово шукатиметься вkeytab за допомогою нашої версії функції бінарного пошуку, написаної в Розділі 3. Список ключових слів потрібно буде сортувати в зростаючій послідовності в таблиці.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
int binsearch(char *, struct key *, int);
/* відлік ключових слів C */
main()
{
int n;
char word[MAXWORD];
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
if ((n = binsearch(word, keytab, NKEYS)) >= 0)
keytab[n].count++;
for (n = 0; n < NKEYS; n++)
if (keytab[n].count > 0)
printf("%4d %s\n",
keytab[n].count, keytab[n].word);
return 0;
}
/* binsearch: знаходить слово word у tab[0]...tab[n-1] */
int binsearch(char *word, struct key tab[], int n)
{
int cond;
int low, high, mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low+high) / 2;
if ((cond = strcmp(word, tab[mid].word)) < 0)
high = mid - 1;
else if (cond > 0)
low = mid + 1;
else
return mid;
}
return -1;
}
Ми покажемо функцію getword за якусь мить; поки-що досить знати, що кожний її виклик знаходить нове слово, яке копійовано в масив, вказаний як її перший аргумент. Кількість NKEYSє числом ключових слів у keytab. Хоча ми могли би самі порахувати це число, набагато легше і безпечніше залишити це машині, особливо якщо список може змінитися пізніше. Однією з можливостей буде завершити список ініціалізаторів нульовим покажчиком, після чого ітерувати через keytab до досягнення кінця.
Але це вкрай потрібно, оскільки розмір масиву повністю визначається під час компіляції. Розмір масиву складає розмір одного елемента помножено на кількість елементів, тож кількість складатиме просто
розмір keytab / розмір struct key
C забезпечує унарним компіляційним оператором під назвою sizeof, який можна застосувати для визначення розміру будь-якого об'єкту. Вирази
sizeof об'єкт
і
sizeof (назва типу)
повертають ціле число, рівне розмірові в байтах вказаного об'єкту або типу. (Точніше, sizeofповертає беззнакове ціле значення, чий тип size_t визначено в файлі заголувку <stddef.h>.) Об'єктом може служити як змінна, так і масив або структура. Назва типу також може бути однією з назв основних типів, таких як int або doble, або ж назвою похідного типу, як структура або покажчик. В нашому випадку, кількість ключових слів дорівнюватиме розмірові масиву, поділено на розмір одного елемента. Це обчислення використано в твердженні #defineдля того, щоб встановити значення NKEYS:
#define NKEYS (sizeof keytab / sizeof(struct key))
Іншим шляхом буде ділення масиву на розмір певного елемента:
#define NKEYS (sizeof keytab / sizeof(keytab[0]))
Останнє має перевагу в тому, що його не потрібно міняти, якщо тип змінено. sizeof неможливо використати в рядку #if, оскільки препроцесор не розуміє назв типів. Зате вираз у #define не обчислюється препроцесором, тож цей код чинний.
Тепер, щодо функції getword. Ми написали більш узагальнену getword, ніж ця програма потребує, але вона не є складною. getword добуває наступне «слово» зі вводу, де словом може служити або ланцюжок з літер і цифр, що починається з літери, або один символ, що не являється пробілом. Функція повертає перший знак слова, або EOF у випадку кінця файла, або самий знак, якщо він не є частиною алфавіта.
/* getword: одержує наступне слово зі вводу */
int getword(char *word, int lim)
{
int c, getch(void);
void ungetch(int);
char *w = word;
while (isspace(c = getch()))
;
if (c != EOF)
*w++ = c;
if (!isalpha(c)) {
*w = '\0';
return c;
}
for ( ; --lim > 0; w++)
if (!isalnum(*w = getch())) {
ungetch(*w);
break;
}
*w = '\0';
return word[0];
}
getword використовує getch і ungetch, які ми написали в Розділі 4. Коли набір буквенно-цифрових лексем закінчився, це означає, що getword зайшла на один символ задалеко. Викликungetch проштовхує символ назад на ввід для наступного виклику функції. getword також використовує isspace, для ігнорування пробілів, isalpha, щоб розпізнати літери, і isalnumдля розрізнення літер і цифр; усі зі стандартного файла заголовка <ctype.h>.
Вправа 6-1. Наша версія getword не обробляє належним чином жорсткі пробіли, ланцюжкові константи, коментарі, або вказівки препроцесору. Напишіть кращу версію.
