任务描述
本关要求通过补全函数BSL_FindKey来实现在已排序的顺序表中查找关键码值为key的结点并返回该结点的编号。
相关知识
折半查找通常是针对顺序存储的线性表，线性表的结点按关键码从小到大排序，后面称之为折半查找的顺序表。为了简化讨论，假设折半查找的顺序表中每个结点只含一个关键码，关键码为整数。图 1 给出了一个存储了 4 个关键码的折半查找的顺序表的存储结构图。
下面描述了线性表顺序存储的一种实现方案。该实现方案的示意图为：
指针pkey是存储关键码的连续空间的起始地址，顺序表中当前的关键码的个数由len给出，该顺序表中最多可存储max个关键码。
将pkey、len、max组织成一个结构，该结构定义为：
struct BSeqList{int* pkey; // 指向关键码数组的指针int len; // 当前元素个数int max; // 线性表的最大元素数};
只要给定指向该结构的一指针blist，就可对线性表进行操作。
对折半查找的顺序表定义如下操作，各个操作函数的功能详见下面给出的代码文件 BSlist.cpp 的代码框架：
BSeqList* BSL_Create(int size);
void BSL_Free(BSeqList* blist);
int BSL_InsKey(BSeqList* blist, int key);
int BSL_FindKey(BSeqList* blist, int key);
int BSL_DelKey(BSeqList* blist, int key);
void BSL_Print(BSeqList* blist);
编程要求
本关的编程任务是补全 step1/BSlist.cpp 文件中的BSL_FindKey函数，以实现在已排序的顺序表中查找关键码值为key的结点并返回该结点的编号。当返回值大于等于 0 时则表示找到值为key的结点的编号，若为 -1 则表示没有找到。
本关涉及的代码文件 BSlist.cpp 的代码框架如下：
#include <stdio.h> #include <stdlib.h> #include "bsList.h" BSeqList* BSL_Create(int size) //创建一个顺序表 //与BSL_Free()配对 { 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) //释放/删除顺序表 //与BSL_Create()配对 { free(blist->pkey); free(blist); } int BSL_FindKey(BSeqList* blist, int key) //在排序的顺序表中查找关键码值为key的结点，返回结点的编号 //返回值大于等于0时表示找到值为key的结点的编号，-1表示没有找到 { // 请在此添加代码，补全函数BSL_FindKey /********** Begin *********/ /********** End **********/ } int BSL_InsKey(BSeqList* blist, int key) //在排序的顺序表中插入一个值为key的结点 //返回值大于等于0表示插入的位置, -1表示表满（无法插入） { if (blist->len>=blist->max) return -1; int k, r, m; k=0; r=blist->len-1; //寻找插入位置 while (k<=r) { m=(k+r)>>1; //m=(k+r)/2 if (key == blist->pkey[m]) return -2;若不允许插入已存在的值，则需要此行 if (key<blist->pkey[m]) r=m-1; else k=m+1; } //插入位置为k, 腾出k号位置 for (r=blist->len; r>k; r--) blist->pkey[r]=blist->pkey[r-1]; //key放入k号位置 blist->pkey[k]=key; blist->len++; return k; } int BSL_DelKey(BSeqList* blist, int key) //在排序的顺序表中删除值为key的结点, //存在值为x的结点则返回结点编号, 未找到返回－1 { int k=BSL_FindKey(blist, key); if (k<0) return -1; int i=k; while(i < blist->len-1) { blist->pkey[i] = blist->pkey[i+1]; i++; } blist->len --; return k; } 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"); }
测试说明
本关的测试文件是 step1/Main.cpp ，测试过程如下：
- 平台编译 step1/Main.cpp ，然后链接相关程序库并生成 exe 可执行文件；
- 平台运行该 exe 可执行文件，并以标准输入方式提供测试输入；
- 平台获取该 exe 可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。
输入输出格式说明
输入格式： 首先输入一个正整数max，创建一个最多可存储max个元素的表。 然后输入多个操作：如果输入 “insert” ，则后面跟一个数x，表示将x插入；如果输入 “delete” ，则后面跟一个数x，表示将x删除；如果输入 “end” ，表示输入结束。
输出格式： 输出表的长度，然后从表头到表尾依次输出各元素。
以下是平台对 step1/Main.cpp 的样例测试集：
样例输入： 9 insert 9 insert 8 insert 89 insert 11 insert 22 insert 13 delete 11 delete 5 end
样例输出： list length: 5 The list contains: 8 9 13 22 89
开始你的任务吧，祝你成功！
AC_Code
//折半查找的顺序表 实现文件 //每个结点的数据是关键码 // #include <stdio.h> #include <stdlib.h> #include "BSlist.h" BSeqList* BSL_Create(int size) //创建一个顺序表 //与BSL_Free()配对 { 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) //释放/删除顺序表 //与BSL_Create()配对 { free(blist->pkey); free(blist); } int BSL_FindKey(BSeqList* blist, int key) //在排序的顺序表中查找关键码值为key的结点，返回结点的编号 //返回值大于等于0时表示找到值为key的结点的编号，-1表示没有找到 { /*请在BEGIN和END之间实现你的代码*/ /*****BEGIN*****/ int k,r,m;//k是low，r是high，m是mid k=0; r=blist->len-1; while(k<=r) { m=(k+r)/2; if(key==blist->pkey[m]) { return m; } else { if(key<blist->pkey[m]) { r=m-1; } else { k=m+1; } } } return -1; /******END******/ /*请不要修改[BEGIN,END]区域外的代码*/ } int BSL_InsKey(BSeqList* blist, int key) //在排序的顺序表中插入一个值为key的结点 //返回值大于等于0时表示插入的位置, -1表示表满（无法插入） { if (blist->len>=blist->max) return -1; int k, r, m; k=0; r=blist->len-1; //寻找插入位置 while (k<=r) { m=(k+r)>>1; //m=(k+r)/2 if (key == blist->pkey[m]) return -2;若不允许插入已存在的值，则需要此行 if (key<blist->pkey[m]) r=m-1; else k=m+1; } //插入位置为k, 腾出k号位置 for (r=blist->len; r>k; r--) blist->pkey[r]=blist->pkey[r-1]; //key放入k号位置 blist->pkey[k]=key; blist->len++; return k; } int BSL_DelKey(BSeqList* blist, int key) //在排序的顺序表中删除值为key的结点, //存在值为x的结点则返回结点编号, 未找到返回－1 { int k=BSL_FindKey(blist, key); if (k<0) return -1; int i=k; while(i < blist->len-1) { blist->pkey[i] = blist->pkey[i+1]; i++; } blist->len --; return k; } 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"); }
