分块查找.txt

数据查找课程设计

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#include<iomanip.h>
#define MaxSize 30 //MaxSize为事先定义的整型常量，它要大于等于主表中元素的个数n
#define ILMSize 10 //ILMSize为事先定义的整型常量，它要大于等于索引项数m
typedef int IndexKeyType;
typedef int KeyType;
class ElemType
{
public:
    int key;
};
class IndexItem
{
public:
    IndexKeyType index;    //IndexKeyType为事先定义的索引值类型
    int start;      //子表中第一个元素所在的下标位置
    int length;     //子表的长度域
};
typedef IndexItem indexlist[ILMSize];     //ILMSize为事先定义的整型常量，它要大于等于索引项数m
typedef ElemType mainlist[MaxSize];    //MaxSize为事先定义的整型常量，它要大于等于主表中元素的个数n
int Blocksch(mainlist A,indexlist B,int m,KeyType k)
    //利用主表A和大小为m的索引表B分块查找关键字为k的记录
{
    int i,j;
    //在索引表中顺序查找关键字为k所对应的索引项
    for(i=0;i<m;i++)
        if(k<=B[i].index)
            break;
    //若i等于m,则表明查找失败，返回-1
    if(i==m)
        return -1;
    //在已经查找到的第i个子表中顺序查找关键字为k的记录
    j=B[i].start;
    while(j<B[i].start+B[i].length)
        if(k==A[j].key)
            break;
        else
            j++;
    //若查找成功则返回元素的下标值，否则返回-1
        if(j<B[i].start+B[i].length)
            return j;
        else
            return -1;

}
void main()
{
	srand(int(time(0)));
    int i=0,k,j=5;
	int mlnum=20;   //主表中元素的个数
    indexlist B;
    mainlist A;
    cout<<"输入主表中的(子表中元素要满足块间有序:我们这里设升序,块内无序)"<<mlnum<<"个元素"<<endl;
    for(i=0;i<mlnum;i++)
        A[i].key=rand()%50;   //随机产生20个数据
    for(i=1;i<mlnum;i++)   //对A数组进行排序
	{ 	
		int flag=0;
		int t;
		for(int j=1;j<mlnum;j++)
			if(A[j-1].key>A[j].key)
			{  
				t=A[j-1].key;
				A[j-1].key=A[j].key;
				A[j].key=t;
				flag=1;
			}
			if(!flag) 
				break;
	} 
	cout<<"处理后的A数组为:"<<endl;
	for(i=0;i<mlnum;i++)
	{
		cout<<A[i].key<<setw(4);
		if((i+1)%5==0)
			cout<<endl;
	}
    cout<<"程序自动生成4个索引项!"<<endl;
    for(i=0;i<4;i++)
	{
		B[i].index=A[j-1].key;
		B[i].start=j-5;
		B[i].length=5;
		j=j+5;
	}	
    cout<<"输入要查找的数:"<<endl;
    cin>>k;
    int findindex=Blocksch(A,B,4,k);
    if(findindex!=-1)
        cout<<"找到,下标为:"<<findindex+1<<"\t值为:"<<A[findindex].key<<endl;
    else
        cout<<"没找到"<<endl;

    
}