bookfind.h

一个海量图书查询系统

#include "define.h"

class BookFind
{
private:
	book data;              //当前处理的图书记录
	int success;           //折半查找标志
    long *HashData;    //申请HASH表的存储空间
	indexISBN *IndexData;  //保存ISBN索引表
public:
	BookFind(void);
	~BookFind(void);
	book operator=(book c);  //运算符重载
    void DisplayData(void) const;  //显示当前处理的图书记录
	int SeqFind(char ISBN[11]);      //顺序查询与输入的ISBN相同的所有ISBN（随机产生的ISBN可能相同）,并显示。
	int IndexSeqFind(char ISBN[11]);  //索引顺序查询与输入的ISBN相同的所有ISBN（随机产生的ISBN可能相同）,并显示。
    long BiSearch(char ISBN[11],long start,long end);     //在索引表中折半查找ISBN号，成功则success=1，返回其位置(在索引表中的相对位置)
	int IndexBinFind(char ISBN[11]);  //索引折半查询与输入的ISBN相同的所有ISBN（随机产生的ISBN可能相同）,并显示。
	int HashIndexBinFind(char ISBN[11]);  //哈希索引折半查询与输入的ISBN相同的所有ISBN（随机产生的ISBN可能相同）,并显示。
 };

book BookFind::operator=(book c)
{
	book x;
    strcpy(x.ISBN,c.ISBN);
	x.category=c.category;
	strcpy(x.bookname,c.bookname);
	strcpy(x.authors,c.authors);
	return x;
}

BookFind::BookFind(void)  //构造函数
{  
	success=0;
	IndexData=new indexISBN[RECORDNUMBER];    //保存ISBN索引表
	if(IndexData==NULL) { cout<<endl<<" 索引表内存申请失败! "<<endl;  exit(0); }
	ifstream indexfile;   //定义输入的索引文件
    indexfile.open("indexdata.dat",ios::nocreate|ios::binary);
	if(!indexfile) 
	{
       cout<<endl<<"  !! ERROR:Cannot open file 'indexdata.dat'. "<<endl;
	   exit(0);
	} 
    long size=0;
	indexISBN tempINDEX;   //临时变量
	while(indexfile.good()&&size<RECORDNUMBER)     //读索引数据文件信息
	{
		indexfile.read((char *)&tempINDEX,sizeof(struct indexISBN));
        IndexData[size++]=tempINDEX;
	}
    indexfile.close();
    HashData=new long[HASHSIZE];    //申请HASH表的存储空间
	if(HashData==NULL) { cout<<endl<<" HASH表内存申请失败! "<<endl;  exit(0); }
    ifstream hashfile;
	hashfile.open("hashdata.dat",ios::binary);      //打开HASH表文件hashdata.dat
	if(!hashfile)
	{
       cout<<endl<<"  !! ERROR:Cannot open file: hashdata.dat  "<<endl;
       exit(0);
	} 
 	int hashnum=0;
	while(hashfile.good()&&hashnum<HASHSIZE)     //将HASH表读入内存
	{
	    hashfile.read((char *)&HashData[hashnum],sizeof(long));    
        hashnum=hashnum+1;
	}
    hashfile.close();
}

BookFind::~BookFind(void)   //统一保存文件头信息
{ 
     delete []IndexData;
	 delete []HashData;
}

void BookFind::DisplayData(void) const
{
	cout<<data.ISBN<<' '<<data.category<<' '<<data.bookname<<' '<<data.authors<<endl;
}

int BookFind::SeqFind(char ISBN[11])
{   //寻找元素序列号为ISBN的所有图书记录,因为可能重复，故需要全程搜索
    int snum=0;
    ifstream myinfile;
	myinfile.open("book.dat",ios::binary);
	if(myinfile)
	{
	    long currptr=0;      //图书记录的起始下标
        cout<<endl<<"顺序查询ISBN为: "<<ISBN<<" 的图书的，请稍候......"<<endl;
        DWORD dwstart,dwend;   
        dwstart=GetTickCount();    //记录开始时间
        while(myinfile.good()&&currptr<RECORDNUMBER)
		{   
			myinfile.read((char *)&data,sizeof(book));
			if(strcmp(data.ISBN,ISBN)==0) { snum++;  cout<<"第"<<snum<<"条记录："; DisplayData();  }   //找到并显示
			currptr++;
		}
        myinfile.close();
        dwend=GetTickCount();   //记录结束时间
        cout<<"共耗时约:  "<<dwend-dwstart<<" 毫秒。"<<endl;
        cout<<"共找到 "<<snum<<" 条图书记录!"<<endl;
	}
	else
	{
       cout<<endl<<"  !! ERROR:Cannot open file 'book.dat'. "<<endl;  exit(0); 
	} 
    return snum;      
}

