分块查找算法实现

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include<algorithm>
using namespace std;
/*
分块查找是折半查找和顺序查找的一种改进方法，
分块查找由于只要求索引表是有序的，对块内节点没有排序要求，
因此特别适合于节点动态变化的情况，其核心有二索引表，二是分块处理。分块查找要求把一个大的线性表分解成若干块，
每块中的节点可以任意存放，但块与块之间必须排序。
假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实
际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。
此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；
然后，在相应的块中采用顺序查找，即可找到对应的节点。
*/ 
struct index
{int key;//一个最大值分块 int start;//一个起始位置 
}newindex[3];
int cmp(const void* a,const void* b)
{return (*(struct index*)a).key>(*(struct index*)b).key?1:-1;
}
void display_table(struct index newindex[])
{for(int i=0;i<3;i++){cout<<"分块最大值为:"<<newindex[i].key<<" 分块起始位置为:"<<newindex[i].start<<endl; }
}
int block_search(int a[],struct index newindex[],int key)
{int i=0;//首先确定search data在哪一块 while(i<3&&newindex[i].key<key) i++;cout<<"搜索值"<<key<<"属于第"<<i<<"个模块!"<<endl;//三个模块内找不到就一定不在a中 if(i>=3) return -1; int j=newindex[i].start;int pos;for(int k=j;k<j+6;k++){//在模块内已经找到 if(key==a[k]) return k;}//循环内没找到就是没有了 return -1; }
int main()
{int a[18]={33,42,44,38,24,48, 22,12,13,8,9,20, 60,58,74,49,86,53};//划分成3块,每一块6个int j=-1; for(int i=0;i<3;i++){newindex[i].start=j+1;//cout<<newindex[i].start<<endl;//cout<<j<<endl;j+=6;//将每一个部分的最大值更新为key for(int k=newindex[i].start;k<=j;k++){if(a[k]>newindex[i].key) newindex[i].key=a[k];}} //display_table(newindex);//对于结构体进行排序 qsort(newindex,3,sizeof(newindex[0]),cmp);//排序后的更新表结果 display_table(newindex);int search_data=49;int k=block_search(a,newindex,search_data);if(k<0) cout<<"分块搜索算法没有找到元素！"<<endl;else  cout<<"分块搜索算法已经找到元素"<<search_data<<" 它位于:"<<k<<endl;//cout<<k<<endl; return 0;
}