Керниган и Ритчи - Язык программирования Си (793773), страница 33
Текст из файла (страница 33)
Число элементов массива keytab будет вычислено по количествуинициализаторов, поскольку они представлены полностью, а внутри квадратных скобок"[]" ничего незадано.Программа подсчета ключевых слов начинается с определения keytab. Программа main читает ввод,многократно обращаясь к функции getword и получая на каждом ее вызове очередное слово. Каждое словоищется в keytab. Для этого используется функция бинарного поиска, которую мы написали в главе 3. Списокключевых слов должен быть упорядочен в алфавитном порядке.#include <stdio.h>#include <ctype.h>#include <string.h>#define MAXWORD 100int getword(char *, int);int binsearch(char *, struct key *, int);/* подсчет ключевых слов Си */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: найти слово в tab[0] ...
tab[n - Т] */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;elsereturn mid;}return -1;}Чуть позже мы рассмотрим функцию getword, а сейчас нам достаточно знать, что при каждом ее вызовеполучается очередное слово, которое запоминается в массиве, заданном первым аргументом.NKEYS — количество ключевых слов в keytab. Хотя мы могли бы подсчитать число таких слов вручную,гораздо легче и безопасней сделать это с помощью машины, особенно если список ключевых слов можетбыть изменен. Одно из возможных решений — поместить в конец списка инициализаторов пустой указатель(NULL) и затем перебирать в цикле элементы keytab, пока не встретится концевой элемент.Но возможно и более простое решение.
Поскольку размер массива полностью определен во времякомпиляции и равен произведению количества элементов массива на размер его отдельного элемента, числоэлементов массива можно вычислить по формулеразмер keytab / размер struct keyВ Си имеется унарный оператор sizeof , который работает во время компиляции. Его можно применять длявычисления размера любого объекта. Выраженияsizeof объектиsizeof (имя-типа)выдают целые значения, равные размеру указанного объекта или типа в байтах.
(Строго говоря, sizeofвыдает беззнаковое целое, тип которого size_t определен в заголовочном файле <stddef.h>.) Чтокасается объекта, то это может быть переменная, массив или структура. В качестве имени типа можетвыступать имя базового типа (int, double...) или имя производного типа, например структуры илиуказателя.В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо поделить на размеродного элемента. Указанное вычисление используется в инструкции #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 не обрабатывает должным образом знак подчеркивания, строковыеконстанты, комментарии и управляющие строки препроцессора. Напишите более совершенный вариантпрограммы.6.4.
Указатели на структурыДля иллюстрации некоторых моментов, касающихся указателей на структуры и массивов структур,перепишем программу подсчета ключевых слов, пользуясь для получения элементов массива вместоиндексов указателями.Внешнее объявление массива keytab остается без изменения, a main и binsearch нужномодифицировать.#include <stdio.h>#include <ctype.h>#include <string.h>#define MAXWORD 100int 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 ;elsereturn 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; р++)Если р — это указатель на структуру, то при выполнении операций с р учитывается размер структуры.
Поэтомур++ увеличит р на такую величину, чтобы выйти на следующий структурный элемент массива, а проверкаусловия вовремя остановит цикл.Не следует, однако, полагать, что размер структуры равен сумме размеров ее элементов. Вследствиевыравнивания объектов разной длины в структуре могут появляться безымянные "дыры". Например, еслипеременная типа char занимает один байт, a 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. Структуры со ссылками на себяПредположим, что мы хотим решить более общую задачу — написать программу, подсчитывающую частотувстречаемости для любых слов входного потока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