int BookFind::IndexSeqFind(char ISBN[11])
{   
    int snum=0;
//在索引表中顺序查询
    ifstream myinfile;
	myinfile.open("book.dat",ios::binary);
	if(!myinfile) {cout<<endl<<"  !! ERROR:Cannot open file 'book.dat'. "<<endl;  exit(0);  };
    cout<<endl<<"索引顺序查询ISBN为: "<<ISBN<<" 的图书的，请稍候......"<<endl;
    DWORD dwstart,dwend;   
    dwstart=GetTickCount();    //记录开始时间
    long size=0;
	while(size<RECORDNUMBER)
	{
		if(strcmp(IndexData[size].ISBN,ISBN)==0)    //在索引表中存在
		{
           myinfile.seekg(IndexData[size].serialnumber*sizeof(struct book));      //定位数据在book中的位置
           myinfile.read((char *)&data,sizeof(struct book));            //读入数据
           snum++; 
		   cout<<"第"<<snum<<"条记录："; DisplayData();    //找到并显示
		}
		if(strcmp(IndexData[size].ISBN,ISBN)>0) break;
		size++;
	}
    myinfile.close();
    dwend=GetTickCount();   //记录结束时间
    cout<<"共耗时约:  "<<dwend-dwstart<<" 毫秒。"<<endl;
    cout<<"共找到 "<<snum<<" 条图书记录!"<<endl;
    return snum;      
}

long BookFind::BiSearch(char ISBN[11],long start,long end)  
 //折半查找ISBN号，成功则success=1，返回其位置(在索引表中的相对位置)。
{  
    success=0;
	long low=start, high=end-1;
    long mid;  
    while(low<=high)
    {
	   mid=(low+high)/2;
	   if(strcmp(IndexData[mid].ISBN,ISBN)==0) { success=1;  return mid; }
	    else if(strcmp(IndexData[mid].ISBN,ISBN)<0) low=mid+1;
		  else high=mid-1;
    }
    return high;
}

int BookFind::IndexBinFind(char ISBN[11])
{   //在索引表中折半查询
    long Findnumber=0;      //找到的图书计数
    ifstream mydatafile;
    mydatafile.open("book.dat",ios::binary);  //打开数据源文件
    if(!mydatafile)
    {
      cout<<endl<<"  !! ERROR:Cannot open file 'book.dat'. "<<endl;
      exit(0);
    }
    cout<<endl<<"索引折半查询ISBN为: "<<ISBN<<" 的图书的，请稍候......"<<endl;
    DWORD dwstart,dwend;   
    dwstart=GetTickCount();    //记录开始时间
    long Fpos=BiSearch(ISBN,0,RECORDNUMBER);    //Fpos为在索引表中的相对位置
	if(success==1)
	{
 	   long Fup=Fpos-1;
	   long Fdown=Fpos+1;      //在找到点Fpos分别向上和向下查询是否有相同的ISBN
	   if(IndexData[Fpos].serialnumber>-1&&IndexData[Fpos].serialnumber<RECORDNUMBER)    //保证数据的正确性
	   {
        mydatafile.seekg(IndexData[Fpos].serialnumber*sizeof(struct book));      //定位数据在book中的位置
        mydatafile.read((char *)&data,sizeof(struct book));       //读入数据
  		cout<<"第"<<Findnumber<<"条记录："; DisplayData();    //找到并显示  
        Findnumber=Findnumber+1;                             //找到的书计数加1
	   }
      while(Fup>=0&&strcmp(IndexData[Fup].ISBN,ISBN)==0)    //向上查询
	  {
	   if(IndexData[Fup].serialnumber>-1&&IndexData[Fup].serialnumber<RECORDNUMBER)    //保证数据的正确性
	   {
        mydatafile.seekg(IndexData[Fpos].serialnumber*sizeof(struct book));      //定位数据在book中的位置
        mydatafile.read((char *)&data,sizeof(struct book));       //读入数据
  		cout<<"第"<<Findnumber<<"条记录："; DisplayData();    //找到并显示  
        Findnumber=Findnumber+1;                             //找到的书计数加1
	   }
       Fup=Fup-1;             //继续向上
	  }
      while(Fdown<RECORDNUMBER&&strcmp(IndexData[Fdown].ISBN,ISBN)==0)    //向下查询
	  {
	   if(IndexData[Fdown].serialnumber>-1&&IndexData[Fdown].serialnumber<RECORDNUMBER)    //保证数据的正确性
	   {
        mydatafile.seekg(IndexData[Fpos].serialnumber*sizeof(struct book));      //定位数据在book中的位置
        mydatafile.read((char *)&data,sizeof(struct book));       //读入数据
  		cout<<"第"<<Findnumber<<"条记录："; DisplayData();    //找到并显示  
        Findnumber=Findnumber+1;                             //找到的书计数加1
	   }
       Fdown=Fdown+1;             //继续向下
	  }
	}
    mydatafile.close();
    dwend=GetTickCount();   //记录结束时间
    cout<<"共耗时约:  "<<dwend-dwstart<<" 毫秒。"<<endl;
    cout<<"共找到 "<<Findnumber<<" 条图书记录!"<<endl;
    return Findnumber;      
}

