Advertisement
Mary_99

bsearch struck

Jun 4th, 2019
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.84 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #define ARRAY_SIZE 20
  5. #define ELEMENTS 7
  6.  
  7. struct data
  8. {
  9.     int integers[10];
  10.     double doubleValues[8];
  11.     char names[5][ARRAY_SIZE];
  12. };
  13.  
  14. int compereInt(const void *integer1, const void *integer2);
  15. int compereDouble(const void *doubleValue1, const void *doubleValue2) ;
  16. int compereNames(const void *name1, const void *name2);
  17. void* bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
  18.  
  19.  
  20. int main()
  21. {
  22.     struct data data = {
  23.         .integers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
  24.         .doubleValues = {1.67, 2.32, 4.23, 6.14, 11.57, 13.11, 21.37, 23.23},
  25.         .names = {"arek", "bartek", "krzys", "ola", "ania"}
  26.     };
  27.    
  28.     int *foundInteger = NULL;
  29.     double *foundDouble = NULL;
  30.     char *foundName = NULL;
  31.     int currentElement;
  32.     int findInteger[ELEMENTS] = {1, 4, 7, 8, 11, 18, 20};
  33.     double findDouble[ELEMENTS] = {2.22,21.37, 6.78, 4.23, 13.12, 23.23, 24.44};
  34.     char findName[ELEMENTS][ARRAY_SIZE] = {"arek", "krystian", "sebastian", "ola", "maciek","bartek", "antek"};
  35.    
  36.     for(currentElement = 0; currentElement < ELEMENTS; currentElement++)
  37.     {
  38.           foundInteger = (int*)bsearch( &findInteger[currentElement], data.integers, sizeof(data.integers)/sizeof(int), sizeof(int), compereInt);
  39.           foundDouble = (double*)bsearch(&findDouble[currentElement], data.doubleValues, sizeof(data.doubleValues)/sizeof(double), sizeof(double), compereDouble);
  40.           foundName = (char*)bsearch(&findName[currentElement], data.names, sizeof(data.names)/sizeof(*data.names), sizeof(*data.names), compereNames);
  41.          
  42.           if(foundInteger != NULL)
  43.             printf("Found integer %d\n", findInteger[currentElement]);
  44.           else
  45.             printf("Integer %d not found\n", findInteger[currentElement]);
  46.          
  47.           if(foundDouble != NULL)
  48.             printf("Found double %f\n", findDouble[currentElement]);
  49.           else
  50.             printf("Double %f not found\n", findDouble[currentElement]);
  51.          
  52.           if (foundName!= NULL)
  53.             printf("Found name %s\n\n", findName[currentElement]);
  54.           else
  55.             printf("Name %s not found\n\n", findName[currentElement]);
  56.     }
  57.    
  58.     return 0;
  59. }
  60.  
  61.  
  62. int compereInt(const void *integer1, const void *integer2)
  63. {
  64.     if (*(int*)integer1 == *(int*)integer2)
  65.     {
  66.         return 0;
  67.     }
  68.     else if (*(int*)integer1 > *(int*)integer2)
  69.     {
  70.         return 1;
  71.     }
  72.     else
  73.     {
  74.         return -1;
  75.     }
  76. }
  77.  
  78. int compereDouble(const void *doubleValue1, const void *doubleValue2)
  79. {
  80.     if (*(double*)doubleValue1 == *(double*)doubleValue2)
  81.     {
  82.         return 0;
  83.     }
  84.     else if (*(double*)doubleValue1 > *(double*)doubleValue2)
  85.     {
  86.         return 1;
  87.     }
  88.     else
  89.     {
  90.         return -1;
  91.     }
  92. }
  93.  
  94. int compereNames(const void *name1, const void *name2)
  95. {
  96.     return strcmp(name1, name2);
  97. }
  98.  
  99. void* bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))
  100. {
  101.    
  102.    /*
  103.     const void *key Poszukiwany klucz.
  104.     const void *base    Wskaźnik na posortowaną tablicę, która ma zostać przeszukana.
  105.     size_t nmemb    Liczba elementów w tablicy.
  106.     size_t size Liczba bajtów zajmowanych przez jeden element tablicy.
  107.     int (*compare ) ( const void *, const void *)   Funkcja porównująca klucze. Do pierwszego argumentu przedmiotowej funkcji trafia wskaźnik na element poszukiwany key, natomiast do drugiego wskaźnik na element tablicy base z którym ma nastąpić porównanie.*/
  108.    
  109.     const void* currentElement = 0;
  110.     int start = 0;
  111.     int end = nmemb;
  112.     int middle;
  113.     int searchElement;
  114.  
  115.     while (start <= end)
  116.     {
  117.         middle = start + (end - start) / 2;
  118.         currentElement = (char*)base + middle* size;
  119.         searchElement = (*compar)(key, currentElement);
  120.  
  121.         if (searchElement == 0)
  122.         {
  123.             return ((void*)currentElement);
  124.         }
  125.         else if (searchElement < 0)
  126.         {
  127.             end = middle - 1;
  128.         }
  129.         else
  130.         {
  131.             start = middle + 1;
  132.         }
  133.     }
  134.  
  135.     return NULL;
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement