indexfile.cpp

索引文件操作（数据结构）

#include<iomanip.h>
#include<stdio.h>
#include<stdlib.h>
#include<fstream.h>

#include"IndexFile.h"
const int m=5;
const int DeleteMark = -100;
void PrintMainFile (char * fname1 )
{
      ifstream fin(fname1,ios::in|ios::nocreate|ios::binary);
      if (!fin) {
            cerr << fname1 << ' ' <<"not find !" << endl;
            exit (1);
	  }
	  ElemType x;
	  fin.seekg(0,ios::end);
	  int bl = sizeof (ElemType);
	  int n=fin.tellg ()/bl;
	  fin.seekg(0);
	  for(int i =0;i<n;i++) {
		  fin.read((char * ) &x, bl );
		  if(i% 4 ==0)  cout <<endl;
		  cout <<setw(5)<<x.key <<setw(10) <<x.rest;
	  }
	  cout << endl;
	  fin.close();
}
void PrintIndexFile (char * fname2 )
{
      ifstream fin (fname2,ios::in |ios::nocreate|ios::binary);
      if (!fin) {
             cerr<<fname2<<' '<<"not find !"<<endl;
             exit (1);
       }
	  IndexItem x;
	  fin.seekg(0,ios::end);
	  int b2 = sizeof (IndexItem);
	  int n = fin.tellg ()/b2;
	  fin.seekg(0);
	  for(int i=0;i<n;i++){
		  fin .read ( (char * ) &x, b2 );
		  if(i% 8 ==0)  cout <<endl;
		  cout <<setw(4)<<x.key<<setw(3)<<x.next;
	  }
      cout << endl;
      fin.close();
}
void MFAppend(char* fname1, char* fname2, ElemType a[], int n)
{
	ofstream ofs(fname1,ios::app|ios::binary);
	if(!ofs){
		cerr<<fname1<<' '<<"not open!"<<endl;
             exit (1);
	}
      int i;
      int b1=sizeof(ElemType);
      ofs.seekp(0,ios::end);
      int flen=ofs.tellp()/b1;
      for(i=0;i<n;i++)
		  ofs.write((char *)&a[i],b1);
	  ofs.close();
	  IndexItem x;
	  for(i=0;i<n;i++) {
		  x.key =a[i].key;
		  x.next = flen + i;
		  IFInsert(fname2,x);
	  }
}



void MFDelete (char * fname1, char * fname2, KeyType a[],int n)
{
   fstream fio(fname1,ios::in|ios::out|
      ios::nocreate|ios::binary);
   if(!fio){
	   cerr<<fname1<<' '<<"not open !"<<endl;
	   exit(1);
   }
   int b1=sizeof(ElemType);
   IndexItem x;
   ElemType y;
   int i;
   for(i=0; i<n; i++) {
	   x.key=a[i];
	   bool k=IFDelete(fname2,x);
	   if (!k){
		   cout<<"关键字为"<<x.key<<"的记录不存在"<<endl;
		   continue;
	   }
	   fio.seekg (x.next *b1);
	   fio.read((char *)&y,b1);
	   y.key=DeleteMark;
	   fio.seekg (-b1,ios::cur);
	   fio.write((char *)&y,b1);
	   cout <<"关键字为"<<x.key<<"的记录被删除"<<endl;
   }
   fio.close();
}
void MFSearch (char * fname1, char * fname2, KeyType a [], int n)
{
   ifstream ifs(fname1,ios::in|ios::nocreate|ios::binary);
   if(!ifs){
	   cerr << fname1<<' '<<"not open!" <<endl;
	   exit(1);
   }
   int b1=sizeof(ElemType);
   IndexItem x;
   ElemType y;
   int i;
   for(i=0;i<n;i++){
	   x.key=a[i];
	   bool k=IFSearch(fname2,x);
	   if(!k){
		   cout << "查关键字为" <<x.key<< "的记录失败!"<<endl;
		   continue;
	   }
	   ifs.seekg(x.next *b1);
	   ifs.read((char *)&y,b1);
	   cout<<"查关键字为"<<x.key<<"的记录成功!"<<endl;
	   cout<<"该记录内容为:"<<y.key<<' '<<y.rest<<endl;
   }
   ifs.close();
}
void SeqInsert (IndexItem A[], int mm, IndexItem x)
{
	for(int i=mm-1;i>=0;i--)
	{
		if (A[i].key>x.key)
			A[i+1]=A[i];
		else {
			A[i+1] =x;
			break;
		}
	}
	if(i<0) A[0] =x;
}

