كيف يتم تنفيذ وظيفة BSearch () في مكتبة C القياسية؟

Question

هل يعرف أي شخص كيف يتم تنفيذ وظيفة البحث الثنائي القياسي؟

هذا هو النموذج الأولي.

void * bsearch (const void*, const void*, size_t, size_t, int (*) (const void *, const void *) );

أنا فضولي حقًا حول كيفية استخدام مؤشرات باطلة.

Answer 1

أفترض أنك مهتم بمعرفة كيف void * يتم استخدام المؤشرات في bsearch, ، بدلاً من خوارزمية البحث الثنائية الفعلية نفسها. النموذج الأولي ل bsearch هو:

void *bsearch(const void *key, const void *base,
    size_t nmemb, size_t size,
    int (*compar)(const void *, const void *));

هنا، void * يتم استخدامه بحيث يمكن البحث في أي نوع تعسفي. يتم تفسير المؤشرات من قبل (Sublied) compar وظيفة.

منذ المؤشر base تشير إلى بداية صفيف ، ويضمن أن تكون عناصر الصفيف متجاورة ، bsearch يمكن الحصول على void * مؤشر إلى أي من nmemb عناصر في المصفوفة عن طريق القيام بحساب المؤشر. على سبيل المثال ، للحصول على مؤشر إلى العنصر الخامس في الصفيف (على افتراض nmemb >= 5):

unsigned char *base_p = base;
size_t n = 5;
/* Go 5 elements after base */
unsigned char *curr = base_p + size*n;
/* curr now points to the 5th element of the array.
   Moreover, we can pass curr as the first or the second parameter
   to 'compar', because of implicit and legal conversion of curr to void *
   in the call */

في المقتطف أعلاه ، لم نتمكن من إضافة size*n مباشرة الى base لأنه من النوع void *, وحساب على void * غير محدد.

Answer 2

يرى BSearch @ Google Codesearch للتطبيقات المختلفة ل bsearch.

Answer 3

انظر إلى المصدر. إذا كان لديك مقابل قياسي أو أفضل ، انظر:

C: Program Files Microsoft Visual Studio 8 Vc Crt Src bsearch.c