//程序隨機生成100萬條圖書記錄并形成索引表和哈希表
#include "define.h"

char getintchar()
{
	char temp=48+rand()%10;		//隨機數為'0'-'9'
	return temp;
}

char getrandchar()
{
	char temp=97+rand()%26;		//隨機數為'a'-'z'
	return temp;
}

void getISBN(char ISBN[11])
{
	for(int i=0;i<10;i++) ISBN[i]=getintchar();   //產生隨機數ISBN
	ISBN[10]=NULL;
} 

char getcategory()   //產生隨機數category
{
	return getintchar(); 
}

void getbookname(char bkname[61])    //產生隨機數bookname
{
	for(int i=0;i<60;i++) bkname[i]=getrandchar();  
	bkname[60]=NULL;
}

void getauthors(char aut[11])    //產生隨機數author
{
	for(int i=0;i<10;i++) aut[i]=getrandchar();  
	aut[10]=NULL;
}

//索引表信息交換
void exchange(indexISBN &x,indexISBN &y)  
{
	indexISBN temp;
    temp.serialnumber=x.serialnumber; strcpy(temp.ISBN,x.ISBN);  
    x.serialnumber=y.serialnumber; strcpy(x.ISBN,y.ISBN); 
    y.serialnumber=temp.serialnumber; strcpy(y.ISBN,temp.ISBN); 
}

//快速排序
void QuickSort(indexISBN a[],long low,long high)
{
	long i=low,j=high;
	indexISBN temp;
	temp.serialnumber=a[low].serialnumber; strcpy(temp.ISBN,a[low].ISBN);
	while(i<j)
	{
		while(i<j&&strcmp(temp.ISBN,a[j].ISBN)<=0) j--;
		if(i<j)
		{
	        a[i].serialnumber=a[j].serialnumber; strcpy(a[i].ISBN,a[j].ISBN); 			
			i++;
		}
        while(i<j&&strcmp(a[i].ISBN,temp.ISBN)<0) i++;
		if(i<j)
		{
	        a[j].serialnumber=a[i].serialnumber; strcpy(a[j].ISBN,a[i].ISBN);
			j--;
		}
	}
	a[i].serialnumber=temp.serialnumber; strcpy(a[i].ISBN,temp.ISBN); 
	if(low<i) QuickSort(a,low,i-1);
	if(i<high) QuickSort(a,j+1,high);
}

void Createindex(indexISBN a[])   //產生索引表
{
	long h=0;
    ofstream myoutfile;
	myoutfile.open("indexdata.dat",ios::trunc|ios::binary);     //索引數據記錄(已排序)存儲文件
	if(!myoutfile)
	{
       cout<<endl<<"  !! ERROR: can not create file: indexdata.dat"<<endl;
	   exit(0);
	} 
    QuickSort(a,0,RECORDNUMBER-1);    //快速排序
//保存排序后的索引數據文件
 	for(h=0;h<RECORDNUMBER;h++) 
	{
		myoutfile.write((char *)&a[h],sizeof(struct indexISBN));  
		if(h<10||h>RECORDNUMBER-10) //數據測試數據，頭10條記錄和后10條記錄
		{
	      cout<<a[h].ISBN<<" ";     
	      cout<<a[h].serialnumber<<endl;
		}
	}
	myoutfile.close();
}