void IFInsert (char *fname2, IndexItem x)
{
	ifstream ifs (fname2, ios::in|ios ::binary);
	if (!ifs) {
		cerr<<fname2 << ' ' << "not open !" << endl;
		exit (1);
	}
	ofstream ofs("temp",ios ::out|ios::binary);
	if (!ofs){
		cerr<<"temp"<<' '<<"not open!"<<endl;
		exit (1);
	}
	IndexItem* A=new IndexItem[m+1];
	ifs.seekg (0);
	int b2=sizeof(IndexItem);
	while (1)
	{
		ifs.read((char *)A, m*b2);
		int s=ifs.gcount()/b2;
		if(s==m)
		{
			if (A[m-1].key<x.key){
				ofs.write((char *)A,m*b2);
			}
			else {
				SeqInsert (A,m,x);
				ofs.write ((char * )A, (m+1)*b2);
				while(!ifs.eof())
				{
					ifs .read((char *)A, m* b2 );
					s=ifs.gcount ()/b2;
					ofs.write((char *)A,s*b2);
				}
				break;
			}
		}
		else
		{
			SeqInsert(A,s,x);
			ofs.write((char *)A,(s+1) *b2);
			break;
		}
	}
	delete [] A;
	ifs.close();
	ofs.close();
	remove(fname2);
	rename("temp",fname2);
}


bool SeqDelete(IndexItem A[], int mm, IndexItem& x)
{
	int i =0;
	while (i<mm&&A[i].key<x.key)
		i++;
	if(i ==mm||A[i].key!=x.key) return false;
	x=A[i];
	for(int j =i +1;j<mm;j++)
		A[j-1] =A[j];
	return true;
}



bool IFDelete(char * fname2, IndexItem& x)
{
	ifstream ifs(fname2,ios::in|ios::nocreate|ios::binary);
	if(!ifs){
		cerr <<fname2<<' ' << "not found !"<<endl;
		exit(1);
	}
	ofstream ofs("temp",ios::out|ios::binary);
	if (!ofs){
		cerr<<"temp"<<' '<<"not open !"<<endl;
		}
	int b2 =sizeof(IndexItem);
	IndexItem *A=new IndexItem[m];
	bool d;
	while (1)
	{
		ifs.read((char *)A, m*b2);
		int s=ifs.gcount()/b2;
		if (s==m)
		{
			if(A[m-1].key<x.key) {
				ofs.write ((char * )A, m * b2);
			}
				else {
					d = SeqDelete (A,m,x);
					if(d)
						ofs.write ((char *)A, (m-1)*b2);
					else
						ofs.write((char *)A,m*b2);
					while(!ifs.eof())
					{
						ifs.read((char *)A,m*b2);
						s=ifs.gcount ()/b2;
						ofs.write((char* )A,s*b2);
					}
					break;
				}
			}
			else
			{
				d=SeqDelete(A,s,x);
				if(d)
					ofs.write((char*)A,(s-1)*b2);
				else
					ofs.write((char *)A,s*b2);
				break;
			}
		}
		delete [] A;
		ifs.close();
		ofs.close();
		remove(fname2);
		rename("temp", fname2);
		if(d)return true;
			else return false;
}

bool IFSearch(char* fname2, IndexItem& x)
{
	ifstream ifs(fname2, ios::in|ios::nocreate|ios::binary);
	if (!ifs)
	{
		cerr << fname2 <<' '<<"not found!"<<endl;
		exit (1);
	}
	ifs.seekg (0,ios::end);
	int b2 = sizeof (IndexItem);
	int n = ifs.tellg()/b2;
	ifs.seekg (0);
	int low=0, high=n-1;
	while(low<=high)
	{
		int mid = (low+high)/2;
		IndexItem tm;
		ifs.seekg (mid*b2);
		ifs.read((char *)&tm,b2);
		if(x.key==tm.key){
			x=tm;
			ifs.close();
			return true;
		}
		else if(x.key<tm.key)
			high=mid-1;
		else
			low=mid+1;
	}
	ifs.close();
	return false;
}