TSEARCH(3C)

НАЗВАНИЕ

tsearch, tfind, tdelete, twalk - управление бинарными деревьями поиска

СИНТАКСИС

#include <search.h>

char *tsearch ((char *) key, (char **) rootp, compar) int (*compar) ( );

char *tfind ((char *) key, (char **) rootp, compar) int (*compar) ( );

char *tdelete ((char *) key, (char **) rootp, compar) int (*compar) ( );

char *twalk ((char *) root, action) void (*action) ( );

ОПИСАНИЕ

Функции tsearch, tfind, tdelete и twalk предназначены для выполнения операций над бинарными деревьями поиска. Функции реализованы на основе алгоритмов, описанных в книге Д. Кнута: Искусство программирования для ЭВМ. Т. 3. Сортировка, поиск. - М.: Мир, 1978. Раздел 6.2.2, алгоритмы T и D. Операции сравнения выполняются с помощью функции, предоставляемой пользователем. Функция сравнения вызывается с двумя аргументами - указателями на сравниваемые элементы. В соответствии с тем, какое целое число она возвращает: меньшее нуля, равное нулю или большее нуля, первый аргумент считается меньшим, равным или большим по отношению ко второму. В сравнении не обязательно должен участвовать каждый байт, поэтому элементы, в дополнение к сравниваемым величинам, могут содержать произвольные данные.

Функция tsearch используется для построения дерева и доступа к нему. Аргумент key является указателем на искомые данные (ключ). Если в дереве есть узел с данными, равными искомым, то результатом функции служит указатель на этот узел, первым полем которого является указатель на данные. В противном случае в дерево вставляется узел со ссылкой на искомые данные и возвращается указатель на него. Отметим, что копируются только указатели, поэтому вызываемая программа сама должна хранить данные. Аргумент rootp указывает на переменную, которая является указателем на корень дерева. Значение NULL переменной, на которую указывает rootp, означает пустое дерево; в этом случае переменная устанавливается равной указателю на данные, которые окажутся в корне нового дерева.

Подобно функции tsearch, функция tfind осуществляет поиск данных в дереве, возвращая в случае успеха указатель на узел. Однако в случае неудачного поиска функция tfind возвращает пустой указатель NULL. Аргументы для функции tfind такие же, как и для функции tsearch.

Функция tdelete удаляет узел из бинарного дерева поиска. Аргументы такие же, как и для функции tsearch. Переменная, на которую указывает rootp, изменяется, если удаляемый узел является корнем дерева. Функция tdelete возвращает указатель на предка удаляемого узла или пустой указатель NULL, если узел не найден.

Функция twalk осуществляет обход бинарного дерева поиска. Аргумент root указывает на корень обрабатываемого дерева. Любой узел может быть использован в качестве корня для обхода соответствующего поддерева. Аргумент action - это функция, которая вызывается для каждого узла. Она в свою очередь имеет три аргумента. Первым аргументом служит адрес текущего узла. Второй аргумент - это значение перечисляемого типа данных, определенного во включаемом файле <search.h> как

typedef enum {preorder, postorder, endorder, leaf} VISIT

Значение показывает, который раз (первый, второй или третий) осуществляется доступ к узлу (во время обхода дерева в глубину и слева направо) или показывает, что узел является листом. Третий аргумент - это уровень узла в дереве (в предположении, что корень имеет уровень 0).

Указатели на ключ и корень дерева должны иметь тип "указатель на элемент" и преобразовываться к типу "указатель на символ". Аналогично, возвращаемое значение следует преобразовывать к типу "указатель на элемент", хотя оно и описывается типом "указатель на символ".

ПРИМЕР

Следующая программа считывает цепочки символов и запоминает в дереве структуры, содержащие указатель на каждую цепочку и ее длину. Затем осуществляется обход дерева и распечатываются в алфавитном порядке сохраненные цепочки символов с их длинами.

#include <search.h>

#include <stdio.h>

struct node { /* В дереве будут запоминаться указатели на эти структуры */ char *string; int length; };

char string_space [10000]; /* Пространство для хранения цепочек символов */ struct node nodes [500]; /* Пространство для хранения структур */ struct node *root=NULL; /* Указатель на корень */

main() { char *strptr = string_space; struct node *nodeptr = nodes; void print_node (), twalk (); int i = 0, node_compare ();

while (gets (strptr) != NULL && i++ < 500) {

/* Инициализация структуры */ nodeptr -> string = strptr; nodeptr -> length = strlen(strptr);

/* Поместить структуру в дерево */ (void) tsearch ((char *) nodeptr, (char **)&root, node_compare);

/* Скорректировать указатели */ strptr += nodeptr->length + 1; nodeptr++; } twalk ((char *) root, print_node); }

/* Функция сравнивает две структуры в соответствии с алфавитной упорядоченностью цепочек символов */ int node_compare (node1, node2) char *node1, *node2; { return strcmp (((struct node *) node1)->string, ((struct node *) node2)->string); }

/* Функция распечатывает узел при первом заходе в него */ void print_node (node, order, level) char **node; VISIT order; int level; { if (order == preorder order == leaf) { (void) printf ("string = %20s, length = %d\n", (*((struct node **)node)) -> string, (*((struct node **)node)) -> length); } }

СМ. ТАКЖЕ

, , .

ДИАГНОСТИКА

Функция tsearch возвращает пустой указатель NULL, если не хватает свободного пространства для создания нового узла.

Функции tfind и tdelete возвращают пустой указатель NULL, если аргумент rootp равен NULL.

Если данные найдены, то функции tsearch и tfind возвращают указатель на них. В случае неудачного поиска функция tfind возвращает пустой указатель NULL, а функция tsearch возвращает указатель на вставленные данные.

ПРЕДОСТЕРЕЖЕНИЯ

Аргумент root функции twalk имеет на один уровень косвенной адресации меньше, чем аргумент rootp функций tsearch и tdelete.

Термины preorder, postorder и endorder могут толковаться двояко. Функция tsearch использует термины preorder, postorder и endorder для обозначения, соответственно, следующих случаев: доступ к узлу перед доступом к какому-либо его потомку, доступ к узлу после доступа к его левому потомку и перед доступом к правому потомку, доступ к узлу после доступа к обоим потомкам. Часто названные термины используются для указания порядка обхода дерева, что может привести к путанице.

ОГРАНИЧЕНИЯ

Если вызываемая функция изменяет указатель на корень дерева, то последствия будут непредсказуемы.

Содержание раздела