顺序表应用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

#include

#include

#include

#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
    {

        cout<
    }

     cout<
}









int query(Sqlist &L,int i,int j,int key)

{

    int mid;

    while(i<=j)

    {

        mid = (j+i)/2;

        /*cout<<"L.elem[mid]=="<
        cout<<"L.elem[i]=="<
        cout<<"L.elem[j]=="<
        */

        if(L.elem[mid]==key)

            return mid+1;

        if(L.elem[mid]
        {

            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的顺序表。 ");

    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!"<
        else

            cout<




    }













return 0;

}