bsearch(3C)                                                     bsearch(3C)

NAME
     bsearch - Sortierte Tabelle binär absuchen

SYNTAX
     #include <stdlib.h>

     void *bsearch(const void *key, const void *base, sizet nel,
           sizet size, int (*compar)(const void *, const void *));

BESCHREIBUNG
     bsearch() ist eine binäre Suchfunktion, eine verallgemeinerte Version
     des Algorithmus (6.2.1) B von Knuth. Sie gibt einen Zeiger zurück, der
     auf die Stelle in der Tabelle (im Feld) zeigt, an der ein gegebener
     Wert gefunden werden kann. Sie gibt einen Nullzeiger zurück, falls der
     Wert nicht gefunden werden kann. key weist auf einen Bezugswert, der
     in der Tabelle zu suchen ist. base weist auf das Element am Anfang der
     Tabelle. nel ist die Anzahl der Elemente in der Tabelle. Die Funktion,
     auf die compar zeigt, wird mit zwei Argumenten aufgerufen, die auf key
     und auf ein Element der Tabelle (in dieser Reihenfolge) zeigen. Die
     Funktion muß eine ganze Zahl liefern, die kleiner, gleich oder größer
     als Null ist, je nachdem, ob das erste Argument kleiner, gleich oder
     größer als das zweite Argument ist. Die Tabelle muß folgende Elemente
     enthalten: erst alle Elemente, die kleiner als key sind, dann alle
     Elemente, die gleich und schließlich alle Elemente, die größer als key
     sind.

BEISPIELE
     In diesem Beispiel wird eine Tabelle durchsucht, die Zeiger auf Knoten
     enthält, die aus einer Zeichenkette und ihrer Länge bestehen. Die
     Tabelle ist alphabetisch nach der Zeichenkette im Knoten geordnet, auf
     die jeder Eintrag zeigt.

     Dieses Programm liest Zeichenketten ein und findet entweder den ent-
     sprechenden Knoten und gibt die Zeichenkette und die Länge aus, oder
     es gibt eine Fehlermeldung aus.

     #include <stdio.h>
     #include <stdlib.h>
     #include <string.h>

     struct node {                 /* Diese werden in der Tabelle */
           char *string;           /* gespeichert */
           int length;
     };
     static struct node table[] =  /* zu durchsuchende Tabelle */
     {
          { "asparagus", 10 },
          { "beans", 6 },
          { "tomato", 7 },
          { "watermelon", 11 },
     };




Seite 1                      Reliant UNIX 5.44               Gedruckt 11/98

bsearch(3C)                                                     bsearch(3C)

     main()
     {
           struct node *nodeptr, node;
           /* Routine um zwei Konten zu vergleichen */
           static int nodecompare(const void *, const void *);
           char strspace[20]; /* Speicherplatz zum Einlesen der
                                  Zeichenkette */
           node.string = strspace;
           while (scanf("%20s", node.string) != EOF) {
                   nodeptr = bsearch( &node,
                              table, sizeof(table)/sizeof(struct node),
                              sizeof(struct node), nodecompare);
                   if (nodeptr != NULL) {
                           (void) printf("string = %20s, length = %d\n"
                                   nodeptr->string, nodeptr->length);
                   } else {
                           (void)printf("not found: %20s\n", node.string)
                   }
           }
           return(0);
     }

     /* Diese Routine vergleicht zwei Knoten auf Grundlage einer */
     /* alphabetischen Ordnung des Zeichenkettenfelds */
     static int
     node_compare(const void *node1, const void *node2)
     {
           return (strcoll(
                           ((const struct node *)node1)->string,
                           ((const struct node *)node2)->string));
     }

ERGEBNIS
     Ein Nullzeiger wird zurückgegeben, wenn das gesuchte Element nicht in
     der Tabelle gefunden werden kann, sonst wird ein Zeiger, der auf die
     Stelle in der Tabelle zeigt, zurückgegeben.

HINWEISE
     Die Zeiger auf key und das Element am Anfang der Tabelle sollten vom
     Typ "Zeiger-auf-Element" sein.

     Die Vergleichsfunktion muß nicht jedes Byte vergleichen, deshalb kön-
     nen die Elemente zusätzlich zu den Vergleichswerten willkürliche Daten
     enthalten.

     Wenn die Anzahl von Elementen in der Tabelle kleiner als die für die
     Tabelle reservierte Größe ist, sollte nel die kleinere Zahl sein.

SIEHE AUCH
     hsearch(3C), lsearch(3C), qsort(3C), tsearch(3C).




Seite 2                      Reliant UNIX 5.44               Gedruckt 11/98