Язык программирования C



         

Структуры, ссылающиеся на себя - часть 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); }




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