void Createhash(indexISBN a[])   //產生哈希表
{
    long *hashtable=new long[HASHSIZE];    //申請HASH表的存儲空間
	if(hashtable==NULL) { cout<<endl<<" 內存申請失敗! "<<endl;  exit(0); }
//  indexISBN indexdata;    //保存讀入的一條索引記錄
    ofstream myoutfile;
	myoutfile.open("hashdata.dat",ios::trunc|ios::binary);   //HASH表的數據記錄存儲文件
	if(!myoutfile)
	{
       cout<<endl<<"  !! ERROR: can not create file: hashdata.dat "<<endl;
	   exit(0);
	} 
    char temp[5];
    for(int i=0;i<HASHSIZE;i++) hashtable[i]=-1;      //hash表賦初值
	long k=0;
	int j;
	int hashvalue;
	while(k<RECORDNUMBER)  //處理數據，建立HASH表
	{
		for(j=0;j<=3;j++)  temp[j]=a[k].ISBN[j];     //取ISBN中的第0-3共四位數據
    	temp[4]='\0';
	    hashvalue=atoi(temp);    //將字符串轉換為記錄對應的HASH數值
		if(hashtable[hashvalue]==-1) hashtable[hashvalue]=k;   //記錄在索引表中的相對位置
		k++;
	} 
	hashtable[HASHSIZE-1]=k; 
//保存HASH表的數據文件
	int h;
 	for(h=0;h<HASHSIZE;h++) myoutfile.write((char *)&hashtable[h],sizeof(long));  
	myoutfile.close();
//輸出前10個數據
	for(h=0;h<10;h++) cout<<"position: "<<h<<"   "<<hashtable[h]<<endl; 
//輸出后10個數據
	for(h=0;h<10;h++) cout<<"position: "<<HASHSIZE-1-h<<"   "<<hashtable[HASHSIZE-1-h]<<endl; 
	delete []hashtable;     //釋放申請的存儲空間
}


int main(int argc, char* argv[])
{
	ofstream outfile;     //定義輸出數據的記錄文件
	outfile.open("book.dat",ios::trunc|ios::binary);   //以二進制保存數據
	if(!outfile) { cout<<endl<<"  !! ERROR: can not create file: book.dat "<<endl;  exit(0);  } 
    ofstream dataout;     
	dataout.open("datatest.txt",ios::trunc);  //以文本保存數據測試數據，頭10條記錄和后10條記錄
	if(!dataout) {  cout<<endl<<"  !! ERROR: can not create headfile: datatest.txt"<<endl;  exit(0); }  
	indexISBN *storeISBN=new indexISBN[RECORDNUMBER];    //保存ISBN號
	if(storeISBN==NULL) { cout<<endl<<" 內存申請失敗! "<<endl;  exit(0); }
	book BUFF;   //保存一條完整的圖書信息
    DWORD dwstart,dwend;   
    dwstart=GetTickCount();    //記錄開始時間
	srand((unsigned)time(NULL));   //srand()函數產生一個以當前時間開始的隨機種子
	cout<<"正在處理數據，請稍候......"<<endl;
    long size=0;
	while(size<RECORDNUMBER) //共產生10000*100條隨機圖書ISBN號記錄，ISBN號可以相同
	{
 	    getISBN(storeISBN[size].ISBN);   //產生一條ISBN號
        storeISBN[size].serialnumber=size;   //記錄初始序號
        strcpy(BUFF.ISBN,storeISBN[size].ISBN);
	    BUFF.category=getcategory();
        getbookname(BUFF.bookname);
        getauthors(BUFF.authors);
        outfile.write((char *)&BUFF,sizeof(struct book));     //保存一條記錄
		if(size<10||size>RECORDNUMBER-10) //以文本保存數據測試數據，頭10條記錄和后10條記錄
		{
	      dataout<<size<<"  ";     
	      dataout<<BUFF.ISBN<<"  "; 
		  dataout<<BUFF.category<<"  ";
          dataout<<BUFF.bookname<<"  "; 
          dataout<<BUFF.authors<<endl; 
		}
        size=size+1;
	}
	outfile.close();
	dataout.close();
    Createindex(storeISBN);    //產生索引表
    Createhash(storeISBN);   //產生哈希表
    dwend=GetTickCount();   //記錄結束時間
	cout<<"成功產生 "<<size<<" 條隨機圖書記錄"<<endl;
    cout<<"共耗時約:  "<<dwend-dwstart<<" 毫秒。"<<endl;
    delete []storeISBN;
	return 0; 
}