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




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


/* addtree: добавляет узел со словом w в р или ниже него */ struct tnode *addtree(struct tnode *p, char *w) { int cond;

if (р == NULL) { /* слово встречается впервые */ p = talloc(); /* создается новый узел */ p->word = strdup(w); p->count = 1; p->left = p->right = NULL; } else if ((cond = strcmp(w, p->word)) == 0) p->count++; /* это слово уже встречалось */ else if (cond < 0) /* меньше корня левого поддерева */ p->left = addtree(p->left, w); else /* больше корня правого поддерева */ p->right = addtree(p->right, w); return p; }

Память для нового узла запрашивается с помощью программы talloc, которая возвращает указатель на свободное пространство, достаточное для хранения одного узла дерева, а копирование нового слова в отдельное место памяти осуществляется с помощью strdup. (Мы рассмотрим эти программы чуть позже.) В тот (и только в тот) момент, когда к дереву подвешивается новый узел, происходит инициализация счетчика и обнуление указателей на сыновей. Мы опустили (что неразумно) контроль ошибок, который должен выполняться при получении значений от strdup и talloc.

Функция treeprint печатает дерево в лексикографическом порядке: для каждого узла она печатает его левое поддерево (все слова, которые меньше слова данного узла), затем само слово и, наконец, правое поддерево (слова, которые больше слова данного узла).

/* treeprint: упорядоченная печать дерева р */ void treeprint(struct tnode *p) { if (p != NULL) { treeprint (p->left); printf("%4d %s\n", p->count, p->word); treeprint(p->right); } }

Если вы не уверены, что досконально разобрались в том, как работает рекурсия, "проиграйте" действия treeprint на дереве, приведенном выше. Практическое замечание: если дерево "несбалансировано" (что бывает, когда слова поступают не в случайном порядке), то время работы программы может сильно возрасти. Худший вариант, когда слова уже упорядочены; в этом случае затраты на вычисления будут такими же, как при линейном поиске. Существуют обобщения бинарного дерева, которые не страдают этим недостатком, но здесь мы их не описываем.




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