tsearch(3C) tsearch(3C)
NAME
tsearch, tfind, tdelete, twalk - Binäre Suchbäume verwalten
SYNTAX
#include <search.h>
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void *tfind(const void *key, void *const *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 *, VISIT, int));
BESCHREIBUNG
tsearch(), tfind(), tdelete() und twalk() sind Funktionen für die Ver-
waltung von binären Suchbäumen. Sie sind Verallgemeinerungen der Algo-
rithmen T und D von Knuth (6.2.2). Alle Vergleiche werden durch eine
vom Benutzer gelieferte Funktion ausgeführt. Diese Funktion wird mit
zwei Argumenten aufgerufen, d. h. mit den Zeigern auf die Elemente,
die verglichen werden. Sie gibt eine ganze Zahl zurück, die kleiner,
gleich oder größer als 0 ist, je nachdem, ob das erste Argument klei-
ner, gleich oder größer als das zweite Argument ist. Die Vergleichs-
funktion braucht nicht jedes Byte zu vergleichen, und daher können
außer den Werten, die verglichen werden, auch willkürliche Daten in
den Elementen enthalten sein.
tsearch() wird zum Aufbau des Baums und für den Zugriff auf den Baum
verwendet. key ist ein Zeiger auf einen Wert, auf den zugegriffen
beziehungsweise der gespeichert werden soll. Wenn der Baum einen Wert
aufweist, der gleich *key (der Wert, auf den der Schlüssel zeigt) ist,
wird ein Zeiger auf diesen gefundenen Wert zurückgegeben. Andernfalls
wird *key eingefügt und ein auf diesen key weisender Zeiger zurückge-
geben. Es werden nur Zeiger kopiert, und daher müssen die Daten von
der Aufrufroutine gespeichert werden. rootp zeigt auf eine Variable,
die auf die Wurzel des Baums zeigt. Ein NULL-Wert für die Variable,
auf die rootp zeigt, gibt einen leeren Baum an; in diesem Fall wird
die Variable so gesetzt, daß sie auf den Wert zeigt, der sich an der
Wurzel des neuen Baums befindet.
Wie tsearch() sucht auch tfind() nach einem Wert im Baum und gibt
einen Zeiger auf diesen Wert zurück, falls dieser gefunden wird. Wird
der Wert nicht gefunden, gibt tfind() einen Nullzeiger zurück. Die
Argumente für tfind() sind dieselben wie für tsearch().
Seite 1 Reliant UNIX 5.44 Gedruckt 11/98
tsearch(3C) tsearch(3C)
Mit tdelete() wird ein Knoten in einem binären Suchbaum gelöscht. Die
Argumente sind dieselben wie für tsearch(). Die Variable, auf die
rootp zeigt, ändert sich, wenn der gelöschte Knoten die Wurzel des
Baums war. tdelete() gibt einen Zeiger auf den Vaterknoten des
gelöschten Knotens zurück oder einen Nullzeiger, wenn der Knoten nicht
gefunden wurde.
twalk() durchläuft einen binären Suchbaum. root ist die Wurzel des
Baums, der durchlaufen werden soll. Jeder Knotenpunkt im Baum kann als
Wurzel für ein Durchlaufen des Baums unterhalb dieses Knotens verwen-
det werden. action ist der Name einer Funktion, die an jedem Knoten
aufgerufen werden soll. Diese Funktion wird mit drei Argumenten aufge-
rufen. Das erste Argument ist die Adresse des besuchten Knotens. Die
Struktur, auf die dieses Argument zeigt, ist nicht spezifiziert und
darf nicht verändert werden. Der Wert vom Typ "Zeiger-auf-Knoten" kann
jedoch in den Typ "Zeiger-auf-Zeiger-auf-Element" konvertiert werden,
um auf die in dem Knoten gespeicherten Elemente zugreifen zu können.
Das zweite Argument ist ein Wert des Aufzählungstyps
typedef enum { preorder, postorder, endorder, leaf } VISIT;
(definiert in der Include-Datei search.h), abhängig davon, ob es sich
um den ersten, zweiten oder dritten Besuch des Knotens handelt, bei
einem Durchlauf des Baums in die Tiefe, von links nach rechts, oder ob
der Knoten ein Blatt ist. Das dritte Argument stellt die Stufe des
Knotens im Baum dar, wobei die Wurzel die Stufe Null ist.
RÜCKGABEWERT
Wenn der Knoten gefunden wird, geben sowohl tsearch() als auch tfind()
einen Zeiger auf diesen zurück. Andernfalls gibt tfind() einen Null-
zeiger und tsearch() einen Zeiger auf das eingefügte Element zurück.
Von tsearch() wird ein Nullzeiger zurückgeliefert, wenn nicht genügend
Speicherplatz zum Erstellen eines neuen Knotens verfügbar ist.
Von tsearch(), tfind() und tdelete() wird ein Nullzeiger zurückgelie-
fert, wenn rootp zu Beginn ein Nullzeiger ist.
Die Funktion tdelete() gibt einen Zeiger auf den Vaterknoten des
gelöschten Knotens zurück oder einen Nullzeiger, wenn der Knoten nicht
gefunden wird.
Die Funktion twalk() gibt keinen Wert zurück.
FEHLER
Es sind keine Fehler definiert.
Seite 2 Reliant UNIX 5.44 Gedruckt 11/98
tsearch(3C) tsearch(3C)
BEISPIELE
Das folgende Programm liest Zeichenketten ein und speichert Strukturen
ab, die einen Zeiger auf eine Zeichenkette und ihre Länge enthalten.
Es durchläuft dann den Baum und gibt die gespeicherten Zeichenketten
und ihre Längen in alphabetischer Reihenfolge aus.
#include <search.h>
#include <string.h>
#include <stdio.h>
#define STRSZ 10000
#define NODSZ 500
struct node { /* pointers to these are stored in the tree */
char *string;
int length;
};
char stringspace[STRSZ]; /* space to store strings */
struct node nodes[NODSZ]; /* nodes to store */
void *root = NULL; /* this points to the root */
int main(int argc, char *argv[])
{
char *strptr = stringspace;
struct node *nodeptr = nodes;
void printnode(const void *, VISIT, int);
int i = 0, nodecompare(const void *, const void *);
while (gets(strptr) != NULL && i++ < NODSZ) {
/* set node */
nodeptr->string = strptr;
nodeptr->length = strlen(strptr);
/* put node into the tree */
(void) tsearch((void *)nodeptr, (void **)&root,
nodecompare);
/* adjust pointers, so we do not overwrite tree */
strptr += nodeptr->length + 1;
nodeptr++;
}
twalk(root, printnode);
return 0;
}
Seite 3 Reliant UNIX 5.44 Gedruckt 11/98
tsearch(3C) tsearch(3C)
/* This routine compares two nodes, based on an
alphabetical ordering of the string field. */
int
nodecompare(const void *node1, const void *node2)
{
return strcmp(((const struct node *) node1)->string,
((const struct node *) node2)->string);
}
/* This routine prints out a node, the second time
twalk encounters it or if it is a leaf. */
void
printnode(const void *ptr, VISIT order, int level)
{
const struct node *p = *(const struct node **) ptr;
if (order == postorder || order == leaf) {
(void) printf("string = %s, length = %d\n",
p->string, p->length);
}
}
ERGEBNIS
Ein Nullzeiger wird von tsearch() zurückgegeben, wenn nicht genügend
Speicher zur Erstellung eines neuen Knotens zur Verfügung steht.
Ein Nullzeiger wird von tfind() und tdelete() zurückgegeben, wenn
rootp zu Beginn NULL ist.
Wird der Wert gefunden, geben tsearch() und tfind() einen Zeiger auf
den Wert zurück. Wird der Wert nicht gefunden, gibt tfind() NULL
zurück, und tsearch() gibt einen Zeiger auf die eingefügte Position
zurück.
HINWEISE
Das Argument root für twalk() ist um eine Stufe der indirekten Adres-
sierung niedriger als die Argumente rootp für tsearch() und tdelete().
Es gibt zwei Nomenklaturen für die Reihenfolge, in der die Knoten
eines Baums durchlaufen werden. tsearch() verwendet die Begriffe
"preorder", "postorder" und "endorder", um auszudrücken, daß ein Kno-
ten vor seinen Söhnen oder nach dem linken und vor dem rechten Sohn
oder nach seinen Söhnen besucht wird. Die andere Nomenklatur verwendet
"preorder", "inorder" und "postorder", um diese Reihenfolgen zu
bezeichnen, wobei "postorder" eine andere Bedeutung hat.
Wenn die aufrufende Funktion den Zeiger auf die Wurzel ändert, werden
die Ergebnisse unvorhersagbar.
Seite 4 Reliant UNIX 5.44 Gedruckt 11/98
tsearch(3C) tsearch(3C)
SIEHE AUCH
bsearch(3C), hsearch(3C), lsearch(3C), search(5).
Seite 5 Reliant UNIX 5.44 Gedruckt 11/98