tsearch

Autres langues

Langue: ja

Autres versions - même langue

Version: 1995-09-24 (openSuse - 09/10/07)

Section: 3 (Bibliothèques de fonctions)

Sommaire

̾Á°

tsearch, tfind, tdelete, twalk, tdestroy - ÆóʬÌÚ (binary tree) ¤òÁàºî¤¹¤ë

½ñ¼°


#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(), tfind(), twalk(), tdelete() ¤Ï ÆóʬÌÚ¤òÁàºî¤¹¤ë´Ø¿ô¤Ç¤¢¤ë¡£ ¤³¤ì¤é¤Î´Ø¿ô¤Ï Knuth (6.2.2) Algorithm T ¤Ë´ð¤Å¤¤¤Æ¤¤¤ë¡£ ÌÚ¹½Â¤¤Ë¤ª¤±¤ë³Æ¥Î¡¼¥É¤ÎºÇ½é¤Î¥Õ¥£¡¼¥ë¥É¤Ï¡¢Âбþ¤¹¤ë¥Ç¡¼¥¿¡¦ ¥¢¥¤¥Æ¥à¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤¢¤ë¡£ (»²¾ÈÀè¤Î¥Ç¡¼¥¿¤Ï¡¢¸Æ¤Ó½Ð¤·¥×¥í¥°¥é¥à¤ÇÍÑ°Õ¤¹¤ë¡£) compar ¤ÏÈæ³Ó¥ë¡¼¥Á¥ó¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤¢¤ë¡£ Èæ³Ó¥ë¡¼¥Á¥ó¤Ï¡¢¥¢¥¤¥Æ¥à¤Ø¤Î¥Ý¥¤¥ó¥¿ 2 ¤Ä¤ò°ú¿ô¤Ë»ý¤Ä¡£ Èæ³Ó¥ë¡¼¥Á¥ó¤ÎÊÖ¤êÃͤϡ¢1 ¤ÄÌܤΥ¢¥¤¥Æ¥à¤¬ 2 ¤ÄÌܤΥ¢¥¤¥Æ¥à¤è¤ê¤â ¡Ö¾®¤µ¤¤¡¢Åù¤·¤¤¡¢Â礭¤¤¡×¤Ë¤è¤Ã¤Æ¡¢ ¡ÖÉé¡¢0¡¢Àµ¡×¤ÎÀ°¿ôÃͤǤʤ±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£

tsearch() ¤Ï¡¢ÌÚ¹½Â¤¤«¤é¥¢¥¤¥Æ¥à¤ò¸¡º÷¤¹¤ë´Ø¿ô¤Ç¤¢¤ë¡£ key ¤Ï¡¢¸¡º÷¤¹¤ë¥¢¥¤¥Æ¥à¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤¢¤ë¡£ rootp ¤ÏÌÚ¹½Â¤¤Îº¬¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤¢¤ë¡£ ÌÚ¹½Â¤¤¬¥Î¡¼¥É¤ò´Þ¤Þ¤Ê¤¤¾ì¹ç¡¢rootp ¤Î»²¾È¤·¤Æ¤¤¤ëÊÑ¿ô¤Ï NULL ¤ËÀßÄꤵ¤ì¤Æ¤¤¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£ ÌÚ¹½Â¤¤Ë¥¢¥¤¥Æ¥à¤¬¸«¤Ä¤«¤Ã¤¿¾ì¹ç¡¢ tsearch() ¤Ï¤½¤Î¥¢¥¤¥Æ¥à¤Ø¤Î¥Ý¥¤¥ó¥¿¤òÊÖ¤¹¡£ ¸«¤Ä¤«¤é¤Ê¤«¤Ã¤¿¾ì¹ç¤Ï¡¢¥¢¥¤¥Æ¥à¤òÌÚ¹½Â¤¤ËÄɲä·¡¢ Äɲä·¤¿¥¢¥¤¥Æ¥à¤Ø¤Î¥Ý¥¤¥ó¥¿¤òÊÖ¤¹¡£

tfind() ¤Ï¡¢ tsearch() ¤Ë»÷¤Æ¤¤¤ë¤¬¡¢ ¥¢¥¤¥Æ¥à¤¬¸«¤Ä¤«¤é¤Ê¤«¤Ã¤¿¾ì¹ç NULL ¤òÊÖ¤¹ÅÀ¤¬°Û¤Ê¤ë¡£

tdelete() ¤ÏÌÚ¹½Â¤¤«¤é¥¢¥¤¥Æ¥à¤òºï½ü¤¹¤ë¡£ °ú¿ô¤Ï tsearch() ¤ÈƱ¤¸¤Ç¤¢¤ë¡£

