bsearch() 在 C 中的字符串数组上

bsearch() on an array of strings in C

我正在用 C 实现一个代码,以便在字符数组 ( string ) 中复制一个字符串,然后对其进行 bsearch。但出乎意料的是,bsearch returns 错误的结果应该是正确的。 我猜这与我在插入过程中首先插入字符串的方式有关。您可以将其视为在 btree 的叶节点上进行插入和搜索。

我在多文件框架中对此进行编码,因此无法 post 所有代码。 post阅读相关部分

字符串数组的结构更易于可视化 -

array of strings ( array of array of chars ) 
                            --
                          0 -- array of characters ( size may be 5 )  
                          1 -- array of characters ( size may be 7 ) 
                          2 -- array of characters ( size may be 10 )

or

keys = [
         [ s t r i n g 1 ]
         [ s t r i n g T w o ]
         [ s t r i n g T H R E E ]
       ]

要插入的函数 -

void insert_in_leaf_node(struct leaf_node * node, u32 len, u8 * key){
    if (node->no_of_keys > 1 ) {
       if (!search_in_fat(node, len, key)) {
            node->keys[node->no_of_keys] = (char *) malloc(sizeof(char) * len);
            strncpy(node->keys[node->no_of_keys], (char *) key, len);                                                              // copy key to array
            node->keys[node->no_of_keys][len] = '[=11=]';
            node->no_of_keys += 1;
            qsort(node->keys, (size_t) node->no_of_keys, sizeof(char *), cstring_cmp);                                          // sort alphabetically to enable bsearch later
        }
    } else {
        node->keys[node->no_of_keys] = (char *) malloc(sizeof(char) * len);
        strncpy(node->keys[node->no_of_keys], (char *) key, len);                                                              // copy key to array
        node->keys[node->no_of_keys][len] = '[=11=]';
        node->no_of_keys += 1;
        qsort(node->keys, (size_t) node->no_of_keys, sizeof(char *), cstring_cmp);                                          // sort alphabetically to enable bsearch later
    }
}

要搜索的代码 -

bool search_in_fat(struct leaf_node * node, u32 len, u8 * key){
    if(!bsearch(key,node->keys,(size_t)node->no_of_keys, sizeof( char * ),(int(*)(const void*,const void*)) strcmp)) return false;
    return true;
}

cstring_cmp 插入函数中使用的函数 -

int cstring_cmp(const void *a, const void *b)
{
    const char **ia = (const char **)a;
    const char **ib = (const char **)b;
    return strcmp(*ia, *ib);
    /* strcmp functions works exactly as expected from
    comparison function */
}

如果有人想知道键中有什么,下面是如何更早地填充键数组以及每次使用单独的键调用 set/get 函数(set/get 函数调用上述函数)

从文件中加载跟踪以生成键数组的代码 - (__samples 持有钥匙)

bool
load_trace(const char * const filename)
{
  char * buf = NULL;
  size_t size = 0;
  FILE * fin = fopen(filename, "r");
  if (fin == NULL) return false;
  u64 i = 0;
  // count for lines
  while (getline(&buf, &size, fin) >= 1) {
    i++;
  }
  rewind(fin);
  __samples = malloc(sizeof(char *) * i);
  __sizes = malloc(sizeof(u32) * i);
  __nr_samples = i;
  ssize_t len = 0;
  i = 0;
  while ((len = getline(&buf, &size, fin)) >= 1) {
    if (buf[len-1] == '\n') { // remove trailing '\n'
      len--;
      buf[len] = '[=14=]';
    }
    __samples[i] = strdup(buf);
    __sizes[i] = len;
    i++;
  }
  free(buf);
  fclose(fin);
  return true;
}

P.S : 这部分不是我写的,是学长在搭建框架的时候写的

可能是什么问题?我已经做了很多谷歌搜索,但还没有积极的结果。

谢谢!

您不能将 strcmp() 作为 bsearch() 的比较函数。该函数需要采用指向要比较的元素的指针(在本例中是指向字符串指针的指针,尽管函数参数的实际类型需要是 const void *),而 strcmp() 需要一个指向字符串的指针。它没有处理额外的间接层。

你没有显示函数,但是你用qsort()cstring_cmp()函数应该可以用。

bsearch()比较函数的第一个参数是作为键给出的指针,第二个参数是指向被比较数组的当前元素的指针,其中与qsort()比较函数,两个参数都是指向元素的指针。因此,如果您将 bsearch() 的关键参数设为指向您要查找的内容的指针,则两者将使用相同的函数。换句话说,bsearch(&key, ...) 好,bsearch(key, ...) 不好。您还可以使用特定于 bsearch() 的比较函数来处理第二种情况。有关示例,请参阅 。