+++ /dev/null
-.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
-.\"
-.\" %%%LICENSE_START(VERBATIM)
-.\" Permission is granted to make and distribute verbatim copies of this
-.\" manual provided the copyright notice and this permission notice are
-.\" preserved on all copies.
-.\"
-.\" Permission is granted to copy and distribute modified versions of this
-.\" manual under the conditions for verbatim copying, provided that the
-.\" entire resulting derived work is distributed under the terms of a
-.\" permission notice identical to this one.
-.\"
-.\" Since the Linux kernel and libraries are constantly changing, this
-.\" manual page may be incorrect or out-of-date. The author(s) assume no
-.\" responsibility for errors or omissions, or for damages resulting from
-.\" the use of the information contained herein. The author(s) may not
-.\" have taken the same level of care in the production of this manual,
-.\" which is licensed free of charge, as they might when working
-.\" professionally.
-.\"
-.\" Formatted or processed versions of this manual, if unaccompanied by
-.\" the source, must acknowledge the copyright and authors of this work.
-.\" %%%LICENSE_END
-.\"
-.\"*******************************************************************
-.\"
-.\" This file was generated with po4a. Translate the source file.
-.\"
-.\"*******************************************************************
-.\"
-.\" Japanese Version Copyright (c) 1999 ishikawa, keisuke
-.\" all rights reserved.
-.\" Translated Tue Mar 9 08:21:04 JST 1999
-.\" by ishikawa, keisuke <ishikawa@sgk.gr.jp>
-.\" Updated & Modified Sun Jan 20 11:31:46 JST 2002
-.\" by Yuichi SATO <ysato@h4.dion.ne.jp>
-.\" Updated 2013-05-06, Akihiro MOTOKI <amotoki@gmail.com>
-.\"
-.TH TSEARCH 3 2014\-05\-28 GNU "Linux Programmer's Manual"
-.SH 名前
-tsearch, tfind, tdelete, twalk, tdestroy \- 二分木 (binary tree) の操作
-.SH 書式
-.nf
-\fB#include <search.h>\fP
-.sp
-\fBvoid *tsearch(const void *\fP\fIkey\fP\fB, void **\fP\fIrootp\fP\fB,\fP
-\fB int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
-.sp
-\fBvoid *tfind(const void *\fP\fIkey\fP\fB, void *const *\fP\fIrootp\fP\fB,\fP
-\fB int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
-.sp
-\fBvoid *tdelete(const void *\fP\fIkey\fP\fB, void **\fP\fIrootp\fP\fB,\fP
-\fB int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
-.sp
-\fBvoid twalk(const void *\fP\fIroot\fP\fB, void (*\fP\fIaction\fP\fB)(const void *\fP\fInodep\fP\fB,\fP
-\fB const VISIT \fP\fIwhich\fP\fB,\fP
-\fB const int \fP\fIdepth\fP\fB));\fP
-.sp
-\fB#define _GNU_SOURCE\fP /* feature_test_macros(7) 参照 */
-.br
-\fB#include <search.h>\fP
-.sp
-\fBvoid tdestroy(void *\fP\fIroot\fP\fB, void (*\fP\fIfree_node\fP\fB)(void *\fP\fInodep\fP\fB));\fP
-.fi
-.SH 説明
-\fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP(), \fBtdelete\fP() は 二分木を操作する関数である。 これらの関数は
-Knuth (6.2.2) Algorithm T に基づいている。 木構造における各ノードの最初のフィールドは、対応するデータ
-アイテムへのポインターである。 (参照先のデータは、呼び出しプログラムで用意する。) \fIcompar\fP は比較ルーチンへのポインターである。
-比較ルーチンは、アイテムへのポインター 2 つを引き数に持つ。 比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
-「小さい、等しい、大きい」によって、 「負、0、正」の整数値でなければならない。
-.PP
-\fBtsearch\fP() は、木構造からアイテムを検索する関数である。 \fIkey\fP は、検索するアイテムへのポインターである。 \fIrootp\fP
-は木構造の根へのポインターへのポインターである。 木構造がノードを含まない場合、\fIrootp\fP の参照している変数は NULL
-に設定されていなければならない。 木構造にアイテムが見つかった場合、 \fBtsearch\fP() はそのアイテムへのポインターを返す。
-見つからなかった場合は、アイテムを木構造に追加し、 追加したアイテムへのポインターを返す。
-.PP
-\fBtfind\fP() は、 \fBtsearch\fP() に似ているが、 アイテムが見つからなかった場合 NULL を返す点が異なる。
-.PP
-\fBtdelete\fP() は木構造からアイテムを削除する。 引き数は \fBtsearch\fP() と同じである。
-.PP
-\fBtwalk\fP() は、二分木を深さ優先 (depth\-first) で、 左から右にたどっていく関数である。 \fIroot\fP
-は起点となるノードへのポインターである。 \fIroot\fP に根以外のノードを指定すると、部分木が対象となる。 \fBtwalk\fP()
-は、ノードを訪れる度にユーザー関数 \fIaction\fP を呼び出す (内部ノードに対しては 3 回、葉に対しては 1 回呼び出しが行われる)。
-\fIaction\fP には以下の順に 3 つの引き数が与えられる。 最初の引き数は訪れたノードへのポインターである。 ノードの構造体は規定されていないが、
-ポインターを要素へのポインターのポインターにキャストし、 ノードに格納された要素にアクセスすることができる。
-アプリケーションは、この引き数が指す構造体を変更してはならない。 2 番目の引き数には、内部ノードの場合は訪問回数に応じて \fBpreorder\fP,
-\fBpostorder\fP, \fBendorder\fP のいずれかの整数が、 葉を最初に訪れた場合は \fBleaf\fP の値が渡される (これらのシンボルは
-\fI<search.h>\fP で定義されている)。 3 番目の引き数はノードの深さで、根の場合は深さ 0 である。
-.PP
-(より一般的には、\fBpreorder\fP, \fBpostorder\fP, \fBendorder\fP は \fBpreorder\fP, \fBinorder\fP,
-\fBpostorder\fP として知られている: それぞれ、子要素を辿る前・最初の子要素を辿った後かつ 2 番目の子要素を辿る前・
-子要素を辿った後ということを表している。 よって \fBpost\%order\fP という名前を選ぶのは少し紛らわしい。)
-.PP
-\fBtdestroy\fP() は \fIroot\fP が指す木構造全体を削除し、 \fBtsearch\fP() 関数で確保されたリソースを全て解放する。
-木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。 データへのポインターがこの関数の引き数として渡される。
-そのような動作が必要でなければ、 \fIfree_node\fP は何もしない関数へのポインターでなければならない。
-.SH 返り値
-\fBtsearch\fP() は、木構造に見つかったアイテムか、 新しく追加したアイテムへのポインターを返す。
-メモリーの不足のためアイテムを追加できなかった場合は NULL を返す。 \fBtfind\fP() は、アイテムへのポインターを返す。
-一致するアイテムが見つからない場合は NULL を返す。 検索条件に一致する要素が複数ある場合、返される値は不定である。
-.PP
-\fBtdelete\fP() は削除したアイテムの親へのポインターを返す。 アイテムが見つからなかった場合は NULL を返す。
-.PP
-\fIrootp\fP が NULL の場合、 \fBtsearch\fP(), \fBtfind\fP(), \fBtdelete\fP() は NULL を返す。
-.SH 準拠
-SVr4, POSIX.1\-2001. 関数 \fBtdestroy\fP() は GNU の拡張である。
-.SH 注意
-\fBtwalk\fP() は根へのポインターを引き数にとるが、 ほかの関数は根へのポインターへのポインターである。
-.PP
-\fBtdelete\fP() は、削除したノードの使用していたメモリーを解放するが、
-ノードに対応するデータのメモリーは、ユーザーが解放しなければならない。
-.PP
-下のプログラム例は、ユーザー関数が "endorder" か "leaf" を引き数にして 呼び出されて以降は、 \fBtwalk\fP()
-がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
-.SH 例
-以下のプログラムは 12 個の乱数を二分木に挿入した後、 挿入した数を順番に出力する (挿入の際、重複した乱数は 1 つにまとめられる)。
-.sp
-.nf
-#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\en");
- 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\en", *datap);
- break;
- case endorder:
- break;
- case leaf:
- datap = *(int **) nodep;
- printf("%6d\en", *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);
-}
-.fi
-.SH 関連項目
-\fBbsearch\fP(3), \fBhsearch\fP(3), \fBlsearch\fP(3) \fBqsort\fP(3)
-.SH この文書について
-この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.79 の一部
-である。プロジェクトの説明とバグ報告に関する情報は
-http://www.kernel.org/doc/man\-pages/ に書かれている。
OSDN Git Service
