Партнёры:
Хостинг:
#include <search.h>
void *tsearch(const void *key, void **rootp,
int(*compar)(const void *, const void *));
void *tfind(const void *key, const void **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
#include <search.h>
void tdestroy (void *root, void (*free_node)(void *nodep));
tsearch производит поиск элемента данных в "дереве". key указывает на искомый элемент. rootp указывает на переменную, являющуюся, в свою очередь, указателем на корень "дерева". Если "дерево" пусто, то переменная rootp должна указывать на значение NULL. Если данные найдены, то tsearch возвращает на них указатель. Если данные не найдены, то tsearch добавляет их и возвращает указатель на новый элемент.
tfind похожа на tsearch, только в случае, если элемент не найден, возвращается значение NULL.
tdelete удаляет значение из "дерева". Аргументы аналогичны функции tsearch.
twalk предоставляет Вам средство для последовательного курсирования по всему "дереву". root указывает на начальный элемент обхода. Если этот узел не является корневым, то будет пройдена только часть дерева. twalk вызывает пользовательскую функцию action каждому посещаемому узлу (то есть три раза внутреннему узлу и один - конечному узлу "листвы"). action каждый раз получает три аргумента. Первый - указатель на посещаемый узел. Второй - целое число, принимающее значения preorder, postorder и endorder (в зависимости от того, в первый, второй или третий раз посещается внутрений узел) или leaf, если это единственый визит конечного узла. Эти символы определены в <search.h>. Третий аргумент - это глубина текущего "погружения" в "дерево", для корня она равна нулю.
(В общем случае, функции preorder, postorder и endorder известны как preorder, inorder и postorder: перед посещением узлов, после первого посещения и перед вторым, и после посещения. Таким образом, выбор имени postorder приводит к путанице.)
Функция tdestroy() удаляет все дерево rootp, высвобождая все ресурсы занятые функцией tsearch(). Для получения данных о каждом узле дерева вызывается функция free_node. Указатель на данные является аргументом функции. Функция вызывается в любом случае.
tdelete возвращает указатель на родительский элемент удаленного элемента или NULL, если элемент не найден.
tsearch, tfind и tdelete также возвращают NULL, если rootp - это запись, указывающая на NULL.
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;
}
|
Закладки на сайте Проследить за страницей |
Created 1996-2024 by Maxim Chirkov Добавить, Поддержать, Вебмастеру |