TSEARCH - Linux手册页

时间:2019-08-20 18:01:31  来源:igfitidea点击:

Linux程序员手册 第3部分
更新日期: 2020-06-09

名称

tsearch,tfind,tdelete,twalk,tdestroy-管理二进制搜索树

语法

#include <search.h>

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

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, VISIT which,
                               int depth));

#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include <search.h>

void twalk_r(const void *root,
                void (*action)(const void *nodep, VISIT which,
                               void *closure),
                void *closure);

void tdestroy(void *root, void (*free_node)(void *nodep));

说明

tsearch(),tfind(),twalk()和tdelete()管理二进制搜索树。它们是从Knuth(6.2.2)算法T推广而来的。树的每个节点中的第一个字段是指向相应数据项的指针。 (调用程序必须存储实际数据。)比较点指向比较例程,该例程需要指向两个项目的指针。它应返回一个负数,零值或正数的整数,具体取决于第一项是否小于,等于或大于第二项。

tsearch()在树中搜索项目。关键点指向要搜索的项目。 rootp指向一个变量,该变量指向树的根。如果树为空,则rootp指向的变量应设置为NULL。如果在树中找到该项目,则tsearch()返回一个指向相应树节点的指针。 (换句话说,tsearch()返回一个指向数据项的指针。)如果找不到该项目,则tsearch()将其添加,并返回一个指向相应树节点的指针。

tfind()类似于tsearch(),不同之处在于如果未找到该项目,则tfind()返回NULL。

tdelete()从树中删除一个项目。其参数与tsearch()相同。

twalk()执行二叉树的深度优先,从左到右遍历。根指向遍历的起始节点。如果该节点不是根节点,则仅访问树的一部分。每次访问节点时,twalk()都会调用用户函数操作(即,内部节点访问3次,叶子访问一次)。反过来,动作需要三个参数。第一个参数是指向要访问的节点的指针。节点的结构未指定,但是可以将指针转换为指向元素的指针,以访问存储在节点内的元素。应用程序不得修改此参数所指向的结构。第二个参数是一个整数,它取值顺序,后序或终止顺序之一,具体取决于这是对内部节点的第一次访问,第二次或第三次访问,或者值叶子(如果这是对叶子节点的单次访问) 。 (这些符号在中定义。)第三个参数是节点的深度。根节点的深度为零。

(更常见的是,预购,后购和终止购货被称为预购,订购和后购:在拜访孩子之前,第一次之后,第二次之前以及拜访孩子之后。因此,对名字postorder的选择相当混乱。 )

twalk_r()与twalk()类似,但是不使用depth参数,而是将闭合参数指针传递给操作回调的每次调用,而不会更改。该指针可用于以线程安全的方式在回调函数之间传递信息,而无需求助于全局变量。

tdestroy()删除根指向的整个树,从而释放tsearch()函数分配的所有资源。对于每个树节点中的数据,将调用函数free_node。指向数据的指针作为函数的参数传递。如果不需要进行此类工作,则free_node必须指向不执行任何操作的函数。

返回值

tsearch()返回指向树中匹配节点或新添加节点的指针,如果没有足够的内存来添加该项,则返回NULL。 tfind()返回指向该节点的指针,如果找不到匹配项,则返回NULL。如果有多个与键匹配的项目,则未指定返回节点的项目。

tdelete()返回指向已删除节点的父节点的指针,如果未找到该项目,则返回NULL。如果删除的节点是根节点,则tdelete()返回一个不能访问的悬空指针。

如果rootp在输入时为NULL,则tsearch(),tfind()和tdelete()也会返回NULL。

版本

从2.30版开始,glibc中提供了twalk_r()。

属性

有关本节中使用的术语的说明,请参见attribute(7)。

InterfaceAttributeValue
tsearch(),tfind(),
tdelete()
Thread safetyMT-Safe race:rootp
twalk()Thread safetyMT-Safe race:root
twalk_r()Thread safetyMT-Safe race:root
tdestroy()Thread safetyMT-Safe

遵循规范

POSIX.1-2001,POSIX.1-2008,SVr4。函数tdestroy()和twalk_r()是GNU扩展。

备注

twalk()使用指向根的指针,而其他函数使用指向指向根的变量的指针。

tdelete()释放树中节点所需的内存。用户负责为相应的数据释放内存。

该示例程序取决于以下事实:在使用参数" endorder"或" leaf"调用用户函数后,twalk()不再进一步引用节点。这适用于GNU库实现,但System V文档中没有。

示例

下面的程序将十二个随机数插入二叉树中,其中重复的数字被折叠,然后按顺序打印数字。

#define _GNU_SOURCE     /* Expose declaration of tdestroy() */
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

static void *root = NULL;

static void *
xmalloc(unsigned n)
{
    void *p;
    p = malloc(n);
    if (p)
        return p;
    fprintf(stderr, "insufficient memory\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, VISIT which, 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);
}

另外参见

bsearch(3),hsearch(3),lsearch(3),qsort(3)

出版信息

这个页面是Linux手册页项目5.08版的一部分。有关项目的说明、有关报告错误的信息以及此页面的最新版本,请访问https://www.kernel.org/doc/man-pages/