-2

有没有办法实现bsearch()找到多个 key 实例。

例如：(obj*)bsearch(key=r,arr,elements,sizeof(obj),(int(*)(const void*, const void*)bcompare);

我目前编写的代码只能找到第一个实例，并且由于它的工作原理，无法继续找到第一个实例。

getline(target,81);
if(strcmp(target,"exit") == 0 || strcmp(target, "") == 0) break;
p = (Info*)bsearch(target,list,num,sizeof(Info),(int(*)(const void*, const void*))bcompare);
int foundIndex = (int)(p-list);
if(!p){
    err_dis1_win();
    clrscr();
}
else{
    display_record(p);
    cout << "\n\n found at index " << foundIndex << "\n";
    getch();
    clrscr();   
}

变量：

  • p - 是指向 Info 类对象的指针
  • 目标- char 的 arr
  • list - obj 的 arr
  • foundIndex - 找到的元素的索引
  • Info - 从基类派生的类

**比较功能

int bcompare(char *a,Info *b){
    return(strncmpi(a, b -> get_name(), strlen(a)));
}

我不能使用其他方法，例如std::find或编写自己的二进制搜索函数，必须使用bsearch()

我尝试了 else 块内的循环，以及使用变量 foundIndex 的比较函数，以及在通过 obj 列表 arr 循环的返回值上使用 while 循环。有没有办法从特定索引开始。我很感激任何帮助。我不是在寻找代码，而是在朝着正确的方向总体推进。谢谢你。

警告- 当前代码按预期编译和运行，但是我自己无法弄清楚我想要的功能。Google 和 Stackoverflow 上的搜索没有产生相关问题。

4

1 回答 1

2

由于bsearch()只返回一个项目，我将“查找键的多个实例”解释为“查找键的第一个实例”。然后，调用者可以从该项目向前遍历数组以处理与键匹配的每个项目，直到它到达末尾或到达不匹配的项目。

如果您必须使用标准库的bsearch()函数并说服它找到与给定键匹配的第一个项目，那么您真正需要使用的只是您提供的比较函数。 bsearch()将根据该函数返回与键匹配的项目，但如果多个项目匹配，则无法保证将返回哪一个。然后，您必须确保只有您想要的项目匹配。

您可以通过适当的比较函数实现来解决这个问题，但存在一个重大问题。在某些情况下，该函数需要评估指定给它的项目之前的项目，但它不能尝试检查数组第一个项目之前的项目。 bsearch()本身不会将有关数组边界的任何信息传达给比较函数。

至少有两种可能的解决方案，它们都不是一流的。

  1. 将数组下限存储在函数可以访问的某个众所周知的位置。 例如，如果比较函数是静态成员函数，那么您可能会使用其类的静态变量。但这不是线程安全的。你可以用线程局部变量做类似的事情，但即使这样也很难看。无论哪种方式，您都必须确保在调用之前适当地设置该变量bsearch()，这也很丑陋。

或者

  1. 确保您从不bsearch()为第一项。 您可以这样做的一种方法是初步检查第一项是否匹配（但不是通过比较函数），并直接使用它而不是bsearch()在它匹配的情况下调用它。我自己把它包装在一个方法中，如果你不能这样做，那么要求手动使用这样的调用规则也是丑陋的。

选择上述之一后，您可以实现一个比较函数，该函数除了查看指定项目的键之外，还查看前一个项目的键。这些方面的东西（假设第二种选择）：

struct my_item {
    int key;
    void *data;
};

// bsearch() passes the target item as the first argument, and the one to compare
// to it as the second
int compare_items(const void *to_find, const void *to_check) {
    const struct my_item *to_find_item = (const struct my_item *) to_find;
    const struct my_item *to_check_item = (const struct my_item *) to_check;

    // Check first how the key members are ordered
    if (to_find_item->key < to_check_item->key) {
        return -1;
    } else if (to_find_item->key > to_check_item->key) {
        return 1;
    } else {
        // The key members match, so check whether we're looking at the first
        // such item.
        const struct my_item *previous_item = to_check_item - 1;

        // If the previous item's key does match, then we know the item we're
        // looking for is an earlier one than we are presently checking.
        return (previous_item->key == to_check_item->key) ? -1 : 0;
    }
}
于 2018-12-07T18:05:30.727 回答