题目描述

/已知有序顺序表类LinearSearch类，实现折半查找。部分代码如下，勿改动，
请补充Bin_Search和DispList函数。
/

include
using namespace std;

const int MaxSize=100; //顺序表的最大长度
//有序表类
class LinearSearch{
public:
LinearSearch(){n=0;}
~LinearSearch(){}
void Insert(int x);//有序表的插入，使序列仍有序
void DispList(); //输出表
int Bin_Search(int key); //查找成功，函数返回key所在数组下标（位置），否则查找失败，返回0
private:
int r[MaxSize+1]; //存储元素(r[1]~r[n]存储元素)
int n; //顺序表实际长度
};

//在有序表中插入元素x，使序列仍有序
void LinearSearch::Insert(int x){
int i;
if (n>=MaxSize) //表满不能插入
throw “Overflow”;
r[0]=x;
for(i=n;r[i]>x;i—)
r[i+1]=r[i];//将i位置元素后移
r[i+1]=x; //在位置i+1插入元素x
n++; //线性表长度增1
}

//请在下面补充实现相关算法的C++函数实现

int main(){
LinearSearch A; //空表A
int x,key;
//利用插入函数创建有序表，以0结束
while(1){
cin>>x;
if(!x)break;
try{
A.Insert(x);
}
catch(const char *wrong){
cout< }
}
A.DispList();
int pos;
cin>>key;
pos=A.Bin_Search(key);
if(!pos)//查找失败
cout<<”Find “< else cout<<”Find “< return 0;
}

输入

输入输出请见样例，注意：要测试查找成功、失败两种情况！

输出

样例输入

43 53 1 25 2 426 324 345 423 34 0 25

样例输出

Data:1 2 25 34 43 53 324 345 423 426 Find 25 success,position:3

提示

来源

提交

import java.util.Scanner;
class LinearSearch{
    int n = 0;
    int[] r;
    int MaxSize = 100;
    public LinearSearch() {
        r = new int[MaxSize];
    }
    void insert(int x) throws Exception {
        int i;
        if (n>MaxSize)         //表满不能插入
            throw new Exception("Overflow");
        r[0]=x;
        for(i=n;r[i]>x;i--)
            r[i+1]=r[i];//将i位置元素后移
        r[i+1]=x;//在位置i+1插入元素x
        n++;//线性表长度增1
    }
    void DispList(){
        System.out.print("Data:");
        for (int i = 1; i <= n; i++) {
            System.out.print(r[i]+" ");
        }
        System.out.println();
    }
    int Bin_Search(int key){
        if(n>0){
            int low = 0,high = n;
            while(low<=high){
                int mid = (low+high)/2;
                if(r[mid]==key){
                    return mid;
                }else if(r[mid]>key){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}
public class Main {
    public static void main(String[] args) throws Exception {
        LinearSearch linearSearch = new LinearSearch();
        Scanner scanner = new Scanner(System.in);
        int key;
        while(true){
            int x = scanner.nextInt();
            if(x == 0)break;
            linearSearch.insert(x);
        }
        key = scanner.nextInt();
        linearSearch.DispList();
        int pos = linearSearch.Bin_Search(key);
        if(pos!=-1){
            System.out.println("Find "+key+" success,position:"+pos);
        }else{
            System.out.println("Find "+key+" failure");
        }
    }
}