题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。
输入
第一行输入n，表示主表有n个数据 第二行输入n个数据，都是正整数，用空格隔开 第三行输入k，表示主表划分为k个块，k也是索引表的长度 第四行输入k个数据，表示索引表中每个块的最大值 第五行输入t，表示有t个要查找的数值 第六行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error
输入样例1
18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 3 22 48 86 6 13 5 48 40 53 90
输出样例1
3-4 error 12-8 error 18-9 error
思路分析
这道题还是有点意思的。
顺序索引查找。
首先建立索引表，即两个数组，或者一个结构体数组，用来装关键字，即一个小分块里面最大的数值，还要装关键字对应的小分块在队列里面的起始位置。
关键字由题目给出。
关键字所对应的起始位置怎么求？
第一个起始位置和最后一个起始位置是固定的，即队列的起始位置和队列的终止位置。
其他的关键字对应的起始位置的求法：
顺序遍历队列，找到比前一个关键字大的数值，该数值对应的位置就是次关键字对应的起始位置。
然后到了查找部分：
其实就是部分顺序查找，先在索引表里面查找出在哪个子块里面，然后到子块里面顺序查找。
AC代码
代码语言：javascript复制#include <iostream>
using namespace std;
int main() {
int n,k,t;
cin>>n;
int a[n];
for(int i=0;i<n;i )
cin>>a[i];
cin>>k;
int max_key[k],address[k 1];
address[0]=0;
address[k]=n-1;
for(int i=0;i<k;i )
cin>>max_key[i];
for(int i=1;i<k;i )
for(int j=0;j<n;j ){
if(a[j]>max_key[i-1]){
address[i]=j;
break;
}
}
int low,high,target;
cin>>t;
while(t--){
int count=0;
cin>>target;
for(int i=0;i<k;i ){
count ;
if(target<=max_key[i]){
low=address[i];
high=address[i 1];
break;
}
}
for(;low<=high;low ){
count ;
if(a[low]==target){
cout<<low 1<<'-'<<count<<endl;
break;
}
}
if(low>high)
cout<<"error"<<endl;
}
return 0;
}
