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

转载于:https://www.cnblogs.com/CCCrunner/p/6444613.html

相关资源：JAVA上百实例源码以及开源项目