c - 如何在c中的2个排序数据表上使用二进制搜索

Question

我正在研究如何在 C 语言中使用二进制搜索。

我将开始，

我有一个结构

struct keyval{
unsigned short key[2];
unsigned short val[2];
};

如您所见，这是一个包含 2 个短数组的结构，可以保存 2 个短值。

然后我将内存分配给这些结构。这使我能够在内存中存储许多此类结构。

struct keyval *codes1 = malloc(sizeof(struct keyval)*(0x1000000));
struct keyval *codes2 = malloc(sizeof(struct keyval)*(0x1000000));

我经历了一些循环并用 struct keyval 填充 code1。然后在另一个循环中，我还用 struct keyval 填充 code2

此数据将根据迭代键填充。所以基本上它会自动按键值排序。

然后我根据 val 值对我的数据进行排序。使用 c qsort 函数 和我自己的比较功能 如果一个 val 数组的位置 0 中的 short 小于另一个结构中相同位置的 short，则返回 -1 等等。

qsort(codes1,SIZE_OF_CODES1, sizeof(struct keyval), compare);
qsort(codes2,SIZE_OF_CODES2, sizeof(struct keyval), compare);

int compare(const void *a, const void *b){
    struct keyval *ia = (struct keyval *)a;
    struct keyval *ib = (struct keyval *)b;

    if(ia->val[0] > ib->val[0]){
        return 1;
    }else if (ia->val[0] < ib->val[0]){
        return -1;
    }else{
        return (ia->val[1] - ib->val[1]);
    }

现在这是我卡住的地方

我需要能够根据代码 2 中的值对代码 1 中的每个值进行二进制搜索。 当 codes1[i].val == codes2[i].val 我可以打印出 codes1[i].key 的值 然后是 codes2.[i].key

我的尝试是这样的

while(e <= SIZE_OF_CODES1){

    struct keyval *found = (struct keyval*) bsearch(&codes1[e],codes2,SIZE_OF_CODES2,sizeof(struct keyval),compare );

    if(found){
        printf("\n found key = %08x %04x value = %04x %04x", found -> key, found -> key[1],found->val[0],found ->val[1] );
    }

    e++;
}

上面的代码不会发现数据是否匹配，因为我确定代码中有匹配的地方

//添加编辑

---

刚刚调试了一下，我发现当bsearch调用比较函数时，每次调用它时，所有与ia关联的值都是零，但ib是正确的。

排序方式正确

---

有人能给我指出正确的方向来实现二分查找吗，我被困住了

我的旧比较函数

int compare(const void *a, const void *b){
struct keyval *ia = (struct keyval *)a;
struct keyval *ib = (struct keyval *)b;

if(ia->val[0] > ib->val[0]){

    return 1;
}else if(ia->val[0] < ib->val[0]){
    return -1;
}else{
    if(ia->val[1] > ib->val[1]){
        return 1;
    }else if(ia->val[1] < ib->val[1]){
        return -1;
    }else{
        return 0;
        }
}

Answer 1

要按照您的描述比较列表，逐步执行代码 1，然后对代码 1 中的每个条目在代码 2 上执行 bsearch()。您可以重复使用比较。我不确定 SIZE_OF_CODES1 和 2 是变量还是定义，我假设它们反射(reflect)了每个数组中元素的数量。

struct keyval *src=codes1;
struct keyval *dest=code2;
struct keyval *p
int i=0;
while(i< SIZE_OF_CODES1)
{
    if( (p=(struct keyval *)bsearch(src, dest, SIZE_OF_CODES2, sizeof(struct keyval), compare))!=NULL)
        printf("duplicate codes1: %d %d  codes2: %d %d\n", src->key,src->val, p->key, p->val);
    i++
}