Язык С




Структуры, ссылающиеся на себя - часть 2


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 */ P->LEFT = TREE(P->LEFT, W); ELSE /* GREATER INTO RIGHT SUBTREE */ P->RIGHT = TREE(P->RIGHT, W); RETURN(P); \)




Содержание  Назад  Вперед