fenkuaichazhao.rar_K._分块查找_编写分块查找

#include"stdio.h" #define MAX 256 typedef struct{ int key; int link; }IdxType; int dis_max(int a[],int start,int end){ int i=0,max=0; for(i=start;i<=end;i++){ if(a[i]>max) max=a[i]; } return max; } int IdxSearch(IdxType I[],int m,int a[],int n,int k){ int low=0,high=m-1,mid,i; int b=n/m; while(low<=high){ mid=(low+high)/2; if(I[mid].key>=k) high=mid-1; else low=mid+1; } i=I[high+1].link; while(i<=I[high+1].link+b-1&&a[i]!=k) i++; if(i<=I[high+1].link+b-1) return i; else return -1; } int main(){ int n,i,a[MAX],t,l,k,m; IdxType IDX[MAX]; printf("请输入主表的元素的个数\n"); scanf("%d",&n); if(n>256||n<=0) { printf("输入有误\n"); return 0; } printf("请输入主表的元素\n"); for(i=0;i<n;i++){ scanf("%d",&t); a[i]=t;//输入主表的元素 } printf("请输入每块的记录数\n"); scanf("%d",&l); k=n/l; for(i=0;i<k;i++){ IDX[i].key=dis_max(a,4*i,4*i+l-1); IDX[i].link=4*i; } printf("请输入要查询的次数\n"); scanf("%d",&m); for(i=0;i<m;i++){ printf("请输入要查询的元素\n"); scanf("%d",&t); if(IdxSearch(IDX,l,a,n,t)==-1) printf("查找失败\n"); else printf("查找成功\n"); } return 1; }