.\" Formatted or processed versions of this manual, if unaccompanied by
.\" the source, must acknowledge the copyright and authors of this work.
.\"
-.\" 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>
+.\"*******************************************************************
.\"
-.TH TSEARCH 3 2008-09-23 "GNU" "Linux Programmer's Manual"
+.\" This file was generated with po4a. Translate the source file.
+.\"
+.\"*******************************************************************
+.TH TSEARCH 3 2008\-09\-23 GNU "Linux Programmer's Manual"
.SH 名前
tsearch, tfind, tdelete, twalk, tdestroy \- 二分木 (binary tree) の操作
.SH 書式
.nf
-.B #include <search.h>
+\fB#include <search.h>\fP
.sp
-.BI "void *tsearch(const void *" key ", void **" rootp ,
-.BI " int (*" compar ")(const void *, const void *));"
+\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
-.BI "void *tfind(const void *" key ", const void **" rootp ,
-.BI " int (*" compar ")(const void *, const void *));"
+\fBvoid *tfind(const void *\fP\fIkey\fP\fB, const void **\fP\fIrootp\fP\fB,\fP
+\fB int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
.sp
-.BI "void *tdelete(const void *" key ", void **" rootp ,
-.BI " int (*" compar ")(const void *, const void *));"
+\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
-.BI "void twalk(const void *" root ", void (*" action ")(const void *" nodep ,
-.BI " const VISIT " which ,
-.BI " const int " depth "));"
+\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
-.BR "#define _GNU_SOURCE" " /* feature_test_macros(7) 参照 */"
+\fB#define _GNU_SOURCE\fP /* feature_test_macros(7) 参照 */
.br
-.B #include <search.h>
+\fB#include <search.h>\fP
.sp
-.BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
+\fBvoid tdestroy(void *\fP\fIroot\fP\fB, void (*\fP\fIfree_node\fP\fB)(void *\fP\fInodep\fP\fB));\fP
.fi
.SH 説明
-.BR tsearch (),
-.BR tfind (),
-.BR twalk (),
-.BR tdelete ()
-は
-二分木を操作する関数である。
-これらの関数は Knuth (6.2.2) Algorithm T に基づいている。
-木構造における各ノードの最初のフィールドは、対応するデータ・
-アイテムへのポインタである。
-(参照先のデータは、呼び出しプログラムで用意する。)
-\fIcompar\fP は比較ルーチンへのポインタである。
-比較ルーチンは、アイテムへのポインタ 2 つを引数に持つ。
-比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
-「小さい、等しい、大きい」によって、
-「負、0、正」の整数値でなければならない。
+\fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP(), \fBtdelete\fP() は 二分木を操作する関数である。 これらの関数は
+Knuth (6.2.2) Algorithm T に基づいている。 木構造における各ノードの最初のフィールドは、対応するデータ・
+アイテムへのポインタである。 (参照先のデータは、呼び出しプログラムで用意する。) \fIcompar\fP は比較ルーチンへのポインタである。
+比較ルーチンは、アイテムへのポインタ 2 つを引数に持つ。 比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
+「小さい、等しい、大きい」によって、 「負、0、正」の整数値でなければならない。
.PP
-.BR tsearch ()
-は、木構造からアイテムを検索する関数である。
-\fIkey\fP は、検索するアイテムへのポインタである。
-\fIrootp\fP は木構造の根へのポインタへのポインタである。
-木構造がノードを含まない場合、\fIrootp\fP の参照している変数は
-NULL に設定されていなければならない。
-木構造にアイテムが見つかった場合、
-.BR tsearch ()
-はそのアイテムへのポインタを返す。
-見つからなかった場合は、アイテムを木構造に追加し、
-追加したアイテムへのポインタを返す。
+\fBtsearch\fP() は、木構造からアイテムを検索する関数である。 \fIkey\fP は、検索するアイテムへのポインタである。 \fIrootp\fP
+は木構造の根へのポインタへのポインタである。 木構造がノードを含まない場合、\fIrootp\fP の参照している変数は NULL
+に設定されていなければならない。 木構造にアイテムが見つかった場合、 \fBtsearch\fP() はそのアイテムへのポインタを返す。
+見つからなかった場合は、アイテムを木構造に追加し、 追加したアイテムへのポインタを返す。
.PP
-.BR tfind ()
-は、
-.BR tsearch ()
-に似ているが、
-アイテムが見つからなかった場合 NULL を返す点が異なる。
+\fBtfind\fP() は、 \fBtsearch\fP() に似ているが、 アイテムが見つからなかった場合 NULL を返す点が異なる。
.PP
-.BR tdelete ()
-は木構造からアイテムを削除する。
-引数は
-.BR tsearch ()
-と同じである。
+\fBtdelete\fP() は木構造からアイテムを削除する。 引数は \fBtsearch\fP() と同じである。
.PP
-.BR twalk ()
-は、二分木を深さ優先 (depth-first) で、
-左から右にたどっていく関数である。
-\fIroot\fP は起点となるノードへのポインタである。
-\fIroot\fP に根以外のノードを指定すると、部分木が対象となる。
-.BR twalk ()
-は、ノードを訪れる度に
-(つまり、内部ノードに対しては 3 回、葉に対しては 1 回)
-ユーザ関数 \fIaction\fP を呼び出す。
-\fIaction\fP には以下の順に 3 つの引数が与えられる。
-最初の引数は訪れたノードへのポインタである。
-2 つ目の引数には、内部ノードの場合は訪問回数に応じて
-\fBpreorder\fP, \fBpostorder\fP, \fBendorder\fP が、
-葉の場合は \fBleaf\fP が与えられる。
-(これらのシンボルは \fI<search.h>\fP で定義されている。)
-3 つ目の引数はノードの深さで、根の場合は 0 である。
+\fBtwalk\fP() は、二分木を深さ優先 (depth\-first) で、 左から右にたどっていく関数である。 \fIroot\fP
+は起点となるノードへのポインタである。 \fIroot\fP に根以外のノードを指定すると、部分木が対象となる。 \fBtwalk\fP()
+は、ノードを訪れる度に (つまり、内部ノードに対しては 3 回、葉に対しては 1 回) ユーザ関数 \fIaction\fP を呼び出す。
+\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 という名前を選ぶのは少し紛らわしい。)
+(より一般的には、\fBpreorder\fP, \fBpostorder\fP, \fBendorder\fP は \fBpreorder\fP, \fBinorder\fP,
+\fBpostorder\fP として知られている: それぞれ、子要素を辿る前・最初の子要素を辿った後かつ 2 番目の子要素を辿る前・
+子要素を辿った後ということを表している。 よって \fBpost\%order\fP という名前を選ぶのは少し紛らわしい。)
.PP
-.BR tdestroy ()
-は \fIroot\fP が指す木構造全体を削除し、
-.BR tsearch ()
-関数で確保されたリソースを全て解放する。
-木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。
-データへのポインタがこの関数の引数として渡される。
-そのような動作が必要でなければ、
-\fIfree_node\fP は何もしない関数へのポインタでなければならない。
+\fBtdestroy\fP() は \fIroot\fP が指す木構造全体を削除し、 \fBtsearch\fP() 関数で確保されたリソースを全て解放する。
+木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。 データへのポインタがこの関数の引数として渡される。
+そのような動作が必要でなければ、 \fIfree_node\fP は何もしない関数へのポインタでなければならない。
.SH 返り値
-.BR tsearch ()
-は、木構造に見つかったアイテムか、
-新しく追加したアイテムへのポインタを返す。
-メモリの不足のためアイテムを追加できなかった場合は NULL を返す。
-.BR tfind ()
-は、アイテムへのポインタを返す。
-一致するアイテムが見つからない場合は NULL を返す。
-検索条件に一致する要素が複数ある場合、返される値は不定である。
+\fBtsearch\fP() は、木構造に見つかったアイテムか、 新しく追加したアイテムへのポインタを返す。
+メモリの不足のためアイテムを追加できなかった場合は NULL を返す。 \fBtfind\fP() は、アイテムへのポインタを返す。
+一致するアイテムが見つからない場合は NULL を返す。 検索条件に一致する要素が複数ある場合、返される値は不定である。
.PP
-.BR tdelete ()
-は削除したアイテムの親へのポインタを返す。
-アイテムが見つからなかった場合は NULL を返す。
+\fBtdelete\fP() は削除したアイテムの親へのポインタを返す。 アイテムが見つからなかった場合は NULL を返す。
.PP
-\fIrootp\fP が NULL の場合、
-.BR tsearch (),
-.BR tfind (),
-.BR tdelete ()
-は NULL を返す。
+\fIrootp\fP が NULL の場合、 \fBtsearch\fP(), \fBtfind\fP(), \fBtdelete\fP() は NULL を返す。
.SH 準拠
-SVr4, POSIX.1-2001.
-関数
-.BR tdestroy ()
-は GNU の拡張である。
+SVr4, POSIX.1\-2001. 関数 \fBtdestroy\fP() は GNU の拡張である。
.SH 注意
-.BR twalk ()
-は根へのポインタを引数にとるが、
-ほかの関数は根へのポインタへのポインタである。
+\fBtwalk\fP() は根へのポインタを引数にとるが、 ほかの関数は根へのポインタへのポインタである。
.PP
-.BR twalk ()
-においては、\fBpostorder\fP は
-「左の部分木の後で、右の部分木の前」を意味している。
-しかし、人によってはこれを "inorder" と呼んで、
-"postorder" を「両方の部分木の後」とする場合もある。
+\fBtwalk\fP() においては、\fBpostorder\fP は 「左の部分木の後で、右の部分木の前」を意味している。 しかし、人によってはこれを
+"inorder" と呼んで、 "postorder" を「両方の部分木の後」とする場合もある。
.PP
-.BR tdelete ()
-は、削除したノードの使用していたメモリを解放するが、
-ノードに対応するデータのメモリは、ユーザが解放しなければならない。
+\fBtdelete\fP() は、削除したノードの使用していたメモリを解放するが、 ノードに対応するデータのメモリは、ユーザが解放しなければならない。
.PP
-下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引数にして
-呼び出されて以降は、
-.BR twalk ()
-がそのノードを参照しないことを前提としている。
-これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
+下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引数にして 呼び出されて以降は、 \fBtwalk\fP()
+がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
.SH 例
-以下のプログラムは 12 個の乱数を二分木に挿入した後、
-挿入した数を順番に出力する (挿入の際、重複した乱数は 1 つにまとめられる)。
+以下のプログラムは 12 個の乱数を二分木に挿入した後、 挿入した数を順番に出力する (挿入の際、重複した乱数は 1 つにまとめられる)。
.sp
.nf
#define _GNU_SOURCE /* Expose declaration of tdestroy() */
p = malloc(n);
if (p)
return p;
- fprintf(stderr, "insufficient memory\\n");
+ fprintf(stderr, "insufficient memory\en");
exit(EXIT_FAILURE);
}
break;
case postorder:
datap = *(int **) nodep;
- printf("%6d\\n", *datap);
+ printf("%6d\en", *datap);
break;
case endorder:
break;
case leaf:
datap = *(int **) nodep;
- printf("%6d\\n", *datap);
+ printf("%6d\en", *datap);
break;
}
}
}
.fi
.SH 関連項目
-.BR bsearch (3),
-.BR hsearch (3),
-.BR lsearch (3)
-.BR qsort (3)
+\fBbsearch\fP(3), \fBhsearch\fP(3), \fBlsearch\fP(3) \fBqsort\fP(3)
OSDN Git Service
