bsearch () всегда возвращает нулевой указатель

Question

Я пытаюсь найти строку ввода пользователя в предварительно отсортированном массиве.Если я напишу свою собственную функцию бинарного поиска, ввод будет найден правильно.Если я использую C bsearch, я всегда получаю нулевой указатель.

Это соответствующий фрагмент кода:

printf(bsearch(&input, *words, curr_idx + 1, max_len,
               (int (*)(const void *, const void *))strcmp) ?
                        "YES" : "NO");

char input[max_len] является результатом scanf("%s", input); uppercase(input);

char **words - это предварительно отсортированный массив строк в верхнем регистре.

int curr_idx - это максимальный индекс words

int max_len - это максимальная длина в байтахслов в words (в настоящее время 18)

Я пробовал вводить строки, которые, как я знаю, находятся в массиве, а также строки, которых я знаю, НЕ в массиве, и каждый случай возвращает нулевой указатель.

Установка точки останова в gdb и проверка содержимого input и words, не похоже, что что-то не так:

(gdb) print (char*)input
$5 = 0x7fffffffe610 "STONE"

(gdb) print words[150980]
$6 = 0x555555bf45a0 "STONE"

РЕДАКТИРОВАТЬ ДОБАВИТЬ MCVE:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char **words;
char *dictionary[5] = { "STOMPS", "STONABLE", "STONE", "STONEBOAT", "STONEBOATS" };
int curr_idx = 4;
int max_len = 18;

int compare(const void *a, const void *b)
{
    return strcmp((const char *)a, (const char *)b);
}

void uppercase(char *input)
{
    char *t = input;
    while (*t) {
        *t = toupper((unsigned char)*t);
        t++;
    }
}

int main()
{
        words = malloc((curr_idx + 1) * sizeof(char *));
        int i;
        for (i = 0; i < 5; i++){
               // words[i] = malloc(sizeof(char) * max_len);
               words[i] = dictionary[i];
        }

        char input[max_len];

    printf("Enter a word: ");
    scanf("%s", input);
    uppercase(input);
    printf(bsearch(input, words, curr_idx + 1, sizeof(*words), compare) ?
               "YES\n" :
               "NO\n");
}

Бит malloc() не нужен, но предназначен для максимально точного копирования исходной программы.

Answer 1

Вот сокращенная версия вашего кода:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b)
{
    return strcmp(a, b);
}

int main(void)
{
    const char *words[] = { "A" };
    puts(bsearch("A", words, 1, sizeof *words, compare) ?
            "YES" :
            "NO");
}

Проблема в том, что bsearch вызывает вашу функцию compare с указателем на текущий элемент массива (то есть вторым аргументом, то есть первым аргументом всегда является указатель ключа, данный bsearch как первый аргумент).

Ваши элементы массива являются указателями (char *), поэтому compare получает указатель на указатель на символ. Чтобы заставить strcmp работать, вам нужно разыменовать этот указатель:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b)
{
    const char *const *pstr = b;
    return strcmp(a, *pstr);
}

int main(void)
{
    const char *words[] = { "A" };
    puts(bsearch("A", words, 1, sizeof *words, compare) ?
            "YES" :
            "NO");
}

Answer 2

Ваша функция сравнения неверна.Вы сравниваете записи в массиве символьных указателей, поэтому функции сравнения передаются два значения 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 s answer ), потому что 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
$