Язык программирования Си - [57]

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

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
#include
#include

#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 *);

/* 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 на дереве, приведенном выше. Практическое замечание: если дерево "несбалансировано" (что бывает, когда слова поступают не в случайном порядке), то время работы программы может сильно возрасти. Худший вариант, когда слова уже упорядочены; в этом случае затраты на вычисления будут такими же, как при линейном поиске. Существуют обобщения бинарного дерева, которые не страдают этим недостатком, но здесь мы их не описываем.

Прежде чем завершить обсуждение этого примера, сделаем краткое отступление от темы и поговорим о механизме запроса памяти. Очевидно, хотелось бы иметь всего лишь одну функцию, выделяющую память, даже если эта память предназначается для разного рода объектов. Но если одна и та же функция обеспечивает память, скажем) и для указателей на char, и для указателей на struct tnode, то возникают два вопроса. Первый: как справиться с требованием большинства машин, в которых объекты определенного типа должны быть выровнены (например, int часто должны размещаться, начиная с четных адресов)? И второе: как объявить функцию-распределитель памяти, которая вынуждена в качестве результата возвращать указатели разных типов?

Вообще говоря, требования, касающиеся выравнивания, можно легко выполнить за счет некоторого перерасхода памяти. Однако для этого возвращаемый указатель должен быть таким, чтобы удовлетворялись любые ограничения, связанные с выравниванием. Функция