完善下列代码，要求如下：实现在已排序的顺序表中查找关键码值为key的结点并返回该结点的编号。当返回值大于等于 0 时则表示找到值为key的结点的编号，若为 -1 则表示没有找到。代码如下： #include <stdio.h> #include <stdlib.h> #include "BSlist.h" BSeqList* BSL_Create(int size){ BSeqList* blist=(BSeqList*)malloc(sizeof(BSeqList)); blist->pkey = (int*)malloc(sizeof(int)size); blist->max=size; blist->len=0; return blist; } void BSL_Free(BSeqList blist) { free(blist->pkey); free(blist); } int BSL_FindKey(BSeqList* blist, int key) { } int BSL_InsKey(BSeqList* blist, int key) { } int BSL_DelKey(BSeqList* blist, int key) { } void BSL_Print(BSeqList* blist) { if (blist->len==0) { printf("The list is empty.\n"); return; } printf("The list contains: "); for (int i=0; i<blist->len; i++) { printf("%d ", blist->pkey[i]); } printf("\n"); }

int BSL_FindKey(BSeqList* blist, int key) {
int low = 0, high = blist->len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (blist->pkey[mid] == key) {
return mid;
} else if (blist->pkey[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

在 BSlist.cpp 文件中补全上面的代码，实现在已排序的顺序表中查找关键码值为 key 的结点并返回该结点的编号。算法采用二分查找，时间复杂度 O(logn)。注意修改 BSL_Free 函数的参数类型为指针类型。

相关问题

本关要求通过补全函数BSL_FindKey来实现在已排序的顺序表中查找关键码值为key的结点并返回该结点的编号。

好的，我知道了。下面是补全后的函数代码：

int BSL_FindKey(SeqList L, KeyType key) {
    int low = 0, high = L.length - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.data[mid].key == key) {
            return mid;
        }
        else if (L.data[mid].key < key) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1; // 未找到返回-1
}

其中，SeqList是已排序的顺序表，KeyType是关键码类型，L.data[mid].key表示顺序表中第mid个结点的关键码值。函数中采用二分查找的方法，将查找区间不断缩小，直到找到关键码为key的结点或查找区间为空。如果未找到，则返回-1。

完善下列代码，要求如下：本关的编程任务是补全 step1/BSlist.cpp 文件中的BSL_FindKey函数，以实现在已排序的顺序表中查找关键码值为key的结点并返回该结点的编号。当返回值大于等于 0 时则表示找到值为key的结点的编号，若为 -1 则表示没有找到。代码如下： #include <stdio.h> #include <stdlib.h> #include "BSlist.h" BSeqList* BSL_Create(int size){ BSeqList* blist=(BSeqList*)malloc(sizeof(BSeqList)); blist->pkey = (int*)malloc(sizeof(int)*size); blist->max=size; blist->len=0; return blist; } void BSL_Free(BSeqList* blist) { free(blist->pkey); free(blist); } int BSL_FindKey(BSeqList* blist, int key) { } int BSL_InsKey(BSeqList* blist, int key) { } int BSL_DelKey(BSeqList* blist, int key) { } void BSL_Print(BSeqList* blist) { if (blist->len==0) { printf("The list is empty.\n"); return; } printf("The list contains: "); for (int i=0; i<blist->len; i++) { printf("%d ", blist->pkey[i]); } printf("\n"); }

int BSL_FindKey(BSeqList* blist, int key) {
int low = 0, high = blist->len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (blist->pkey[mid] == key) {
return mid;
} else if (blist->pkey[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

在 BSlist.cpp 文件中补全上面的代码，实现在已排序的顺序表中查找关键码值为 key 的结点并返回该结点的编号。算法采用二分查找，时间复杂度 O(logn)。