возможностей было бы закончить список инициализаторов указа-
нием на нуль и затем пройти в цикле сквозь массив 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
--------------
Напишите вариант программы подсчета ключевых слов, кото-
рый бы не учитывал появления этих слов в заключенных в ка-
вычки строках.
6.4. Указатели на структуры
Чтобы проиллюстрировать некоторые соображения, связанные
с использованием указателей и массивов структур, давайте
снова составим программу подсчета ключевых строк, используя
на этот раз указатели, а не индексы массивов.
Внешнее описание массива KEYTAB не нужно изменять, но
функции MAIN и BINARY требуют модификации.
MAIN() /* COUNT C KEYWORD; POINTER VERSION */
\(
INT T;
CHAR WORD[MAXWORD];
STRUCT KEY *BINARY(), *P;
WHILE ((T = GETWORD(WORD, MAXWORD;) !=EOF)
IF (T==LETTER)
IF ((P=BINARY(WORD,KEYTAB,NKEYS)) !=NULL)
P->KEYCOUNT++;
FOR (P=KEYTAB; P>KEYTAB + NKEYS; P++)
IF (P->KEYCOUNT > 0)
PRINTF("%4D %S/N", P->KEYCOUNT, P->KEYWORD);
\)
STRUCT KEY *BINARY(WORD, TAB, N) /* FIND WORD */
CHAR *WORD /* IN TAB[0]...TAB[N-1] */
STRUCT KEY TAB [];
INT N;
\(
INT COND;
STRUCT KEY *LOW = &TAB[0];
STRUCT KEY *HIGH = &TAB[N-1];
STRUCT KEY *MID;
WHILE (LOW <= HIGH) \(
MID = LOW + (HIGH-LOW) / 2;
IF ((COND = STRCMP(WORD, MID->KEYWORD)) < 0)
HIGH = MID - 1;
ELSE IF (COND > 0)
LOW = MID + 1;
ELSE
RETURN(MID);
\)
RETURN(NULL);
\)
Здесь имеется несколько моментов, которые стоит отме-
тить. Во-первых, описание функции BINARI должно указывать,
что она возвращает указатель на структуру типа KEY, а не на
целое; это объявляется как в функции MAIN, так и в BINARY.
Если функция BINARI находит слово, то она возвращает указа-
тель на него; если же нет, она возвращает NULL.
Во-вторых, все обращения к элементам массива KEYTAB осу-
ществляются через указатели. Это влечет за собой одно сущес-
твенное изменение в функции BINARY: средний элемент больше
нельзя вычислять просто по формуле
MID = (LOW + HIGH) / 2
потому что сложение двух указателей не дает какого-нибудь
полезного результата (даже после деления на 2) и в действи-
тельности является незаконным. эту формулу надо заменить на
MID = LOW + (HIGH-LOW) / 2
в результате которой MID становится указателем на элемент,
расположенный посередине между LOW и HIGH.
Вам также следует разобраться в инициализации LOW и
HIGH. указатель можно инициализировать адресом ранее опреде-
ленного объекта; именно как мы здесь и поступили.
В функции MAIN мы написали
FOR (P=KEYTAB; P < KEYTAB + NKEYS; P++)
Если P является указателем структуры, то любая арифметика с
P учитывает фактический размер данной структуры, так что P++
увеличивает P на нужную величину, в результате чего P указы-
вает на следующий элемент массива структур. Но не считайте,
что размер структуры равен сумме размеров ее членов, - из-за
требований выравнивания для различных объектов в структуре
могут возникать "дыры".
И, наконец, несколько второстепенный вопрос о форме за-
писи программы. Если возвращаемая функцией величина имеет
тип, как, например, в
STRUCT KEY *BINARY(WORD, TAB, N)
Tо может оказаться, что имя функции трудно выделить среди
текста. В связи с этим иногда используется другой стиль за-
писи:
STRUCT KEY *
BINARY(WORD, TAB, N)
Это главным образом дело вкуса; выберите ту форму, которая
вам нравится, и придерживайтесь ее.
6.5. Структуры, ссылающиеся на себя
Предположим, что нам надо справиться с более общей зада-
чей, состоящей в подсчете числа появлений всех слов в неко-
тором файле ввода. Так как список слов заранее не известен,
мы не можем их упорядочить удобным образом и использовать
бинарный поиск. Мы даже не можем осуществлять последователь-
ный просмотр при поступлении каждого слова, с тем чтобы ус-
тановить, не встречалось ли оно ранее; такая программа будет
работать вечно. (Более точно, ожидаемое время работы растет
как квадрат числа вводимых слов). Как же нам организовать
программу, чтобы справиться со списком произвольных слов?
Одно из решений состоит в том, чтобы все время хранить
массив поступающих до сих пор слов в упорядоченном виде, по-
мещая каждое слово в нужное место по мере их поступления.
OДнако это не следует делать, перемещая слова в линейном
массиве, - это также потребует слишком много времени. Вместо
этого мы используем структуру данных, называемую доичным де-
ревом.
Каждому новому слову соответствует один "узел" дерева;
каждый узел содержит:
указатель текста слова
---------------------------------------------------------------------------
счетчик числа появлений
---------------------------------------------------------------------------
указатель узла левого потомка
---------------------------------------------------------------------------
указатель узла правого потомка
---------------------------------------------------------------------------
Никакой узел не может иметь более двух детей; возможно от-
сутсвие детей или наличие только одного потомка.
Узлы создаются таким образом, что левое поддерево каждо-
го узла содержит только те слова, которые меньше слова в
этом узле, а правое поддерево только те слова, которые боль-
ше. Чтобы определить, находится ли новое слово уже в дереве,
начинают с корня и сравнивают новое слово со словом, храня-
щимся в этом узле. Если слова совпадают, то вопрос решается
утвердительно. Если новое слово меньше слова в дереве, то
переходят к рассмотрению левого потомка; в противном случае
исследуется правый потомок. Если в нужном направлении пото-
мок отсутствует, то значит новое слово не находится в дереве
и место этого недостающего потомка как раз и является мес-
том, куда следует поместить новое слово. Поскольку поиск из
любого узла приводит к поиску одного из его потомков, то сам
процесс поиска по существу является рекурсивным. В соответс-
твии с этим наиболее естественно использовать рекурсивные
процедуры ввода и вывода.
Возвращаясь назад к описанию узла, ясно, что это будет
структура с четырьмя компонентами:
STRUCT TNODE \( /* THE BASIC NODE */
CHAR *WORD; /* POINTS TO THE TEXT */
INT COUNT; /* NUMBER OF OCCURRENCES */
STRUCT TNODE *LEFT; /* LEFT CHILD */
STRUCT TNODE *RIGHT; /* RIGHT CHILD */
\);
Это "рекурсивное" описание узла может показаться рискован-
ным, но на самом деле оно вполне корректно. Структура не
имеет права содержать ссылку на саму себя, но
STRUCT TNODE *LEFT;
описывает LEFT как указатель на узел, а не как сам узел.
Текст самой программы оказывается удивительно маленьким,
если, конечно, иметь в распоряжении набор написанных нами
ранее процедур, обеспечивающих нужные действия. Мы имеем в
виду функцию GETWORD для извлечения каждого слова из файла
ввода и функцию ALLOC для выделения места для хранения слов.
Ведущая программа просто считывает слова с помощью функ-
ции GETWORD и помещает их в дерево, используя функцию TREE.
#DEFINE MAXWORD 20
MAIN() /* WORD FREGUENCY COUNT */
\(
STRUCT TNODE *ROOT, *TREE();
CHAR WORD[MAXWORD];
INT T;
ROOT = NULL;
WHILE ((T = GETWORD(WORD, MAXWORD)) \! = EOF)
IF (T == LETTER)
ROOT = TREE(ROOT, WORD);
TREEPRINT(ROOT);
\)
Функция TREE сама по себе проста. Слово передается функ-
цией MAIN к верхнему уровню (корню) дерева. На каждом этапе
это слово сравнивается со словом, уже хранящимся в этом уз-
ле, и с помощью рекурсивного обращения к TREE просачивается
вниз либо к левому, либо к правому поддереву. В конце концов
это слово либо совпадает с каким-то словом, уже находящимся
в дереве (в этом случае счетчик увеличивается на единицу),
либо программа натолкнется на нулевой указатель, свидетель-
ствующий о необходимости создания и добавления к дереву но-
вого узла. В случае создания нового узла функция TREE возв-
ращает указатель этого узла, который помещается в родитель-
ский узел.
STRUCT TNODE *TREE(P, W)
/* INSTALL W AT OR BELOW P */
STRUCT TNODE *P;
CHAR *W;
\(
STRUCT TNODE *TALLOC();
CHAR *STRSAVE();
INT COND;
IF (P == NULL) \( /* A NEW WORD
HAS ARRIVED */
P == TALLOC(); /* MAKE A NEW NODE */
P->WORD = STRSAVE(W);
P->COUNT = 1;
P->LEFT = P->RIGHT = NULL;
\) ELSE IF ((COND = STRCMP(W, P->WORD)) == 0)
P->COUNT++; /* REPEATED WORD */
ELSE IF (COND < 0)/* LOWER GOES INTO LEFT SUBTREE */
