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