bsearch не ищет весь переданный ему массив

Question

У меня проблемы с этим исследователем. Я уверен, что я выделил проблему в число байтов параметра, который принимает bsearch. Массив данных - это словарь скрэббл, и я на 100% уверен, что весь словарь загружен в память, но когда я использую bsearch для Попытайтесь найти, находится ли определенное слово в словаре, оно работает только для слов до слова "Wontenly", хотя последнее слово словаря - "zzz", поэтому некоторые слова, начинающиеся с "w", "x", "y" и "z", не может быть найден. Это почти как если бы функция bsearch не видела конец массива, даже если он там есть. Также следует отметить, что в моей функции сравнения я распечатываю то, что bsearch передал ей, чтобы увидеть, какие слова сравниваются, и кажется, что при первом сравнении bsearch не отправляет среднее значение, которое является чем-то вроде 'lunkheads' вместо этого он начинается с слова "lodge", которое не является средним словом в словаре. 16 байтов - это число, которое я вставил методом проб и ошибок, которое, кажется, работает. Проблема в том, что я не знаю, какова длина каждого элемента в массиве, или, по крайней мере, я думаю, что это проблема.

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

#define LEN 128


 int search(const void *usr_word,const void *words);

struct data_t {
    int nval;       /* current number of values in array */
    int max;        /* allocated number of values */
    char **data;        /* the data array */
};

enum {INIT = 1, GROW = 2};

int main(void)
{
    FILE *fp = fopen("scrabble.txt", "r");
    assert(fp);
    char *usr_word = NULL;
    char buf[LEN];
    int i = 0;
    char number[LEN];
    char* item = NULL;


    struct data_t *data = malloc(sizeof(struct data_t));
    data->nval = INIT;
    data->max = INIT;
    data->data = NULL;
    while (fgets(buf, LEN, fp)) {
            if (data->data == NULL) {
                    data->data = malloc(strlen(buf) - 1);
                    assert(data->data);
            }
            else if (data->nval > data->max) {
                    data->data = realloc(data->data, GROW * data->max * LEN);
                    assert(data->data);
                    data->max = GROW * data->max;
            }

            data->data[i] = strndup(buf, strlen(buf) - 1);
            i++;
            data->nval++;
    }
    /* overcounted */
    data->nval--;
    printf("Enter word: ");
    fgets(buf, LEN, stdin);
    usr_word = strndup(buf, strlen(buf)-1);

    /*search for word*/
    item = (char *) bsearch(usr_word, data->data[0], data->nval, 16, search);
    if (item != NULL) 
           printf("\n%s is valid\n", item);
    else if (item == NULL)
           printf("\n%s is not valid\n", usr_word);

    return 0;
}

int search(const void *usr_word,const void *words)
{      
 printf("%s | %s | %d\n", (char *)usr_word,(char *)  words, strcmp(usr_word,words));
    return strcmp(usr_word,words);
}

Answer 1

Хорошо, в вашем коде много проблем, связанных с вашим неправильным пониманием char ** который используется в struct data_t.data.

char ** это массив указателей на указатели. это никак не массив строк.

Это означает следующее:

data->data = malloc(strlen(buf) - 1);

должно быть заменено следующим:

data->data = malloc(sizeof(char *) * (data->nval));

то же самое с realloc:

data->data = realloc(data->data, GROW * data->max * LEN);

заменить

data->data = realloc(data->data, GROW * data->max * sizeof(char *));

далее вызов bsearch:

item = (char *) bsearch(usr_word, data->data[0], data->nval, 16, search);

заменить:

item = (char **) bsearch(usr_word, data->data, data->nval, sizeof(char*), search);

Посмотрите, как я заменил 16 с sizeof(char*)? это потому что bsearch применяется к char **Например, массив char *следовательно, элементарный элемент поиска char *, Следовательно, возвращаемое значение из bsearch является pointer to elementary item, e.g. pointer toсимвол *, e.g.символ **`.

цитата из manpage:

Функция bsearch() возвращает указатель на соответствующий элемент массива

Следующим является printf:

printf("\n%s is valid\n", item);

я заменил на: printf("\n%s является действительным \n", *item);

*item вместо item происходит по той же причине - bsearch возвращает нам указатель на то, что он нашел. Нам нужно преобразовать этот указатель в реальное значение.

И, наконец, ваш search:

printf("%s | %s | %d\n", (char *)usr_word,(char *)  words, strcmp(usr_word,words));
return strcmp(usr_word,words);

Опять же, используйте правильный уровень указателей - у нас есть два уровня, и нам нужен один уровень:

printf("%s | %s | %d\n", (char *)usr_word,*(char **)  words, strcmp(usr_word,words));
return strcmp(usr_word,*(char**)words);

Для вашего удобства, вот вся программа, которая работает:

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

#define LEN 128

int search(const void *usr_word,const void *words);

struct data_t {
    int nval;       /* current number of values in array */
    int max;        /* allocated number of values */
    char **data;        /* the data array */
};

enum {INIT = 1, GROW = 2};

int main(void)
{
FILE *fp = fopen("scrabble.txt", "r");
assert(fp);
char *usr_word = NULL;
char buf[LEN];
int i = 0;
char number[LEN];
char** item = NULL;


struct data_t *data = malloc(sizeof(struct data_t));
data->nval = INIT;
data->max = INIT;
data->data = NULL;
while (fgets(buf, LEN, fp)) {
        if (data->data == NULL) {
                data->data = malloc(sizeof(char *) * (data->nval));
                assert(data->data);
        }
        else if (data->nval > data->max) {
                data->data = realloc(data->data, GROW * data->max * sizeof(char *));
                assert(data->data);
                data->max = GROW * data->max;
        }

        data->data[i] = strndup(buf, strlen(buf) - 1);
        i++;
        data->nval++;
}
/* overcounted */
data->nval--;
printf("Enter word: ");
fgets(buf, LEN, stdin);
usr_word = strndup(buf, strlen(buf)-1);

/*search for word*/
item = (char **) bsearch(usr_word, data->data, data->nval, sizeof(char*), search);
if (item != NULL)
       printf("\n%s is valid\n", *item);
else if (item == NULL)
       printf("\n%s is not valid\n", usr_word);

for(i=0;i<data->nval;++i) free(data->data[i]);
free(data->data);
free(data);
free(usr_word);

return 0;
}

int search(const void *usr_word,const void *words)
{
 printf("%s | %s | %d\n", (char *)usr_word,*(char **)  words,     strcmp(usr_word,words));
    return strcmp(usr_word,*(char**)words);
}