/* 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. Haшa вepcия getword не обрабатывает должным образом знак подчеркивания, строковые константы, комментарии и управляющие строки препроцессора. Напишите более совершенный вариант программы.
6.4 Указатели на структуры
Для иллюстрации некоторых моментов, касающихся указателей на структуры и массивов структур, перепишем программу подсчета ключевых слов, пользуясь для получения элементов массива вместо индексов указателями.
Внешнее объявление массива keytab остается без изменения, a main и binsearch нужно модифицировать.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
struct key *binsearch(char *, struct key *, int);
/* подсчет ключевых слов Си: версия с указателями */
main()
{
char word[MAXWORD];
struct key *p;
while (getword(word, MAXWORD) != EOF)
if (isalpha(word[0]))
if ((p = binsearch(word, keytab, NKEYS)) != NULL)
p->count++;
for (p = keytab; p < keytab + NKEYS; p++)
if (p->count > 0)
printf("%4d %s\n", p->count, p->word);
return 0;
}
/* binsearch: найти слово word в tab[0]...tab[n-1] */
struct key *binsearch(char *word, struct key *tab, int n)
{
int cond;
struct key *low = &tab[0];
struct key *high = &tab[n];
struct key *mid;
while (low < high) {
mid = low + (high - low) / 2;
if ((cond = strcmp(word, mid->word)) < 0)
high = mid;
else if (cond > 0)
low = mid + 1;
else
return mid;
}
return NULL;
}
Некоторые детали этой программы требуют пояснений. Во-первых, описание функции binsearch должно отражать тот факт, что она возвращает указатель на struct key, а не целое, это объявлено как в прототипе функции, так и в функции binsearch. Если binsearch находит слово, то она выдает указатель на него, в противном случае она возвращает NULL. Во-вторых, к элементам keytab доступ в нашей программе осуществляется через указатели. Это потребовало значительных изменений в binsearch. Инициализаторами для low и high теперь служат указатели на начало и на место сразу после конца массива. Вычисление положения среднего элемента с помощью формулы
mid = (low + high) / 2 /* НЕВЕРНО */
не годится, поскольку указатели нельзя складывать. Однако к ним можно применить операцию вычитания, и так как high-low есть число элементов, присваивание
mid = low + (high-low) / 2
превратит mid в указатель на элемент, лежащий посередине между low и high.
Самое важное при переходе на новый вариант программы - сделать так, чтобы не генерировались неправильные указатели и не было попыток обратиться за пределы массива. Проблема в том, что и &tab[-1], и &tab[n] находятся вне границ массива. Первый адрес определенно неверен, нельзя также осуществить доступ и по второму адресу. По правилам языка, однако, гарантируется, что адрес ячейки памяти, следующей сразу за концом массива (т. е. &tab[n]), в арифметике с указателями воспринимается правильно.
В главной программе main мы написали
for (р = keytab; р < keytab + NKEYS; р++)
Если p - это указатель на структуру, то при выполнении операций с р учитывается размер структуры. Поэтому р++ увеличит р на такую величину, чтобы выйти на следующий структурный элемент массива, а проверка условия вовремя остановит цикл.
Не следует, однако, полагать, что размер структуры равен сумме размеров ее элементов. Вследствие выравнивания объектов разной длины в структуре могут появляться безымянные "дыры". Например, если переменная типа char занимает один байт, а int - четыре байта, то для структуры
struct {
char с;
int i;
};
может потребоваться восемь байтов, а не пять. Оператор sizeof возвращает правильное значение.
Наконец, несколько слов относительно формата программы. Если функция возвращает значение сложного типа, как, например, в нашем случае она возвращает указатель на структуру:
struct key *binsearch(char *word, struct key *tab, int n)
то "высмотреть" имя функции оказывается совсем не просто. В подобных случаях иногда пишут так:
struct key *
binsearch(char *word, struct key *tab, int n)
Какой форме отдать предпочтение - дело вкуса. Выберите ту, которая больше всего вам нравится, и придерживайтесь ее.
6.5 Структуры со ссылками на себя
Предположим, что мы хотим решить более общую задачу - написать программу, подсчитывающую частоту встречаемости для любых слов входного потока. Так как список слов заранее не известен, мы не можем предварительно упорядочить его и применить бинарный поиск. Было бы неразумно пользоваться и линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет - в этом случае программа работала бы слишком медленно. (Более точная оценка: время работы такой программы пропорционально квадрату количества слов.) Как можно организовать данные, чтобы эффективно справиться со списком произвольных слов?