Tsearch что это за программа
Функции tsearch , tfind , twalk и tdelete позволяют управлять бинарными «деревьями». Они были написаны по книге профессора Knuth (6.2.2) «Algorithm Theory». Первое поле в каждом узле «дерева» является указателем на соответствующий элемент данных. Вызывающая программа должна сохранить действительные данные. compar указывает на процедуру сравнения, которая ставит указатели на два элемента данных. Эта процедура должна возвращать отрицательное, положительное или нулевое значение, если первый элемент меньше, больше второго или равен ему.
tsearch производит поиск элемента данных в «дереве». key указывает на искомый элемент. rootp указывает на переменную, являющуюся, в свою очередь, указателем на корень «дерева». Если «дерево» пусто, то переменная rootp должна указывать на значение NULL . Если данные найдены, то tsearch возвращает на них указатель. Если данные не найдены, то tsearch добавляет их и возвращает указатель на новый элемент.
tfind похожа на tsearch , только в случае, если элемент не найден, возвращается значение NULL .
tdelete удаляет значение из «дерева». Аргументы аналогичны функции tsearch .
twalk предоставляет Вам средство для последовательного курсирования по всему «дереву». root указывает на начальный элемент обхода. Если этот узел не является корневым, то будет пройдена только часть дерева. twalk вызывает пользовательскую функцию action каждому посещаемому узлу (то есть три раза внутреннему узлу и один — конечному узлу «листвы»). action каждый раз получает три аргумента. Первый — указатель на посещаемый узел. Второй — целое число, принимающее значения preorder , postorder и endorder (в зависимости от того, в первый, второй или третий раз посещается внутрений узел) или leaf , если это единственый визит конечного узла. Эти символы определены в . Третий аргумент — это глубина текущего «погружения» в «дерево», для корня она равна нулю.
(В общем случае, функции preorder , postorder и endorder известны как preorder , inorder и postorder : перед посещением узлов, после первого посещения и перед вторым, и после посещения. Таким образом, выбор имени postorder приводит к путанице.)
Функция tdestroy () удаляет все дерево rootp , высвобождая все ресурсы занятые функцией tsearch (). Для получения данных о каждом узле дерева вызывается функция free_node . Указатель на данные является аргументом функции. Функция вызывается в любом случае.
ВОЗВРАЩАЕМЫЕ ЗНАЧЕНИЯ
tsearch возвращает указатель на соответствующий элемент дерева или добавляет элемент и возвращает указатель на него, а также возвращает NULL , если для нового элемента недостаточно памяти. tfind возвращает указатель на элемент или NULL , если совпадений не найдено. Если есть несколько элементов с одинаковым ключом, то неизвестно, какой из них будет возвращен.
tdelete возвращает указатель на родительский элемент удаленного элемента или NULL , если элемент не найден.
tsearch , tfind и tdelete также возвращают NULL , если rootp — это запись, указывающая на NULL .
ПРЕДУПРЕЖДЕНИЯ
twalk ставит указатель на корневой элемент, в то время как другие функции ставят указатель на переменную, содержащую ссылку на корень.
twalk использует postorder , это значит «после левого «поддерева», но перед правым «поддеревом». Некоторые назовут это «inorder» и будут использовать «postorder», что значит «после обоих «поддеревьев».
tdelete освобождает память, необходимую для хранения элемента «дерева». Пользователь отвечает за освобождение памяти, использованной для хранения соответствующих данных.
На описанную в примере программу влияет то, что twalk не делает различий между узлом после вызова пользовательской функции с аргументом «endorder» или «leaf». Он работает в соответствии с реализацией GNU-библиотеки, но может и не работать, согласно документации SysV.
ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ
Приведенная ниже программа вставляет двенадцать случайных чисел в бинарное «дерево», в котором повторяющиеся числа удаляются, а затем печатает их по порядку.
#include search.h> #include stdlib.h> #include stdio.h> #include time.h> void *root=NULL; void *xmalloc(unsigned n) < void *p; p = malloc(n); if(p) return p; fprintf(stderr, "недостаточно памяти\n"); exit(1); > int compare(const void *pa, const void *pb) < if(*(int *)pa < *(int *)pb) return -1; if(*(int *)pa >*(int *)pb) return 1; return 0; > void action(const void *nodep, const VISIT which, const int depth) < int *datap; switch(which) < case preorder: break; case postorder: datap = *(int **)nodep; printf("%6d\n", *datap); break; case endorder: break; case leaf: datap = *(int **)nodep; printf("%6d\n", *datap); break; >return; > int main() < int i, *ptr; void *val; srand(time(NULL)); for (i = 0; i < 12; i++) < if(val == NULL) exit(1); > twalk(root, action); return 0; >
Tsearch что это за программа
#include
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void *tfind(const void *key, void *const *rootp,
int (*compar)(const void *, const void *));
void *tdelete(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void twalk(const void *root, void (*action)(const void *nodep,
const VISIT which,
const int depth));
#define _GNU_SOURCE /* см. feature_test_macros(7) */
#include
void tdestroy(void *root, void (*free_node)(void *nodep));
ОПИСАНИЕ
Функции tsearch(), tfind(), twalk() и tdelete() позволяют работать с двоичным деревом. Они реализуют «Algorithm T» Д. Кнута (6.2.2). Первое поле в каждом узле дерева является указателем на соответствующий элемент данных (вызывающая программа должна хранить реальные данные). Аргумент compar указывает на процедуру сравнения, которой передаются указатели на два элемента данных. Эта процедура должна возвращать отрицательное, нулевое или положительное значение, если первый элемент меньше, равен или больше чем второй. Функция tsearch() ищет в дереве элемент, на который указывает key. Аргумент rootp указывает на переменную, которая указывает на корень дерева. Если дерево пустое, то переменная, на которую ссылается rootp, должна быть равна NULL. Если элемент найден, то tsearch() возвращает указатель на него, иначе tsearch() добавляет его и возвращает указатель на только что созданный элемент. Функция tfind() похожа на tsearch(), за исключением того, что tfind() в случае нулевого результата поиска возвращает NULL. Функция tdelete() удаляет элемент из дерева. Аргументы те же, что и для tsearch(). Функция twalk() выполняет обход дерева, сначала в глубину, затем слева направо. Аргумент root указывает на начальный элемент обхода. Если этот узел не является корневым, то будет пройдена только часть дерева. Функция twalk вызывает пользовательскую функцию action для каждого посещаемого узла (то есть три раза для внутреннего узла и один раз для конечного узла-листа). Функция action получает три аргумента. Первый — указатель на посещаемый узел. Структура узла не определена, но возможно привести указатель к указателю на указатель на элемент, чтобы получить доступ к элементу, хранящемуся внутри узла. Приложение не должно изменять структуру, на которую указывает этот аргумент. Второй — целое число, принимающее значение preorder, postorder или endorder в зависимости от того, в первый, второй или третий раз посещается внутренний узел, или значение leaf, если это единственный просмотр узла-листа. Эти символы определены в . Третий аргумент — это глубина текущего погружения в дерево; для корня она равна нулю. (В общем случае, функции preorder, postorder и endorder известны как preorder, inorder и postorder: перед посещением потомков, после первого посещения и перед вторым и после посещения. Таким образом, выбор имени postorder приводит к путанице.) Функция tdestroy() удаляет всё дерево, на которое указывает rootp, высвобождая все ресурсы, выделенные функцией tsearch(). Для данных каждого узла дерева вызывается функция free_node. Указатель на данные передаётся в аргумент функции. Если делать ничего не нужно, то в free_node нужно указать функцию, которая ничего не делает.
ВОЗВРАЩАЕМОЕ ЗНАЧЕНИЕ
Функция tsearch() возвращает указатель на соответствующий элемент дерева или добавляет элемент и возвращает указатель на него, а также возвращает NULL, если для нового элемента недостаточно памяти. Функция tfind() возвращает указатель на элемент или NULL, если совпадений не найдено. Если есть несколько элементов с одинаковым ключом, то какой из них будет возвращён — не определено. Функция tdelete() возвращает указатель на родителя удалённого элемента, или NULL, если элемент не найден. Функции tsearch(), tfind() и tdelete() также возвращают NULL, если rootp для записи был равен NULL.
АТРИБУТЫ
Описание терминов данного раздела смотрите в attributes(7).
| Интерфейс | Атрибут | Значение |
| tsearch(), tfind(), tdelete() |
безвредность в нитях | безвредно (MT-Safe race:rootp) |
| twalk() | безвредность в нитях | безвредно (MT-Safe race:root) |
| tdestroy() | безвредность в нитях | безвредно (MT-Safe) |
СООТВЕТСТВИЕ СТАНДАРТАМ
POSIX.1-2001, POSIX.1-2008, SVr4. Функция tdestroy() является расширением GNU.
ЗАМЕЧАНИЯ
Функции twalk() передаётся указатель на корень, а остальные функции ожидают указатель на переменную, которая указывает на корень. Функция tdelete() освобождает память, которая необходима для хранения элемента в дереве. Пользователь отвечает за освобождение памяти, использованной для хранения соответствующих данных. Программа в примере зависит от того, что twalk() больше не ссылается на узел после вызова пользовательской функции с аргументом «endorder» или «leaf». Это работает с реализацией библиотеки GNU, но этого нет в документации System V.
ПРИМЕР
Приведённая ниже программа вставляет двенадцать случайных чисел в двоичное дерево, в котором повторяющиеся числа удаляются, а затем печатает их по порядку.
#define _GNU_SOURCE /* для объявления tdestroy() */ #include #include #include #include static void *root = NULL; static void * xmalloc(unsigned n) < void *p; p = malloc(n); if (p) return p; fprintf(stderr, "недостаточно памяти\n"); exit(EXIT_FAILURE); > static int compare(const void *pa, const void *pb) < if (*(int *) pa < *(int *) pb) return -1; if (*(int *) pa >*(int *) pb) return 1; return 0; > static void action(const void *nodep, const VISIT which, const int depth) < int *datap; switch (which) < case preorder: break; case postorder: datap = *(int **) nodep; printf("%6d\n", *datap); break; case endorder: break; case leaf: datap = *(int **) nodep; printf("%6d\n", *datap); break; >> int main(void) < int i, *ptr; void *val; srand(time(NULL)); for (i = 0; i < 12; i++) < ptr = xmalloc(sizeof(int)); *ptr = rand() & 0xff; val = tsearch((void *) ptr, &root, compare); if (val == NULL) exit(EXIT_FAILURE); else if ((*(int **) val) != ptr) free(ptr); >twalk(root, action); tdestroy(root, free); exit(EXIT_SUCCESS); >
Доступные файлы и ссылки:
Этот файл мы отметили как основной. Если вы не знаете что скачивать, то скачивайте его.
TSearch102.zip | jebysfile.altervista.org
MD5: 2094ae8b6364afcac22ccf424ff5faee
✔ Проверено антивирусами
TSearch102.zip | soft.mydiv.net
MD5: 2094ae8b6364afcac22ccf424ff5faee
Внимание! Мы стараемся тщательно проверять все программы, но не гарантируем абсолютную безопасность скачиваемых файлов. Администрация сайта не несет ответственности за содержание файлов, программ и возможный вред от их использования.
Tsearch что это за программа
НАЗВАНИЕ
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 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); > >
ДИАГНОСТИКА
Функция tsearch возвращает пустой указатель NULL, если не хватает свободного пространства для создания нового узла.
Функции tfind и tdelete возвращают пустой указатель NULL, если аргумент rootp равен NULL.
Если данные найдены, то функции tsearch и tfind возвращают указатель на них. В случае неудачного поиска функция tfind возвращает пустой указатель NULL, а функция tsearch возвращает указатель на вставленные данные.
ПРЕДОСТЕРЕЖЕНИЯ
Аргумент root функции twalk имеет на один уровень косвенной адресации меньше, чем аргумент rootp функций tsearch и tdelete.
Термины preorder, postorder и endorder могут толковаться двояко. Функция tsearch использует термины preorder, postorder и endorder для обозначения, соответственно, следующих случаев: доступ к узлу перед доступом к какому-либо его потомку, доступ к узлу после доступа к его левому потомку и перед доступом к правому потомку, доступ к узлу после доступа к обоим потомкам. Часто названные термины используются для указания порядка обхода дерева, что может привести к путанице.
ОГРАНИЧЕНИЯ
Если вызываемая функция изменяет указатель на корень дерева, то последствия будут непредсказуемы.