qq_54509887
2021-11-19 19:57
采纳率: 66.7%
浏览 89

数据结构--折半查找(oj题)

题目

Input

输入的第一行包含2个正整数n和k,分别表示共有n个整数和k次查询。其中n不超过1000,k同样不超过1000。
第二行包含n个用空格隔开的正整数,表示n个有序的整数。输入保证这n个整数是从小到大递增的。
第三行包含k个用空格隔开的正整数,表示k次查询的目标。

Output

只有1行,包含k个整数,分别表示每一次的查询结果。如果在查询中找到了对应的整数,则输出其相应的位置,否则输出-1。
请在每个整数后输出一个空格,并请注意行尾输出换行。

Sample Input Copy

8 3
1 3 5 7 8 9 10 15
9 2 5

Sample Output Copy

5 -1 2

出现问题:提交oj上总是显示 Compile Error 0
怎么解决?

我写的代码

#include<stdio.h>
#include<malloc.h>

//顺序存储结构
typedef struct{
    int key;
}ElemType;

typedef struct{
    ElemType *elem; //0 不存元素 
    int length;
}SSTable;

//创建顺序静态表
void CreateSST(SSTable &ST,int n){
    int i;
    ST.elem =(ElemType*)malloc(sizeof(ElemType)*(n+1));
    ST.length=n;
    for(i=1;i<=n;i++){
        scanf("%d",&ST.elem [i].key);
    
        getchar();
    } 
}  

//折半查找
int Search_Bin(SSTable &ST,int key){
    int low,mid,high;
    low=1;
    high=ST.length ;
    while(low<=high){
        mid=(low+high)/2;
        if(key==ST.elem [mid].key) return mid;
        else if(key>ST.elem [mid].key) low=mid+1;
        else if(key<ST.elem [mid].key) high=mid-1;
        else return -1;
    }
    return 0;
} 

int main(){
    int j,n,k;
    while(scanf("%d%d",&n,&k)!=EOF&&n<=1000&&k<=1000){
    SSTable ST,DT;
    CreateSST(ST,n);
    CreateSST(DT,k);
    for(j=1;j<=k;j++){
        int t=Search_Bin(ST,DT.elem [j].key);
        printf("%d ",t-1);
     
    }
    printf("\n");

    }
    return 0;
}


1条回答 默认 最新

相关推荐 更多相似问题