1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
.\" Hey Emacs! This file is -*- nroff -*- source.
.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
.\"
.\" 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.
.\"
.TH TSEARCH 3 "24 de setembro de 1995" "GNU" "Manual do Programador Linux"
.SH NOME
tsearch, tfind, tdelete, twalk \- gerencia uma rvore binria
.SH SINOPSE
.nf
.B #include <search.h>
.sp
.BI "void *tsearch (const void *" key ", void **" rootp ,
.BI " int (*" compar ")(const void *, const void *));"
.sp
.BI "void *tfind (const void *" key ", const void **" rootp ,
.BI " int (*" compar ")(const void *, const void *));"
.sp
.BI "void *tdelete (const void *" key ", void **" rootp ,
.BI " int (*" compar ")(const void *, const void *));"
.sp
.BI "void twalk (const void *" root ", void (*" action ") (const void *" nodep ,
.BI " const VISIT " which ,
.BI " const int " depth "));"
.RE
.fi
.SH DESCRIO
\fBtsearch\fP, \fBtfind\fP, \fBtwalk\fP, e \fBtdelete\fP gerenciam uma rvore binria.
Eles so gerados a partir do Algoritmo T de Knuth (6.2.2). O primeiro campo
em cada n da rvore um ponteiro para o item correspondente de dados. ( O programa
solicitante precisa armazenar os dados atuais). \fIcompar\fP aponta para uma rotina de
comparao, que pega ponteiros para dois itens. Ele deve retornar um inteiro que
negaivo, ou zero, ou positivo, dependendo se o primeiro item menor, igual ou maior
que o segundo.
.PP
\fBtsearch\fP busca um item na rvore. \fIkey\fP aponta para o item a ser buscado.
\fIrootp\fP aponta para uma varivel que aponta para a raiz da rvore. Se a rvore
est vazia, ento a varivel apontada por \fIrootp\fP deve ser setada para \fBNULL\fP.
Se o item encontrado na rvore, ento \fBtsearch\fP retorna um ponteiro para ele.
Se no encontrado, ento \fBtsearch\fP o acrescenta, e retorna um ponteiro para
o novo item acrescentado.
.PP
\fBtfind\fP como \fBtsearch\fP, exceto pelo fato de que, se o item no encontrado,
ento \fBtfind\fP retorna \fBNULL\fP.
.PP
\fBtdelete\fP apaga um item da rvore. Seus argumentos so os mesmos de \fBtsearch\fP.
.PP
\fBtwalk\fP realiza uma travessia de uma rvore binria por profundidade, da esquerda para
a direita. \fIroot\fP aponta para o n inicial da travessia. Se aquele n no a raiz, ento
apenas parte da rvore ser visitada.
\fBtwalk\fP chama a funo de usurio \fIaction\fP cada vez que um n visitado (ou seja,
trs vezes para um n interno, e uma vez para uma folha).
\fIaction\fP, por sua vez, leva trs argumentos. O primeiro um ponteiro para o n que est
sendo visitado. O segundo um inteiro que recebe os valores \fBpreorder\fP, \fBpostorder\fP
e \fBendorder\fP, dependendo se este a primeira, a segundo ou a terceira visita ao n interno,
ou \fBleaf\fP se uma visita nica a um n-folha. (Estes smbolos so definidos em
\fI<search.h>\fP.) O terceiro argumento a profundidade do n, com zero sendo a raiz.
.SH "VALOR DE RETORNO"
\fBtsearch\fP retorna um ponteiro para um item encontrado na rvore, ou para o novo item
acrescentado, ou \fBNULL\fP se havia memria insuficiente para acrescentar o item.
\fBtfind\fP retorna um ponteiro para o item, ou \fBNULL\fP se nada foi encontrado. Se haviam
mltiplos elementos que casaram com a chave, o elemento retornado no especificado.
.PP
\fBtdelete\fP retorna um ponteiro para o pai do item apagado, ou
\fBNULL\fP se o item no foi encontrado.
.PP
\fBtsearch\fP, \fBtfind\fP, e \fBtdelete\fP tambm
retornam \fBNULL\fP se \fIrootp\fP era \fBNULL\fP na entrada.
.SH ALERTAS
\fBtwalk\fP pega um ponteiro para a raiz, enquanto as outras funes
pegam um ponteiro para uma varivel que aponta para a raiz.
.PP
\fBtwalk\fP usa \fBps-ordem\fP para dizer "depois da sub-rvore da esquerda, mas
antes da sub-rvore da direita". Algumas autoridades chamariam isto de
"em-ordem", e reservariam "ps-ordem" para dizer "depois de ambas as sub-rvores".
.PP
\fBtdelete\fP libera a memria requerida para o n na rvore. O usurio
responsvel para liberar a memria dos dados correspondentes.
.PP
O programa exemplo depende do fato de que \fBtwalk\fP no faz referncia
adicional a um n depois de chamar a funo de usurio com o argumento
"endorder" ou "leaf". Isto funciona com a implementao da biblioteca GNU, mas
no est na documentao SysV.
.SH EXEMPLO
O programa a seguir insere doze nmeros aleatrios em uma rvore binria, e ento
imprime os nmeros em ordem. Os nmeros so removidos da rvore e seus armazenamentos
so liberados durante a travessia.
.sp
.nf
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
void *root=NULL;
void *xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if(p) return p;
fprintf(stderr, "memria insuficiente\\n");
exit(1);
}
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;
void *val;
switch(which)
{
case preorder:
break;
case postorder:
datap = *(int **)nodep;
printf("%6d\\n", *datap);
break;
case endorder:
datap = *(int **)nodep;
(void)tdelete(datap, &root, compare);
free(datap);
break;
case leaf:
datap = *(int **)nodep;
printf("%6d\\n", *datap);
val = tdelete(datap, &root, compare);
free(datap);
break;
}
return;
}
int main()
{
int i, *ptr;
void *val;
for (i = 0; i < 12; i++)
{
ptr = (int *)xmalloc(sizeof(int));
*ptr = rand()&0xff;
val = tsearch((void *)ptr, &root, compare);
if(val == NULL) exit(1);
}
twalk(root, action);
return 0;
}
.fi
.SH "CONFORME"
SVID
.SH "VEJA TAMBM"
.BR qsort "(3), " bsearch "(3), " hsearch "(3), " lsearch "(3)"
.SH TRADUZIDO POR LDP-BR EM 03/08/2000
\&\fR\&\f(CWRUBENS DE JESUS NOGUEIRA <darkseid99@usa.net> (traduo)\fR
\&\fR\&\f(CWXXXXXX XX XXXXX XXXXXXXX <xxxxxxxxxx@xxx.xxx> (reviso)\fR
|
