45940 (665245), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

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©;

\)

• 136 -

WHILE (--LIM > 0) \(

T = TYPE(C = *W++ = GETCH());

IF (T ! = LETTER && T ! = DIGIT) \(

UNGETCH©;

BREAK;

\)

\)

*(W-1) - '\0';

RETURN(LETTER);

\)

Функция GETWORD использует функции GETCH и UNGETCH, которые

мы написали в главе 4: когда набор алфавитных символов пре-

рывается, функция GETWORD получает один лишний символ. В ре-

зультате вызова UNGETCH этот символ помещается назад во ввод

для следующего обращения.

Функция GETWORD обращается к функции TYPE для определе-

ния типа каждого отдельного символа из файла ввода. Вот ва-

риант, справедливый только для алфавита ASCII.

TYPE© /* RETURN TYPE OF ASCII CHARACTER */ INT C;

\(

IF (C>= 'A' && C= 'A' && C<= 'Z')

RETURN(LETTER);

ELSE IF (C>= '0' && C<= '9')

RETURN(DIGIT);

ELSE

RETURN©;

\)

Символические константы LETTER и DIGIT могут иметь любые

значения, лишь бы они не вступали в конфликт с символами,

отличными от буквенно-цифровых, и с EOF; очевидно возможен

следующий выбор

#DEFINE LETTER 'A'

#DEFINE DIGIT '0'

функция GETWORD могла бы работать быстрее, если бы обращения

к функции TYPE были заменены обращениями к соответствующему

массиву TYPE[ ]. В стандартной библиотеке языка “C” предус-

мотрены макросы ISALPHA и ISDIGIT, действующие необходимым

образом.

Упражнение 6-1.

Сделайте такую модификацию функции GETWORD и оцените,

как изменится скорость работы программы.

Упражнение 6-2.

Напишите вариант функции TYPE, не зависящий от конкрет-

ного наборасимволов.

• 137 -

Упражнение 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.

• 138 -

Во-вторых, все обращения к элементам массива 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. Структуры, ссылающиеся на себя.

Предположим, что нам надо справиться с более общей зада-

чей, состоящей в подсчете числа появлений всех слов в неко-

тором файле ввода. Так как список слов заранее не известен,

мы не можем их упорядочить удобным образом и использовать

бинарный поиск. Мы даже не можем осуществлять последователь-

ный просмотр при поступлении каждого слова, с тем чтобы ус-

тановить, не встречалось ли оно ранее; такая программа будет

работать вечно. (Более точно, ожидаемое время работы растет

как квадрат числа вводимых слов). Как же нам организовать

программу, чтобы справиться со списком произвольных слов?

• 139 -

Одно из решений состоит в том, чтобы все время хранить

массив поступающих до сих пор слов в упорядоченном виде, по-

мещая каждое слово в нужное место по мере их поступления.

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 как указатель на узел, а не как сам узел.

• 140 -

Текст самой программы оказывается удивительно маленьким,

если, конечно, иметь в распоряжении набор написанных нами

ранее процедур, обеспечивающих нужные действия. Мы имеем в

виду функцию 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 */

P->LEFT = TREE(P->LEFT, W);

ELSE /* GREATER INTO RIGHT SUBTREE */

P->RIGHT = TREE(P->RIGHT, W);

RETURN(P);

\)

• 141 -

Память для нового узла выделяется функцией TALLOC, явля-

ющейся адаптацией для данного случая функции ALLOC, написан-

ной нами ранее. Она возвращает указатель свободного прост-

ранства, пригодного для хранения нового узла дерева. (Мы

вскоре обсудим это подробнее). Новое слово копируется функ-

цией STRSAVE в скрытое место, счетчик инициализируется еди-

ницей, и указатели обоих потомков полагаются равными нулю.

Эта часть программы выполняется только при добавлении нового

узла к ребру дерева. Мы здесь опустили проверку на ошибки

возвращаемых функций STRSAVE и TALLOC значений (что неразум-

но для практически работающей программы).

Функция TREEPRINT печатает дерево, начиная с левого под-

дерева; в каждом узле сначала печатается левое поддерево

(все слова, которые младше этого слова), затем само слово, а

затем правое поддерево (все слова, которые старше). Если вы

неуверенно оперируете с рекурсией, нарисуйте дерево сами и

напечатайте его с помощью функции TREEPRINT ; это одна из

наиболее ясных рекурсивных процедур, которую можно найти.

TREEPRINT (P) /* PRINT TREE P RECURSIVELY */

STRUCT TNODE *P;

\(

IF (P != NULL) \(

TREEPRINT (P->LEFT);

PRINTF(“%4D %S\N”, P->COUNT, P->WORD);

Характеристики

Список файлов реферата