twalk() ¤Ï¡¢ÆóʬÌÚ¤ò¿¼¤µÍ¥Àè (depth-first) ¤Ç¡¢ º¸¤«¤é±¦¤Ë¤¿¤É¤Ã¤Æ¤¤¤¯´Ø¿ô¤Ç¤¢¤ë¡£ root ¤Ïµ¯ÅÀ¤È¤Ê¤ë¥Î¡¼¥É¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤¢¤ë¡£ root ¤Ëº¬°Ê³°¤Î¥Î¡¼¥É¤ò»ØÄꤹ¤ë¤È¡¢ÉôʬÌÚ¤¬ÂоݤȤʤ롣 twalk() ¤Ï¡¢¥Î¡¼¥É¤òˬ¤ì¤ëÅÙ¤Ë (¤Ä¤Þ¤ê¡¢ÆâÉô¥Î¡¼¥É¤ËÂФ·¤Æ¤Ï 3 ²ó¡¢ÍÕ¤ËÂФ·¤Æ¤Ï 1 ²ó) ¥æ¡¼¥¶´Ø¿ô action ¤ò¸Æ¤Ó½Ð¤¹¡£ action ¤Ë¤Ï°Ê²¼¤Î½ç¤Ë 3 ¤Ä¤Î°ú¿ô¤¬Í¿¤¨¤é¤ì¤ë¡£ ºÇ½é¤Î°ú¿ô¤Ïˬ¤ì¤¿¥Î¡¼¥É¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤¢¤ë¡£ 2 ¤ÄÌܤΰú¿ô¤Ë¤Ï¡¢ÆâÉô¥Î¡¼¥É¤Î¾ì¹ç¤ÏˬÌä²ó¿ô¤Ë±þ¤¸¤Æ preorder, postorder, endorder ¤¬¡¢ Íդξì¹ç¤Ï leaf ¤¬Í¿¤¨¤é¤ì¤ë¡£ (¤³¤ì¤é¤Î¥·¥ó¥Ü¥ë¤Ï <search.h> ¤ÇÄêµÁ¤µ¤ì¤Æ¤¤¤ë¡£) 3 ¤ÄÌܤΰú¿ô¤Ï¥Î¡¼¥É¤Î¿¼¤µ¤Ç¡¢º¬¤Î¾ì¹ç¤Ï 0 ¤Ç¤¢¤ë¡£

(¤è¤ê°ìÈÌŪ¤Ë¤Ï¡¢preorder, postorder, endorder ¤Ï preorder, inorder, postorder ¤È¤·¤ÆÃΤé¤ì¤Æ¤¤¤ë: ¤½¤ì¤¾¤ì¡¢»ÒÍ×ÁǤòé¤ëÁ°¡¦ºÇ½é¤Î»ÒÍ×ÁǤòé¤Ã¤¿¸å¤«¤Ä 2 ÈÖÌܤλÒÍ×ÁǤòé¤ëÁ°¡¦ »ÒÍ×ÁǤòé¤Ã¤¿¸å¤È¤¤¤¦¤³¤È¤òɽ¤·¤Æ¤¤¤ë¡£ ¤è¤Ã¤Æ postorder ¤È¤¤¤¦Ì¾Á°¤òÁª¤Ö¤Î¤Ï¾¯¤·Ê¶¤é¤ï¤·¤¤¡£)

tdestroy() ¤Ï root ¤¬»Ø¤¹ÌÚ¹½Â¤Á´ÂΤòºï½ü¤·¡¢ tsearch() ´Ø¿ô¤Ç³ÎÊݤµ¤ì¤¿¥ê¥½¡¼¥¹¤òÁ´¤Æ²òÊü¤¹¤ë¡£ ÌÚ¹½Â¤¤Î³Æ¥Î¡¼¥É¤Ë¤Ä¤¤¤Æ¡¢´Ø¿ô free_node ¤¬¸Æ¤Ó½Ð¤µ¤ì¤ë¡£ ¥Ç¡¼¥¿¤Ø¤Î¥Ý¥¤¥ó¥¿¤¬¤³¤Î´Ø¿ô¤Î°ú¿ô¤È¤·¤ÆÅϤµ¤ì¤ë¡£ ¤½¤Î¤è¤¦¤ÊÆ°ºî¤¬É¬ÍפǤʤ±¤ì¤Ð¡¢ free_node ¤Ï²¿¤â¤·¤Ê¤¤´Ø¿ô¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£

ÊÖ¤êÃÍ

tsearch() ¤Ï¡¢ÌÚ¹½Â¤¤Ë¸«¤Ä¤«¤Ã¤¿¥¢¥¤¥Æ¥à¤«¡¢ ¿·¤·¤¯Äɲä·¤¿¥¢¥¤¥Æ¥à¤Ø¤Î¥Ý¥¤¥ó¥¿¤òÊÖ¤¹¡£ ¥á¥â¥ê¤ÎÉÔ­¤Î¤¿¤á¥¢¥¤¥Æ¥à¤òÄɲäǤ­¤Ê¤«¤Ã¤¿¾ì¹ç¤Ï NULL ¤òÊÖ¤¹¡£ tfind() ¤Ï¡¢¥¢¥¤¥Æ¥à¤Ø¤Î¥Ý¥¤¥ó¥¿¤òÊÖ¤¹¡£ °ìÃפ¹¤ë¥¢¥¤¥Æ¥à¤¬¸«¤Ä¤«¤é¤Ê¤¤¾ì¹ç¤Ï NULL ¤òÊÖ¤¹¡£ ¸¡º÷¾ò·ï¤Ë°ìÃפ¹¤ëÍ×ÁǤ¬Ê£¿ô¤¢¤ë¾ì¹ç¡¢ÊÖ¤µ¤ì¤ëÃͤÏÉÔÄê¤Ç¤¢¤ë¡£