int BookFind::HashIndexBinFind(char ISBN[11])
{   //在哈希表查询和索引表中折半查询
    long Findnumber=0;      //找到的图书计数
    ifstream mydatafile;
    mydatafile.open("book.dat",ios::binary);  //打开数据源文件
    if(!mydatafile)
    {
      cout<<endl<<"  !! ERROR:Cannot open file 'book.dat'. "<<endl;
      exit(0);
    }
    cout<<endl<<"哈希索引折半查询ISBN为: "<<ISBN<<" 的图书的，请稍候......"<<endl;
    DWORD dwstart,dwend;   
    dwstart=GetTickCount();    //记录开始时间
    char temp[5];
	int j;
	int hashvalue;
	for(j=0;j<=3;j++)  temp[j]=ISBN[j];     //取ISBN中的第0-3共四位数据
    temp[4]='\0';
	hashvalue=atoi(temp);    //将字符串转换为记录对应的HASH数值
    long Fpos=BiSearch(ISBN,HashData[hashvalue],HashData[hashvalue+1]);    //Fpos为在索引表中的相对位置
	if(success==1)
	{
 	   long Fup=Fpos-1;
	   long Fdown=Fpos+1;      //在找到点Fpos分别向上和向下查询是否有相同的ISBN
	   if(IndexData[Fpos].serialnumber>-1&&IndexData[Fpos].serialnumber<RECORDNUMBER)    //保证数据的正确性
	   {
        mydatafile.seekg(IndexData[Fpos].serialnumber*sizeof(struct book));      //定位数据在book中的位置
        mydatafile.read((char *)&data,sizeof(struct book));       //读入数据
  		cout<<"第"<<Findnumber<<"条记录："; DisplayData();    //找到并显示  
        Findnumber=Findnumber+1;                             //找到的书计数加1
	   }
      while(Fup>=0&&strcmp(IndexData[Fup].ISBN,ISBN)==0)    //向上查询
	  {
	   if(IndexData[Fup].serialnumber>-1&&IndexData[Fup].serialnumber<RECORDNUMBER)    //保证数据的正确性
	   {
        mydatafile.seekg(IndexData[Fpos].serialnumber*sizeof(struct book));      //定位数据在book中的位置
        mydatafile.read((char *)&data,sizeof(struct book));       //读入数据
  		cout<<"第"<<Findnumber<<"条记录："; DisplayData();    //找到并显示  
        Findnumber=Findnumber+1;                             //找到的书计数加1
	   }
       Fup=Fup-1;             //继续向上
	  }
      while(Fdown<RECORDNUMBER&&strcmp(IndexData[Fdown].ISBN,ISBN)==0)    //向下查询
	  {
	   if(IndexData[Fdown].serialnumber>-1&&IndexData[Fdown].serialnumber<RECORDNUMBER)    //保证数据的正确性
	   {
        mydatafile.seekg(IndexData[Fpos].serialnumber*sizeof(struct book));      //定位数据在book中的位置
        mydatafile.read((char *)&data,sizeof(struct book));       //读入数据
  		cout<<"第"<<Findnumber<<"条记录："; DisplayData();    //找到并显示  
        Findnumber=Findnumber+1;                             //找到的书计数加1
	   }
       Fdown=Fdown+1;             //继续向下
	  }
	}
    mydatafile.close();
    dwend=GetTickCount();   //记录结束时间
    cout<<"共耗时约:  "<<dwend-dwstart<<" 毫秒。"<<endl;
    cout<<"共找到 "<<Findnumber<<" 条图书记录!"<<endl;
    return Findnumber;      
}