你的比较函数是错误的。您正在比较字符指针数组中的条目,因此比较函数传递了两个char **
伪装为const void *
. 您的比较代码需要做出相应的反应。
int compare(const void *v1, const void *v2)
{
const char *s1 = *(char **)v1;
const char *s2 = *(char **)v2;
// printf("[%s] <=> [%s] = %d\n", s1, s2, strcmp(s1, s2));
return strcmp(s1, s2);
}
然后也需要正确调用 bsearch 函数:
char *key = input;
bsearch(&key, words, 5, sizeof(*words), compare);
与其他比较函数相比,此比较函数的优势在于可以使用相同的比较器qsort()
对数组中的数据进行排序,从而确保比较是……错误……可比较的。您可以设计其他驾驶方式bsearch()
(请参阅melpomene的回答),因为bsearch()
始终将密钥作为第一个参数传递给比较函数。但是在我看来,使用相同的比较器进行排序和搜索(而不是需要两个不同的函数)的能力似乎超过了不总是取消引用键的好处。
工作代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
static char **words;
static char *dictionary[] = { "STOMPS", "STONABLE", "STONE", "STONEBOAT", "STONEBOATS" };
static int curr_idx = 4;
static int max_len = 18;
#if 0
int compare(const void *a, const void *b)
{
return strcmp((const char *)a, (const char *)b);
}
#endif
static int compare(const void *v1, const void *v2)
{
const char *s1 = *(char **)v1;
const char *s2 = *(char **)v2;
printf("%s(): [%s] <=> [%s] = %d\n", __func__, s1, s2, strcmp(s1, s2));
return strcmp(s1, s2);
}
static void uppercase(char *input)
{
char *t = input;
while (*t)
{
*t = toupper((unsigned char)*t);
t++;
}
}
int main(void)
{
words = malloc((curr_idx + 1) * sizeof(char *));
int i;
for (i = 0; i < curr_idx + 1; i++)
{
// words[i] = malloc(sizeof(char) * max_len);
words[i] = dictionary[i];
}
char input[max_len];
char fmt[10];
snprintf(fmt, sizeof(fmt), "%%%ds", max_len - 1);
while (printf("Enter a word: ") > 0 && scanf(fmt, input) == 1)
{
uppercase(input);
char *key = input;
char **result = bsearch(&key, words, curr_idx + 1, sizeof(*words), compare);
if (result != 0)
printf("Key [%s] found at %p [%s]\n", input, result, *result);
else
printf("Key [%s] not found\n", input);
}
putchar('\n');
return 0;
}
示例运行(程序名称bs11
):
$ ./bs11
Enter a word: abracadabra
compare(): [ABRACADABRA] <=> [STONE] = -18
compare(): [ABRACADABRA] <=> [STONABLE] = -18
compare(): [ABRACADABRA] <=> [STOMPS] = -18
Key [ABRACADABRA] not found
Enter a word: STOMPS
compare(): [STOMPS] <=> [STONE] = -1
compare(): [STOMPS] <=> [STONABLE] = -1
compare(): [STOMPS] <=> [STOMPS] = 0
Key [STOMPS] found at 0x7fa1e4402a70 [STOMPS]
Enter a word: stona
compare(): [STONA] <=> [STONE] = -4
compare(): [STONA] <=> [STONABLE] = -66
compare(): [STONA] <=> [STOMPS] = 1
Key [STONA] not found
Enter a word: STONABLE
compare(): [STONABLE] <=> [STONE] = -4
compare(): [STONABLE] <=> [STONABLE] = 0
Key [STONABLE] found at 0x7fa1e4402a78 [STONABLE]
Enter a word: stonable
compare(): [STONABLE] <=> [STONE] = -4
compare(): [STONABLE] <=> [STONABLE] = 0
Key [STONABLE] found at 0x7fa1e4402a78 [STONABLE]
Enter a word: stonc
compare(): [STONC] <=> [STONE] = -2
compare(): [STONC] <=> [STONABLE] = 2
Key [STONC] not found
Enter a word: STONE
compare(): [STONE] <=> [STONE] = 0
Key [STONE] found at 0x7fa1e4402a80 [STONE]
Enter a word: stobneage
compare(): [STOBNEAGE] <=> [STONE] = -12
compare(): [STOBNEAGE] <=> [STONABLE] = -12
compare(): [STOBNEAGE] <=> [STOMPS] = -11
Key [STOBNEAGE] not found
Enter a word: STONEBOAT
compare(): [STONEBOAT] <=> [STONE] = 66
compare(): [STONEBOAT] <=> [STONEBOATS] = -83
compare(): [STONEBOAT] <=> [STONEBOAT] = 0
Key [STONEBOAT] found at 0x7fa1e4402a88 [STONEBOAT]
Enter a word: stoneboatatdawn
compare(): [STONEBOATATDAWN] <=> [STONE] = 66
compare(): [STONEBOATATDAWN] <=> [STONEBOATS] = -18
compare(): [STONEBOATATDAWN] <=> [STONEBOAT] = 65
Key [STONEBOATATDAWN] not found
Enter a word: STONEBOATS
compare(): [STONEBOATS] <=> [STONE] = 66
compare(): [STONEBOATS] <=> [STONEBOATS] = 0
Key [STONEBOATS] found at 0x7fa1e4402a90 [STONEBOATS]
Enter a word: zoo
compare(): [ZOO] <=> [STONE] = 7
compare(): [ZOO] <=> [STONEBOATS] = 7
Key [ZOO] not found
Enter a word: ^D
$