Книга: Linux программирование в примерах

14.4.3. Ввод элемента в дерево: tsearch()

14.4.3. Ввод элемента в дерево: tsearch()

Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную void*, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте этот указатель в NULL:

void *root = NULL; /* Корень нового дерева */
void *val; /* Указатель на возвращенные данные */
extern int my_compare(const void*, const void*); /* Функция сравнения */
extern char key[], key2[]; /* Значения для ввода в дерево */
val = tsearch(key, &root, my_compare);
 /* Ввести в дерево первый элемент */
/* ...заполнить key2 другим значением. НЕ изменять корень... */
val = tsearch(key2, &root, my_compare);
 /* Ввести в дерево последующий элемент */

Как показано, в переменной root должен быть NULL лишь в первый раз, после чего нужно оставить ее как есть. При каждом последующем вызове tsearch() использует ее для управления деревом.

Когда разыскиваемый key найден, как tsearch(), так и tfind() возвращают указатель на содержащую его вершину. Поведение функций различно, когда key не найден: tfind() возвращает NULL, a tsearch() вводит в дерево новое значение и возвращает указатель на него. Функции tsearch() и tfind() возвращают указатели на внутренние вершины дерева. Они могут использоваться в последующих вызовах в качестве значения root для работы с поддеревьями. Как мы вскоре увидим, значение key может быть указателем на произвольную структуру; он не ограничен символьной строкой, как можно было бы предположить из предыдущего примера.

Эти процедуры сохраняют лишь указатели на данные, использующиеся в качестве ключей. Соответственно это ваше дело управлять памятью для хранения значений данных, обычно с помощью malloc().

Оглавление книги