比较功能中的 Bsearch 和垃圾值

Question

我有以下程序：

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

#define DICT_BUFSIZE 64

int compar(const void * a, const void * b)
{
    const char* c1 = (const char*)a;
    const char* c2 = (const char*)b;

    printf("c1: %s | c2: %s\n", c1, c2);

    return strcmp(c1, c2);
}

int main (void)
{
    FILE*     fdict;
    uint32_t  i;
    char**    dict = NULL;
    size_t    size = 0;
    size_t    size_alloced = 0;
    char      buf[DICT_BUFSIZE];

    fdict = fopen("/usr/share/dict/words", "r");
    if (!fdict) {
        printf("Could not open \"%s\": %s\n", "usr/share/dict/words", strerror(errno));
        exit(1);
    }

    for (i = 0; fgets(buf, DICT_BUFSIZE, fdict); ++i) {
        size_t len;

        if (i == size_alloced) {
            dict = realloc(dict, (i +50000) * sizeof(*dict));
            size_alloced += 50000;
        }
        len = strlen(buf);
        dict[i] = malloc(len);

        memcpy(dict[i], buf, len -1);
        dict[i][len -1] = '[=10=]';
    }
    size = i;

    //for (i = 0; i < size; i++)
        //printf("%s\n", dict[i]);

    if(bsearch("company", dict, size, sizeof(*dict), compar))
        printf("Found!\n");

    for (i = 0; i < size; ++i)
        free(dict[i]);
    free(dict);

    fclose(fdict);

    return 0;
}

在 "compar" 函数中 "c1" 变量（要搜索的键）显示正确，但是 v2 变量中有垃圾输出。

这是一个示例输出：

c1: company | c2: ���
c1: company | c2: �$z
c1: company | c2: ��I
c1: company | c2: ��7
c1: company | c2: P�.
c1: company | c2: �b3
c1: company | c2: �1
c1: company | c2: P�/
c1: company | c2: ��0
c1: company | c2: PC0
c1: company | c2: @g0
c1: company | c2:  y0
c1: company | c2: 0�0
c1: company | c2: ��0
c1: company | c2: `�0
c1: company | c2: ��0
c1: company | c2: 
c1: company | c2: P�0

我无法理解这种行为。

Answer 1

如果您要搜索 int 的数组，您会将 const void * 参数转换为比较函数 int *，不是吗？

您正在搜索 char * 的数组，因此您需要将 const void * 参数转换为 char ** — 并且您需要传递 char ** 参数寻找价值。

您的代码所需的更改很少但很重要：

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

#define DICT_BUFSIZE 64

static int compar(const void *a, const void *b)
{
    const char *c1 = *(const char **)a;
    const char *c2 = *(const char **)b;

    printf("c1: %s | c2: %s\n", c1, c2);

    return strcmp(c1, c2);
}

int main (void)
{
    FILE*     fdict;
    uint32_t  i;
    char**    dict = NULL;
    size_t    size = 0;
    size_t    size_alloced = 0;
    char      buf[DICT_BUFSIZE];
    const char *file = "/usr/share/dict/words";

    fdict = fopen(file, "r");
    if (!fdict) {
        printf("Could not open \"%s\": %s\n", file, strerror(errno));
        exit(1);
    }

    for (i = 0; fgets(buf, DICT_BUFSIZE, fdict); ++i) {
        size_t len;

        if (i == size_alloced) {
            dict = realloc(dict, (i +50000) * sizeof(*dict));
            size_alloced += 50000;
        }
        len = strlen(buf);
        dict[i] = malloc(len);

        memcpy(dict[i], buf, len -1);
        dict[i][len -1] = '[=10=]';
    }
    size = i;

    //for (i = 0; i < size; i++)
        //printf("%s\n", dict[i]);

    const char *search = "company";
    if(bsearch(&search, dict, size, sizeof(*dict), compar))
        printf("Found!\n");

    for (i = 0; i < size; ++i)
        free(dict[i]);
    free(dict);

    fclose(fdict);

    return 0;
}

比较器函数现在需要两个 char ** 值，并捕获每个值指向的字符串。

调用的第一个参数需要是char *变量的地址；因此添加变量 const char *search = "company";.

次要清理包括使比较器函数静态化（主要是为了满足我迂腐的默认编译选项——尽管最好在定义函数之前声明函数），并使用变量 const char *file = "/usr/share/dict/words"; 来避免（接近) 调用 fopen() 和错误消息之间的重复。

示例输出（运行在具有 macOS Sierra 10.12.3 的 Mac 上）：

c1: company | c2: modifier
c1: company | c2: eagle
c1: company | c2: Canarian
c1: company | c2: counteridea
c1: company | c2: citropten
c1: company | c2: compulsoriness
c1: company | c2: coelenteric
c1: company | c2: Colossian
c1: company | c2: commonable
c1: company | c2: compilation
c1: company | c2: compagination
c1: company | c2: compatriot
c1: company | c2: comparition
c1: company | c2: comparable
c1: company | c2: companionate
c1: company | c2: companionway
c1: company | c2: comparability
c1: company | c2: company
Found!

比较功能中的 Bsearch 和垃圾值

Bsearch and junk values in the comparison function

c

bsearch