顺序表应用6：有序顺序表查询

顺序表应用6：有序顺序表查询

Time Limit: 7MS Memory Limit: 700KB

Submit Statistic

Problem Description

顺序表内按照由小到大的次序存放着n个互不相同的整数（1<=n<=20000)，任意输入一个整数，判断该整数在顺序表中是否存在。如果在顺序表中存在该整数，输出其在表中的序号；否则输出“No Found!"。

Input

第一行输入整数n，表示顺序表的元素个数；
第二行依次输入n个各不相同的有序整数，代表表里的元素；
第三行输入整数t，代表要查询的次数；
第四行依次输入t个整数，代表每次要查询的数值。

Output

输出t行，代表t次查询的结果，如果找到在本行输出该元素在表中的位置，否则本行输出No Found!

Example Input

10
1 22 33 55 63 70 74 79 80 87
4
55 10 2 87

Example Output

4
No Found!
No Found!
10

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#define LISTINCREASMENT 20012                 /*每次分配元素的个数*/
#define  LISTSIZE 20012                         /*顺序存储的最大个数*/
#define  OVERFLOW -1
#define  OK 1
int n,m;
using namespace std;
typedef int ElemType;


typedef struct                                   /*顺序表元素的的定义*/
{
    ElemType * elem;
    int length;
    int listsize;
} Sqlist;


int SqInitial(Sqlist &L)                           /*初始化线性表*/
{
    L.elem=(ElemType *) malloc (LISTSIZE*sizeof(ElemType));
    if (! L.elem)  exit(OVERFLOW); //存储分配失败
    L.length=0;
    L.listsize=LISTSIZE;
    return OK;
}


int ListInsert(Sqlist &L,int i,ElemType e)            /*插入元素*/
{
    if(i<1|| i > L.length+1) exit(-1);
    if(L.length>=L.listsize)
    {
        ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREASMENT)
                                            *sizeof(ElemType));
        if(!newbase)   return  OVERFLOW;// 当前存储空间已满


L.elem=newbase;
        L.listsize+=LISTINCREASMENT;         /*表的容量不足分配内存*/
    }
    ElemType *  q=&(L.elem[i-1]);
    ElemType *  p;
    for(p=&(L.elem[L.length-1]); p>=q; --p)
        *(p+1)=*p;
    *q=e;
    ++L.length;
    return OK;


}
void display(Sqlist &L)
{
    int i;
    for(i=0;i<L.length-1;i++)
    {
        cout<<L.elem[i]<<" ";
    }
     cout<<L.elem[i]<<endl;
}




int query(Sqlist &L,int i,int j,int key)
{
    int mid;
    while(i<=j)
    {
        mid = (j+i)/2;
        /*cout<<"L.elem[mid]=="<<L.elem[mid]<<endl;
        cout<<"L.elem[i]=="<<L.elem[i]<<endl;
        cout<<"L.elem[j]=="<<L.elem[j]<<endl;
        */
        if(L.elem[mid]==key)
            return mid+1;
        if(L.elem[mid]<key)
        {
            i = mid+1;
        }
        if(L.elem[mid]>key)
        {
            j = mid-1;
        }
    }
    return -1;
}




int main()
{
    Sqlist L,L1,L2;
    int t =1 ,d;
    cin>>n;
    SqInitial(L);
    //printf("构建长度为len的顺序表。\n");
    for(t=1; t<=n; t++)                         /*构建长度为n的顺序表*/
    {
        //printf("Please input the %dth list elem:",t);
        scanf("%d",&d);
        ListInsert(L,t,d);
    }
    cin>>m;
    while(m--)
    {
        scanf("%d",&t);
        d = query(L,0,n-1,t);
        if(d==-1)
            cout<<"No Found!"<<endl;
        else
            cout<<d<<endl;


    }






return 0;
}