tdelete() ¤Ïºï½ü¤·¤¿¥¢¥¤¥Æ¥à¤Î¿Æ¤Ø¤Î¥Ý¥¤¥ó¥¿¤òÊÖ¤¹¡£ ¥¢¥¤¥Æ¥à¤¬¸«¤Ä¤«¤é¤Ê¤«¤Ã¤¿¾ì¹ç¤Ï NULL ¤òÊÖ¤¹¡£

rootp ¤¬ NULL ¤Î¾ì¹ç¡¢ tsearch(), tfind(), tdelete() ¤Ï NULL ¤òÊÖ¤¹¡£

½àµò

SVr4, POSIX.1-2001. ´Ø¿ô tdestroy() ¤Ï GNU ¤Î³ÈÄ¥¤Ç¤¢¤ë¡£

Ãí°Õ

twalk() ¤Ïº¬¤Ø¤Î¥Ý¥¤¥ó¥¿¤ò°ú¿ô¤Ë¤È¤ë¤¬¡¢ ¤Û¤«¤Î´Ø¿ô¤Ïº¬¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ç¤¢¤ë¡£

twalk() ¤Ë¤ª¤¤¤Æ¤Ï¡¢postorder ¤Ï ¡Öº¸¤ÎÉôʬÌڤθå¤Ç¡¢±¦¤ÎÉôʬÌÚ¤ÎÁ°¡×¤ò°ÕÌ£¤·¤Æ¤¤¤ë¡£ ¤·¤«¤·¡¢¿Í¤Ë¤è¤Ã¤Æ¤Ï¤³¤ì¤ò "inorder" ¤È¸Æ¤ó¤Ç¡¢ "postorder" ¤ò¡ÖξÊý¤ÎÉôʬÌڤθå¡×¤È¤¹¤ë¾ì¹ç¤â¤¢¤ë¡£

tdelete() ¤Ï¡¢ºï½ü¤·¤¿¥Î¡¼¥É¤Î»ÈÍѤ·¤Æ¤¤¤¿¥á¥â¥ê¤ò²òÊü¤¹¤ë¤¬¡¢ ¥Î¡¼¥É¤ËÂбþ¤¹¤ë¥Ç¡¼¥¿¤Î¥á¥â¥ê¤Ï¡¢¥æ¡¼¥¶¤¬²òÊü¤·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£

²¼¤Î¥×¥í¥°¥é¥àÎã¤Ï¡¢¥æ¡¼¥¶´Ø¿ô¤¬ "endorder" ¤« "leaf" ¤ò°ú¿ô¤Ë¤·¤Æ ¸Æ¤Ó½Ð¤µ¤ì¤Æ°Ê¹ß¤Ï¡¢ twalk() ¤¬¤½¤Î¥Î¡¼¥É¤ò»²¾È¤·¤Ê¤¤¤³¤È¤òÁ°Äó¤È¤·¤Æ¤¤¤ë¡£ ¤³¤ì¤Ï GNU ¥é¥¤¥Ö¥é¥ê¤Î¼ÂÁõ¤Ç¤Ïµ¡Ç½¤¹¤ë¤¬¡¢SysV ¤Î¥Þ¥Ë¥å¥¢¥ë¤Ë¤Ï¸ºß¤·¤Ê¤¤¡£

Îã

°Ê²¼¤Î¥×¥í¥°¥é¥à¤Ï 12 ¸Ä¤ÎÍð¿ô¤òÆóʬÌÚ¤ËÁÞÆþ¤·¤¿¸å¡¢ ÁÞÆþ¤·¤¿¿ô¤ò½çÈ֤˽ÐÎϤ¹¤ë (ÁÞÆþ¤ÎºÝ¡¢½ÅÊ£¤·¤¿Íð¿ô¤Ï 1 ¤Ä¤Ë¤Þ¤È¤á¤é¤ì¤ë)¡£ 

#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, "insufficient memory\n");

    exit(EXIT_FAILURE);

}



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;

    }

}



int

main(void)

{

    int i, *ptr;

    void *val;



    srand(time(NULL));

    for (i = 0; i < 12; i++) {

        ptr = (int *) xmalloc(sizeof(int));

        *ptr = rand() & 0xff;

        val = tsearch((void *) ptr, &root, compare);

        if (val == NULL)

            exit(EXIT_FAILURE);

    }

    twalk(root, action);

    exit(EXIT_SUCCESS);

}

´ØÏ¢¹àÌÜ

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