tsearch, tdelete, tfind oder twalk Subroutine
Zweck
Verwaltet binäre Suchbaumstrukturen.
Bibliothek
Standard-C-Bibliothek (libc.a)
Syntax
#include <search.h>const void *Key;
void **RootPointer;
int (*ComparisonPointer) (const void *Element1, const void *Element2);
void *tdelete (Key, RootPointer, ComparisonPointer)
const void *Key;
void **RootPointer;
int (*ComparisonPointer) (const void *Element1, const void *Element2);void *tfind (Key, RootPointer, ComparisonPointer)
const void *Key;
void *const *RootPointer;
int (*ComparisonPointer) (const void *Element1, const void *Element2);Beschreibung
Die Unterroutinen TSearch, Löschen, Tfind und Twalk bearbeiten binäre Suchbaumstrukturen. Vergleiche werden mit der benutzerdefinierten Routine durchgeführt, die durch den Parameter ComparisonPointer angegeben wird. Diese Routine wird mit zwei Parametern aufgerufen, den Zeigern auf die Elemente, die verglichen werden.
Die Subroutine TSearch führt eine binäre Baumstruktursuche durch und gibt einen Zeiger in eine Baumstruktur zurück, die angibt, wo sich die durch den Parameter Schlüssel angegebenen Daten befinden. Wenn die durch den Parameter Schlüssel angegebenen Daten nicht gefunden werden, werden die Daten an der richtigen Stelle zur Baumstruktur hinzugefügt. Wenn nicht genügend Speicherplatz zum Erstellen eines neuen Knotens verfügbar ist, wird ein Nullzeiger zurückgegeben. Es werden nur Zeiger kopiert, sodass die aufrufende Routine die Daten speichern muss. Der Parameter RootPointer verweist auf eine Variable, die auf das Stammelement der Baumstruktur verweist. Wenn der Parameter RootPointer der Nullwert ist, wird die Variable so gesetzt, dass sie auf das Stammelement einer neuen Baumstruktur verweist. Wenn der Parameter RootPointer der Nullwert im Eintrag ist, wird ein Nullzeiger zurückgegeben.
Die Subroutine Löschen löscht die durch den Parameter Schlüssel angegebenen Daten. Die Parameter RootPointer und ComparisonPointer führen dieselbe Funktion wie für die Subroutine tsearch aus. Die Variable, auf die der Parameter RootPointer verweist, wird geändert, wenn der gelöschte Knoten das Stammelement der binären Baumstruktur ist. Die Subroutine Löschen gibt einen Zeiger auf den übergeordneten Knoten des gelöschten Knotens zurück. Wenn die Daten nicht gefunden werden, wird ein Nullzeiger zurückgegeben. Wenn der Parameter RootPointer beim Eintrag null ist, wird ein Nullzeiger zurückgegeben.
Die Subroutine Tfind durchsucht die binäre Suchbaumstruktur. Wie die Subroutine TSearch sucht auch die Subroutine Tfind nach einem Knoten in der Baumstruktur und gibt einen Zeiger darauf zurück, wenn er gefunden wird. Wenn sie jedoch nicht gefunden wird, gibt die Subroutine Tfind einen Nullzeiger zurück. Die Parameter für die Subroutine Tfind sind dieselben wie für die Subroutine TSearch .
Die Subroutine twalk durchläuft die binäre Suchbaumstruktur, auf deren Stammverzeichnis durch den Parameter RootPointer verwiesen wird. (Jeder Knoten in einer Baumstruktur kann als Stammelement verwendet werden, um die Baumstruktur unter diesem Knoten schrittweise durchzugehen.) Der Parameter Aktion ist der Name einer Routine, die auf jedem Knoten aufgerufen werden soll. Die im Parameter Aktion angegebene Routine wird mit drei Parametern aufgerufen. Der erste Parameter ist die Adresse des Knotens, auf den gerade verwiesen wird. Der zweite Parameter ist ein Wert aus einem Aufzählungsdatentyp:
typedef enum [preorder, postorder, endorder, leaf] VISIT;(Dieser Datentyp ist in der Datei search.h definiert). Der tatsächliche Wert des zweiten Parameters hängt davon ab, ob es sich um den ersten, zweiten oder dritten Zeitpunkt handelt, an dem der Knoten während einer ersten, von links nach rechts verlaufenden Traversierung der Baumstruktur aufgerufen wurde, oder ob der Knoten ein Blattist. Ein Blatt ist ein Knoten, der nicht das übergeordnete Element eines anderen Knotens ist. Der dritte Parameter ist die Ebene des Knotens in der Baumstruktur, wobei der Stammknoten die Ebene null ist.
Obwohl als Typ pointer-to-void deklariert, sollten die Zeiger auf den Schlüssel und den Stamm der Baumstruktur vom Typ pointer-to-element sein und in den Typ pointer-to-character umgesetzt werden. Obwohl als Typ pointer-to-character deklariert, sollte der zurückgegebene Wert in Typ pointer-to-element umgesetzt werden.
Parameter
| Element | Beschreibung |
|---|---|
| key | Verweist auf die zu lokierenden Daten. |
| ComparisonPointer | Verweist auf die Vergleichsfunktion, die mit zwei Parametern aufgerufen wird, die auf die Elemente verweisen, die verglichen werden. |
| RootPointer | Zeigt auf eine Variable, die wiederum auf den Stamm der Baumstruktur verweist. |
| Aktion | Benennt eine Routine, die auf jedem Knoten aufgerufen werden soll. |
| Root | Verweist auf die Stammverzeichnisse eines binären Suchknotens. |
Rückgabewerte
Die Vergleichsfunktion vergleicht ihre Parameter und gibt einen Wert wie folgt zurück:
- Wenn der erste Parameter kleiner als der zweite Parameter ist, gibt der Parameter ComparisonPointer einen Wert kleiner als 0 zurück.
- Wenn der erste Parameter dem zweiten Parameter entspricht, gibt der Parameter ComparisonPointer den Wert 0 zurück.
- Wenn der erste Parameter größer als der zweite Parameter ist, gibt der Parameter ComparisonPointer einen Wert größer als 0 zurück.
Die Vergleichsfunktion muss nicht jedes Byte vergleichen, so dass neben den Werten, die verglichen werden, beliebige Daten in den Elementen enthalten sein können.
Wenn der Knoten gefunden wird, geben die Subroutinen TSearch und Tfind einen Zeiger darauf zurück. Wenn der Knoten nicht gefunden wird, gibt die Subroutine TSearch einen Zeiger auf das eingefügte Element und die Subroutine Tfind einen Nullzeiger zurück. Wenn nicht genügend Speicherplatz vorhanden ist, um einen neuen Knoten zu erstellen, gibt die Subroutine TSearch einen Nullzeiger zurück.
Wenn der Parameter RootPointer ein Nullzeiger auf einen Eintrag ist, wird ein Nullzeiger von den Subroutinen tsearch und tdelete zurückgegeben.
Die Subroutine Löschen gibt einen Zeiger auf das übergeordnete Element des gelöschten Knotens zurück. Wird der Knoten nicht gefunden, wird ein Nullzeiger zurückgegeben.