TSEARCH(3C) TSEARCH(3C) НАЗВАНИЕ tsearch, tfind, tdelete, twalk - управление бинарными деревьями поиска СИНТАКСИС #include 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 - это функция, которая вызывается для каждого узла. Она в свою очередь имеет три аргумента. Первым аргументом служит адрес текущего узла. Второй аргумент - это значение перечисляемого типа данных, определенно- го во включаемом файле как typedef enum {preorder, postorder, endorder, leaf} VISIT Значение показывает, который раз (первый, второй или третий) осуществляется доступ к узлу (во время обхода дерева в глубину и слева направо) или показывает, что узел является листом. Третий аргумент - это уровень уз- ла в дереве (в предположении, что корень имеет уровень 0). Указатели на ключ и корень дерева должны иметь тип "указатель на элемент" и преобразовываться к типу "ука- затель на символ". Аналогично, возвращаемое значение следует преобразовывать к типу "указатель на элемент", хотя оно и описывается типом "указатель на символ". ПРИМЕР Следующая программа считывает цепочки символов и запо- минает в дереве структуры, содержащие указатель на каж- дую цепочку и ее длину. Затем осуществляется обход де- рева и распечатываются в алфавитном порядке сохраненные цепочки символов с их длинами. #include #include 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; } } СМ. ТАКЖЕ bsearch(3C), hsearch(3C), lsearch(3C). ДИАГНОСТИКА Функция tsearch возвращает пустой указатель NULL, если не хватает свободного пространства для создания нового узла. Функции tfind и tdelete возвращают пустой указатель NULL, если аргумент rootp равен NULL. Если данные найдены, то функции tsearch и tfind возвра- щают указатель на них. В случае неудачного поиска функ- ция tfind возвращает пустой указатель NULL, а функция tsearch возвращает указатель на вставленные данные. ПРЕДОСТЕРЕЖЕНИЯ Аргумент root функции twalk имеет на один уровень кос- венной адресации меньше, чем аргумент rootp функций tsearch и tdelete. Термины preorder, postorder и endorder могут толковать- ся двояко. Функция tsearch использует термины preorder, postorder и endorder для обозначения, соответственно, следующих случаев: доступ к узлу перед доступом к како- му-либо его потомку, доступ к узлу после доступа к его левому потомку и перед доступом к правому потомку, дос- туп к узлу после доступа к обоим потомкам. Часто наз- ванные термины используются для указания порядка обхода дерева, что может привести к путанице. ОГРАНИЧЕНИЯ Если вызываемая функция изменяет указатель на корень дерева, то последствия будут непредсказуемы.