.\" 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"
-.\"O .SH NAME
+.\" This file was generated with po4a. Translate the source file.
+.\"
+.\"*******************************************************************
+.TH TSEARCH 3 2008\-09\-23 GNU "Linux Programmer's Manual"
.SH 名前
-.\"O tsearch, tfind, tdelete, twalk, tdestroy \- manage a binary tree
tsearch, tfind, tdelete, twalk, tdestroy \- 二分木 (binary tree) の操作
-.\"O .SH SYNOPSIS
.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
-.\"O .BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
-.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
-.\"O .SH DESCRIPTION
.SH 説明
-.\"O .BR tsearch (),
-.\"O .BR tfind (),
-.\"O .BR twalk (),
-.\"O and
-.\"O .BR tdelete ()
-.\"O manage a
-.\"O binary tree.
-.\"O They are generalized from Knuth (6.2.2) Algorithm T.
-.\"O The first field in each node of the tree is a pointer to the
-.\"O corresponding data item.
-.\"O (The calling program must store the actual data.)
-.\"O \fIcompar\fP points to a comparison routine, which takes
-.\"O pointers to two items.
-.\"O It should return an integer which is negative,
-.\"O zero, or positive, depending on whether the first item is less than,
-.\"O equal to, or greater than the second.
-.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
-.\"O .BR tsearch ()
-.\"O searches the tree for an item.
-.\"O \fIkey\fP points to the item to be searched for.
-.\"O \fIrootp\fP points to a
-.\"O variable which points to the root of the tree.
-.\"O If the tree is empty,
-.\"O then the variable that \fIrootp\fP points to should be set to NULL.
-.\"O If the item is found in the tree, then
-.\"O .BR tsearch ()
-.\"O returns a pointer
-.\"O to it.
-.\"O If it is not found, then
-.\"O .BR tsearch ()
-.\"O adds it, and returns a
-.\"O pointer to the newly added item.
-.BR tsearch ()
-は、木構造からアイテムを検索する関数である。
-\fIkey\fP は、検索するアイテムへのポインタである。
-\fIrootp\fP は木構造の根へのポインタへのポインタである。
-木構造がノードを含まない場合、\fIrootp\fP の参照している変数は
-NULL に設定されていなければならない。
-木構造にアイテムが見つかった場合、
-.BR tsearch ()
-はそのアイテムへのポインタを返す。
-見つからなかった場合は、アイテムを木構造に追加し、
-追加したアイテムへのポインタを返す。
+\fBtsearch\fP() は、木構造からアイテムを検索する関数である。 \fIkey\fP は、検索するアイテムへのポインタである。 \fIrootp\fP
+は木構造の根へのポインタへのポインタである。 木構造がノードを含まない場合、\fIrootp\fP の参照している変数は NULL
+に設定されていなければならない。 木構造にアイテムが見つかった場合、 \fBtsearch\fP() はそのアイテムへのポインタを返す。
+見つからなかった場合は、アイテムを木構造に追加し、 追加したアイテムへのポインタを返す。
.PP
-.\"O .BR tfind ()
-.\"O is like
-.\"O .BR tsearch (),
-.\"O except that if the item is not
-.\"O found, then
-.\"O .BR tfind ()
-.\"O returns NULL.
-.BR tfind ()
-は、
-.BR tsearch ()
-に似ているが、
-アイテムが見つからなかった場合 NULL を返す点が異なる。
+\fBtfind\fP() は、 \fBtsearch\fP() に似ているが、 アイテムが見つからなかった場合 NULL を返す点が異なる。
.PP
-.\"O .BR tdelete ()
-.\"O deletes an item from the tree.
-.\"O Its arguments are the same as for
-.\"O .BR tsearch ().
-.BR tdelete ()
-は木構造からアイテムを削除する。
-引数は
-.BR tsearch ()
-と同じである。
+\fBtdelete\fP() は木構造からアイテムを削除する。 引数は \fBtsearch\fP() と同じである。
.PP
-.\"O .BR twalk ()
-.\"O performs depth-first, left-to-right traversal of a binary
-.\"O tree.
-.\"O \fIroot\fP points to the starting node for the traversal.
-.\"O If that node is not the root, then only part of the tree will be visited.
-.\"O .BR twalk ()
-.\"O calls the user function \fIaction\fP each time a node is
-.\"O visited (that is, three times for an internal node, and once for a
-.\"O leaf).
-.\"O \fIaction\fP, in turn, takes three arguments.
-.\"O The first is a pointer to the node being visited.
-.\"O The second is an integer which
-.\"O takes on the values \fBpreorder\fP, \fBpostorder\fP, and
-.\"O \fBendorder\fP depending on whether this is the first, second, or
-.\"O third visit to the internal node, or \fBleaf\fP if it is the single
-.\"O visit to a leaf node.
-.\"O (These symbols are defined in \fI<search.h>\fP.)
-.\"O The third argument is the depth of the node, with
-.\"O zero being the root.
-.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
-.\"O (More commonly, \fBpreorder\fP, \fBpostorder\fP, and \fBendorder\fP
-.\"O are known as \fBpreorder\fP, \fBinorder\fP, and \fBpostorder\fP:
-.\"O before visiting the children, after the first and before the second,
-.\"O and after visiting the children.
-.\"O Thus, the choice of name \fBpost\%order\fP
-.\"O is rather confusing.)
-(より一般的には、\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
-.\"O .BR tdestroy ()
-.\"O removes the whole tree pointed to by \fIroot\fP,
-.\"O freeing all resources allocated by the
-.\"O .BR tsearch ()
-.\"O function.
-.\"O For the data in each tree node the function \fIfree_node\fP is called.
-.\"O The pointer to the data is passed as the argument to the function.
-.\"O If no such work is necessary \fIfree_node\fP must point to a function
-.\"O doing nothing.
-.BR tdestroy ()
-は \fIroot\fP が指す木構造全体を削除し、
-.BR tsearch ()
-関数で確保されたリソースを全て解放する。
-木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。
-データへのポインタがこの関数の引数として渡される。
-そのような動作が必要でなければ、
-\fIfree_node\fP は何もしない関数へのポインタでなければならない。
-.\"O .SH "RETURN VALUE"
+\fBtdestroy\fP() は \fIroot\fP が指す木構造全体を削除し、 \fBtsearch\fP() 関数で確保されたリソースを全て解放する。
+木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。 データへのポインタがこの関数の引数として渡される。
+そのような動作が必要でなければ、 \fIfree_node\fP は何もしない関数へのポインタでなければならない。
.SH 返り値
-.\"O .BR tsearch ()
-.\"O returns a pointer to a matching item in the tree, or to
-.\"O the newly added item, or NULL if there was insufficient memory
-.\"O to add the item.
-.\"O .BR tfind ()
-.\"O returns a pointer to the item, or
-.\"O NULL if no match is found.
-.\"O If there are multiple elements that match the key,
-.\"O the element returned is unspecified.
-.BR tsearch ()
-は、木構造に見つかったアイテムか、
-新しく追加したアイテムへのポインタを返す。
-メモリの不足のためアイテムを追加できなかった場合は NULL を返す。
-.BR tfind ()
-は、アイテムへのポインタを返す。
-一致するアイテムが見つからない場合は NULL を返す。
-検索条件に一致する要素が複数ある場合、返される値は不定である。
+\fBtsearch\fP() は、木構造に見つかったアイテムか、 新しく追加したアイテムへのポインタを返す。
+メモリの不足のためアイテムを追加できなかった場合は NULL を返す。 \fBtfind\fP() は、アイテムへのポインタを返す。
+一致するアイテムが見つからない場合は NULL を返す。 検索条件に一致する要素が複数ある場合、返される値は不定である。
.PP
-.\"O .BR tdelete ()
-.\"O returns a pointer to the parent of the item deleted, or
-.\"O NULL if the item was not found.
-.BR tdelete ()
-は削除したアイテムの親へのポインタを返す。
-アイテムが見つからなかった場合は NULL を返す。
+\fBtdelete\fP() は削除したアイテムの親へのポインタを返す。 アイテムが見つからなかった場合は NULL を返す。
.PP
-.\"O .BR tsearch (),
-.\"O .BR tfind (),
-.\"O and
-.\"O .BR tdelete ()
-.\"O also
-.\"O return NULL if \fIrootp\fP was NULL on entry.
-\fIrootp\fP が NULL の場合、
-.BR tsearch (),
-.BR tfind (),
-.BR tdelete ()
-は NULL を返す。
-.\"O .SH "CONFORMING TO"
+\fIrootp\fP が NULL の場合、 \fBtsearch\fP(), \fBtfind\fP(), \fBtdelete\fP() は NULL を返す。
.SH 準拠
-SVr4, POSIX.1-2001.
-.\"O The function
-.\"O .BR tdestroy ()
-.\"O is a GNU extension.
-関数
-.BR tdestroy ()
-は GNU の拡張である。
-.\"O .SH NOTES
+SVr4, POSIX.1\-2001. 関数 \fBtdestroy\fP() は GNU の拡張である。
.SH 注意
-.\"O .BR twalk ()
-.\"O takes a pointer to the root, while the other functions
-.\"O take a pointer to a variable which points to the root.
-.BR twalk ()
-は根へのポインタを引数にとるが、
-ほかの関数は根へのポインタへのポインタである。
+\fBtwalk\fP() は根へのポインタを引数にとるが、 ほかの関数は根へのポインタへのポインタである。
.PP
-.\"O .BR twalk ()
-.\"O uses \fBpostorder\fP to mean "after the left subtree, but
-.\"O before the right subtree".
-.\"O Some authorities would call this
-.\"O "inorder", and reserve "postorder" to mean "after both subtrees".
-.BR twalk ()
-においては、\fBpostorder\fP は
-「左の部分木の後で、右の部分木の前」を意味している。
-しかし、人によってはこれを "inorder" と呼んで、
-"postorder" を「両方の部分木の後」とする場合もある。
+\fBtwalk\fP() においては、\fBpostorder\fP は 「左の部分木の後で、右の部分木の前」を意味している。 しかし、人によってはこれを
+"inorder" と呼んで、 "postorder" を「両方の部分木の後」とする場合もある。
.PP
-.\"O .BR tdelete ()
-.\"O frees the memory required for the node in the tree.
-.\"O The user is responsible for freeing the memory for the corresponding
-.\"O data.
-.BR tdelete ()
-は、削除したノードの使用していたメモリを解放するが、
-ノードに対応するデータのメモリは、ユーザが解放しなければならない。
+\fBtdelete\fP() は、削除したノードの使用していたメモリを解放するが、 ノードに対応するデータのメモリは、ユーザが解放しなければならない。
.PP
-.\"O The example program depends on the fact that
-.\"O .BR twalk ()
-.\"O makes no
-.\"O further reference to a node after calling the user function with
-.\"O argument "endorder" or "leaf".
-.\"O This works with the GNU library
-.\"O implementation, but is not in the System V documentation.
-下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引数にして
-呼び出されて以降は、
-.BR twalk ()
-がそのノードを参照しないことを前提としている。
-これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
-.\"O .SH EXAMPLE
+下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引数にして 呼び出されて以降は、 \fBtwalk\fP()
+がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
.SH 例
-.\"O The following program inserts twelve random numbers into a binary
-.\"O tree, where duplicate numbers are collapsed, then prints the numbers
-.\"O in order.
-以下のプログラムは 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;
}
}
exit(EXIT_SUCCESS);
}
.fi
-.\"O .SH "SEE ALSO"
.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
