Programowanie w języku C/C++

Bsearch

  • 2010-10-31 18:27
  • 0 komentarzy
  • 1302 odsłony
  • Oceń ten tekst jako pierwszy
void *bsearch (const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

<justify>Funkcja bsearch() przeszukuje tablicę obiektów nmemb, której pierwszy element jest wskazywany przez wskaźnik base, w poszukiwaniu elementu pasującego do obiektu wskazywanego przez key. Rozmiar każdego z elementów tablicy określony jest przez size.</justify><justify>     Zawartość tablicy powinna być posortowana w kolejności rosnącej zgodnie z funkcją porównawczą wskazywaną przez compar. Funkcja compar powinna posiadać dwa argumenty: wskaźnik do obiektu key oraz do elementu tablicy, i powinna zwracać wartość integer mniejszą, równą lub większą niż zero jeśli obiekt key okazał się, odpowiednio, mniejszy, równy lub większy niż element tablicy.</justify>
Parametry:
key
Szukany element.
base
Pierwszy element tablicy.
nmemb
Liczba elementów przeszukiwanej tablicy.
size
Rozmiar pojedynczego elementu w bajtach.
compar
Wskaźnik do funkcji porównującej elementy.
Zwracana wartość:
bsearch() zwraca wskaźnik do znalezionego elementu lub NULL gdy elementu nie znaleziono. Jeżeli tablica zawiera wiele elementów zgodnych ze wzorcem, nie jest określone który zostanie znaleziony.

Przykłady


#include <stdio.h>
#include <stdlib.h>
 
int compareIntegers (const void* a, const void* b)
{
        return (*(int*)a - *(int*)b);
}
 
int main (int argc, char* argv[])
{
        int* element;
        int szukana_wartosc = 25;
        int ciag[] = { 10, 20, 25, 40, 90, 100, 200, 400, 768, 769, 780, 781, 1000 };
 
        element = (int*) bsearch(&szukana_wartosc, ciag, 14, sizeof (int), compareIntegers);
        if ( element )
                printf ("%d znajduje sie w ciagu na pozycji %d.\n", *element, element-ciag+1);
        else
                printf ("%d nie znajduje sie w ciagu.\n", szukana_wartosc);
        return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main (int argc, char* argv[])
{
        char* element;
        char szukana_wartosc[20] = "sensu";
        char ciag[][20] = {"przykladowy","pozbawiony", "wiekszego", "sensu", "string"};
 
        qsort (ciag, 5, 20, (int(*)(const void*,const void*)) strcmp);        /* ← sortowanie elementów ciągu */
 
        element = (char*) bsearch_ (szukana_wartosc, ciag, 5, 20, (int(*)(const void*,const void*)) strcmp);
 
        if ( element )
                printf ("element '%s' znajduje sie w ciagu.\n", element);
        else
                printf ("element '%s' nie zostal znaleziony w ciagu.\n", szukana_wartosc);
        return 0;
}

Prosta implementacja


 /* ↓ what oznacza szukany element, low i high odpowiednio pierwszy i ostatni element przeszukiwanej tablicy */
int * binarySearch (int what, int *low, int *high)
{
        int *middle;        /* ← środkowy element tablicy */
        while ( high > low )
        {
                middle = low + (high - low) / 2;
                if ( *middle == what )
                        return middle;
                else if ( *middle > what )
                        high = middle;
                else
                        low = middle + 1;
        }
        return NULL;
}


Zobacz też: