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




Структуры со ссылками на себя - часть 2


Вернемся к описанию узла, которое удобно представить в виде структуры с четырьмя компонентами:

struct tnode { /* узел дерева */ char *word; /* указатель на текст */ int count; /* число вхождений */ struct tnode *left; /* левый сын */ struct tnode *right; /* правый сын */ };

Приведенное рекурсивное определение узла может показаться рискованным, но оно правильное. Структура не может включать саму себя, но ведь

struct tnode *left;

объявляет left как указатель на tnode, а не сам tnode.

Иногда возникает потребность во взаимоссылающихся структурах: двух структурах, ссылающихся друг на друга. Прием, позволяющий справиться с этой задачей, демонстрируется следующим фрагментом:

struct t { ... struct s *p; /* р указывает на s */ }; struct s { ... struct t *q; /* q указывает на t */ }

Вся программа удивительно мала - правда, она использует вспомогательные программы вроде getword, уже написанные нами. Главная программа читает слова с помощью getword и вставляет их в дерево посредством addtree.

#include <stdio.h> #include <ctype.h> #include <string.h>

#define MAXWORD 100

struct tnode *addtree(struct tnode *, char *); void treeprint(struct tnode *); int getword(char *, int);

/* подсчет частоты встречаемости слов */ main() { struct tnode *root; char word[MAXWORD];

root = NULL; while (getword (word, MAXWORD) != EOF) if (isalpha(word[0])) root = addtree(root, word); treeprint(root); return 0; }

Функция addtree рекурсивна. Первое слово функция main помещает на верхний уровень дерева (корень дерева). Каждое вновь поступившее слово сравнивается со словом узла и "погружается" или в левое, или в правое поддерево с помощью рекурсивного обращения к addtree. Через некоторое время это слово обязательно либо совпадет с каким-нибудь из имеющихся в дереве слов (в этом случае к счетчику будет добавлена 1), либо программа встретит пустую позицию, что послужит сигналом для создания нового узла и добавления его к дереву. Создание нового узла сопровождается тем, что addtree возвращает на него указатель, который вставляется в узел родителя.

struct tnode *talloc(void); char *strdup(char *);




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