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 для обозначения, соответственно, следующих случаев: доступ к узлу перед доступом к како- му-либо его потомку, доступ к узлу после доступа к его левому потомку и перед доступом к правому потомку, дос- туп к узлу после доступа к обоим потомкам. Часто наз- ванные термины используются для указания порядка обхода дерева, что может привести к путанице. ОГРАНИЧЕНИЯ Если вызываемая функция изменяет указатель на корен дерева, то последствия будут непредсказуемы.