标准C库中的bsearch（）函数是如何实现的？

有谁知道标准二进制搜索功能是如何实现的？标准C库中的bsearch（）函数是如何实现的？

这是原型。

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

我真的很好奇他们如何使用void指针。

来源

2010-01-03 Dave Danuve

要小心GCC的代码 - 将'void *'等同于'char *'用于计算地址，而C标准则说您不能对'void *'值进行算术计算。 – 2010-01-03 03:31:03

@Jonathan：我不确定GCC是如何进入的;他列出的原型（在问题中提到的唯一的地方是'void *'）是直接脱离C99标准的。 – 2010-01-04 23:36:12

我相信Jonathan的评论是关于'void *'上依赖算术的'bsearch'的一些实现。一个可移植的实现（即自身符合标准的实现）不能做到这一点。 – 2010-01-13 09:09:07

我假设你有兴趣知道如何在bsearch中使用void *指针，而不是实际的二进制搜索算法本身。原型为bsearch是：

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

这里，void *用于使任意类型的搜索。指针的解释由（用户提供的）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*nbase，因为它是void *类型，并且算术上void *未定义。

来源

2010-01-13 09:05:49

我不认为这个技巧是标准允许的。 – 2010-01-13 22:12:18

@Dave：你指的是什么部分？ – 2010-01-13 22:52:49

从（void *）转换为（char *）。反正我检查过，它是允许的。谢谢。 – 2010-02-10 20:01:32

-1

看看源代码。如果你有VS标准或更好的，请参阅：

C：\ Program Files文件\微软的Visual Studio 8 \ VC \ CRT \ SRC \ bsearch.c

来源

2010-01-03 03:03:16

见bsearch @ Google's codesearch 为bsearch不同的实现。

来源

2010-01-03 03:07:51 cschol

标准C库中的bsearch（）函数是如何实现的？

回答

相关问题