程序填空题:有序顺序表的折半查找
本题目要求创建一个有序顺序表并进行折半查找,顺序表中的元素由小到大排列。
```c++
#include
#include
#include
#define OK 1
#define OVERFLOW -1
typedef int Status;
typedef int ElemType;
typedef struct SqList{
ElemType *elem; //存放元素的数组。从1号开始存放元素
int length; //有效元素的个数
}SqList;
//下面的函数用于创建一个有序顺序表,n代表元素个数。
Status ListCreate(SqList &L, int n){
@@[L.elem=(ElemType *)malloc((n+1)*sizeof(ElemType))](3); //补充代码开辟一个长度为n+1的数组
if(!L.elem)exit(OVERFLOW);
L.length=n ;
for(int i=1;i<=L.length;++i)
L.elem[i]= 2*i ;
return OK;
}
//下面的函数用于折半查找。查找成功时返回位序(从1开始),查找失败则返回0。
int BinSearch(SqList &L, ElemType x){
int low, high, mid;
low=1; high=L.length;
while(low <= high ){
@@[mid=(low+high)/2](3);
if(x==L.elem[mid])
return mid;
else if(x @@[high=mid-1](4);
else
low=mid+1;
}
return 0;
}
int main()
{
SqList L;
ElemType x;
int k;
scanf("%d",&x); //输入要查找的元素
ListCreate(L,50);
k=BinSearch(L,x);
printf("%d", k);
return 0;
}
```
答案:
第1空:L.elem=(ElemType *)malloc((n+1)*sizeof(ElemType))
第2空:mid=(low+high)/2
第3空:high=mid-1
```c++
#include
#include
#include
#define OK 1
#define OVERFLOW -1
typedef int Status;
typedef int ElemType;
typedef struct SqList{
ElemType *elem; //存放元素的数组。从1号开始存放元素
int length; //有效元素的个数
}SqList;
//下面的函数用于创建一个有序顺序表,n代表元素个数。
Status ListCreate(SqList &L, int n){
@@[L.elem=(ElemType *)malloc((n+1)*sizeof(ElemType))](3); //补充代码开辟一个长度为n+1的数组
if(!L.elem)exit(OVERFLOW);
L.length=n ;
for(int i=1;i<=L.length;++i)
L.elem[i]= 2*i ;
return OK;
}
//下面的函数用于折半查找。查找成功时返回位序(从1开始),查找失败则返回0。
int BinSearch(SqList &L, ElemType x){
int low, high, mid;
low=1; high=L.length;
while(low <= high ){
@@[mid=(low+high)/2](3);
if(x==L.elem[mid])
return mid;
else if(x
else
low=mid+1;
}
return 0;
}
int main()
{
SqList L;
ElemType x;
int k;
scanf("%d",&x); //输入要查找的元素
ListCreate(L,50);
k=BinSearch(L,x);
printf("%d", k);
return 0;
}
```
答案:
第1空:L.elem=(ElemType *)malloc((n+1)*sizeof(ElemType))
第2空:mid=(low+high)/2
第3空:high=mid-1