bsearch() c 上的比较函数

Question

我正在努力在我的代码中执行 bsearch() 中的比较功能。显然，我想根据包含结构 (word_dict_t) 的字典数组上的键字符串(来自链表)进行二进制搜索

typedef struct {
    word_t name;
    probarr_t prob;
} word_dict_t;

这是我做的比较函数:

int cmp_func(const void *source, const void *dest) {
   const word_dict_t *dest_struct = (word_dict_t *)dest;
   return strcmp((const char*)source, dest_struct->name);
}

这是 bsearch() 函数的实现:

void categorize(list_t *list, word_dict_t dictionary[], int *num_dict) {
    int i=0;
    word_dict_t *result;
    word_t key;

    printf("%sSTAGE 4%s\n", LINE_STG, LINE_STG);

    while (!is_empty_list(list)){
        strcpy(key, *get_head(list));
        list=get_tail(list);

        result = (word_dict_t *) bsearch(key, dictionary, *num_dict,
                       sizeof(word_t),cmp_func);
        if (result==NULL){
            printf("%-32s NOT_NAME \n", key);
        }
        else{
            print_probabilities(result);
        }
        i++;
    }
}

word_t 是一个包含单词的字符数组。

如有任何帮助，我们将不胜感激。

Answer 1

bsearch() 需要知道数组中每个元素的大小。它作为指针传递，因此 bsearch() 需要知道如何计算每个元素的偏移量。

当 bsearch() 试图找到数组的 nth 元素时，它将执行如下操作:

ptr + size * n;

(其中 ptr 是 bsearch() 的第二个参数，size 是第四个参数)。

因此，如果您提供了错误的 size 值(您正在这样做)，bsearch() 将无法计算出正确的地址。

修复 - 传递数组元素的正确大小:

result = bsearch(key, dictionary, *num_dict, sizeof(word_dict_t), cmp_func);

或:

result = bsearch(key, dictionary, *num_dict, sizeof(dictionary[0]), cmp_func);