//散列文件的插入、刪除和查找操作
//HashFM.cpp
#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
#include<iomanip.h>
//m為散列表的長(zhǎng)度,確定取值為16
  const int m=16;  
//km為散列主文件中每個(gè)結(jié)點(diǎn)所含的元素個(gè)數(shù)，
//取值大于等于1,暫取為3
  const int km=3;  
//定義關(guān)鍵字類(lèi)型為整型
  typedef int KeyType;
//索引主文件中的記錄元素類(lèi)型
struct ElemType {
 int key;    //關(guān)鍵字域
 char rest[10];//其他域,暫用字符數(shù)組表示
};
//索引主文件中的結(jié)點(diǎn)類(lèi)型
struct FLNode {
  ElemType data[km];//值域
  int next; //指向下一個(gè)結(jié)點(diǎn)的指針域
};
//b1為索引表文件中的記錄長(zhǎng)度
  const int b1=sizeof(int);
//b2為索引主文件中的記錄長(zhǎng)度
  const int b2=sizeof(FLNode); 
//NullTag作為空關(guān)鍵字的標(biāo)記,假定用-10表示
  const int NullTag=-10;
//散列文件的類(lèi)定義
template<class T>
class HFile
{public:
  //構(gòu)造函數(shù),初始化散列表文件和主文件
  HFile(char* fn1,char* fn2);
  //把元素x插入到按桶散列的文件中
  void THFInsertA(char* fn1,char* fn2,T x);
  //把數(shù)組x中n個(gè)元素插入到按桶散列的文件中
  void THFInsertB(char* fn1,char* fn2,T x[],int n);
  //從按桶散列的文件中刪除關(guān)鍵字為x.key的元素,
  //并由x帶回該元素,若刪除成功則返回1,否則返回0
  bool THFDelete(char* fn1, char* fn2, T& x);
  //從按桶散列的文件中查找關(guān)鍵字為x.key的元素,
  //并由x帶回該元素,若查找成功則返回1,否則返回0
  bool THFSearch(char* fn1,char* fn2,T& x);
  //按單鏈表順序打印出按桶散列主文件中每個(gè)結(jié)點(diǎn)的所有元素值
  void THFPrint(char* fn1,char* fn2);
};
//散列文件的類(lèi)實(shí)現(xiàn)
//初始化散列表文件和主文件
template<class T>
HFile<T>::HFile(char* fn1,char* fn2)
{//以輸出方式打開(kāi)并建立空的散列表文件
 ofstream f1(fn1, ios::out|ios::binary);
 if(!f1) {
   cerr<<fn1<<' '<<"不能打開(kāi)!"<<endl;
   exit(1);}
//以輸出方式打開(kāi)并建立空的散列主文件
 ofstream f2(fn2, ios::out|ios::binary);
 if(!f2) {cerr<<fn2<<' '<<"不能打開(kāi)!"<<endl;
	  exit(1);}
//動(dòng)態(tài)分配具有m+1個(gè)整型存儲(chǔ)空間的數(shù)組A
 int* A=new int[m+1];
 if(!A){cerr<<"申請(qǐng)堆內(nèi)存失敗!"<<endl;
       	exit(1);}
//給數(shù)組A中的每個(gè)元素賦初值-1，表示空指針
 for(int i=0; i<m+1; i++)
   A[i]=-1;
//初始化散列表文件
  f1.write((char*)A, (m+1)*b1);
 //刪除數(shù)組A并關(guān)閉文件
  delete [] A;
  f1.close();
  f2.close();
}
//把元素x插入到按桶散列的文件中
template<class T>
void HFile<T>::THFInsertA(char* fn1, char* fn2, T x)
{//以輸入輸出和不新建方式打開(kāi)散列表文件
 fstream f1(fn1,ios::in|ios::out|ios::binary);
 if(!f1) {cerr<<fn1<<' '<<"不能打開(kāi)!"<<endl;
      exit(1);}
 //以輸入輸出和不新建方式打開(kāi)散列主文件
 fstream f2(fn2, ios::in|ios::out|ios::binary);
 if(!f2){cerr<<fn2<<' '<<"不能打開(kāi)!"<<endl;
         exit(1);}
 //給數(shù)組A中的每個(gè)元素賦初值-1，表示空指針
 int* A=new int[m+1];
 if(!A) {cerr<<"申請(qǐng)堆內(nèi)存失敗!"<<endl;
	 exit(1);}
 //將散列表文件中的內(nèi)容全部讀入到數(shù)組A中
 f1.read((char*)A, (m+1)*b1);
 //以關(guān)鍵字x.key計(jì)算x的散列地址
 int d=x.key%m;
 //將x插入到d單鏈表的表頭結(jié)點(diǎn)中
 int j;
 FLNode temp;
 if(A[d]!=-1)
  {f2.seekg(A[d]*b2);
   f2.read((char*)&temp, b2);
   for(j=0; j<km; j++)
    if(temp.data[j].key==NullTag) break;
    if(j<km) {
      temp.data[j]=x;
      f2.seekg(-b2, ios::cur);
      f2.write((char*)&temp, b2);
      goto END;  //插入表頭結(jié)點(diǎn)后，轉(zhuǎn)去做結(jié)束處理
  }}
  //當(dāng)d單鏈表為空或頭結(jié)點(diǎn)中沒(méi)有空閑位置時(shí)向下執(zhí)行
  //建立待插入d單鏈表表頭的內(nèi)存結(jié)點(diǎn)temp
  temp.data[0]=x;
  for(j=1; j<km; j++)
   temp.data[j].key=NullTag;
  temp.next=A[d];
  //將temp結(jié)點(diǎn)的值寫(xiě)入到f2文件尾并被鏈接到d單鏈表的表頭
  if(A[m]==-1) {
  //將f2中的文件指針移至文件尾
   f2.seekg(0,ios::end);
  //計(jì)算出文件尾的結(jié)點(diǎn)位置序號(hào)
   int len=f2.tellg()/b2;
  //將temp結(jié)點(diǎn)的值寫(xiě)入文件尾
   f2.write((char*)&temp,b2);
  //使A[d]指向新插入的結(jié)點(diǎn)
   A[d]=len;}
  //將temp結(jié)點(diǎn)的值寫(xiě)入到f2文件的一個(gè)空閑結(jié)點(diǎn)中
  //并被鏈接到d單鏈表的表頭
   else {//p指向空閑單鏈表的表頭結(jié)點(diǎn)
     int p=A[m];
   //使空閑單鏈表的表頭指針指向其下一個(gè)結(jié)點(diǎn)
     f2.seekg(p*b2);
     FLNode pn;
     f2.read((char*)&pn, b2);
     A[m]=pn.next;
   //使temp的值寫(xiě)入到p位置的結(jié)點(diǎn)上
     f2.seekg(-b2, ios::cur);
     f2.write((char*)&temp, b2);
   //使A[d]指向新插入的p結(jié)點(diǎn)
     A[d]=p;}
  //將數(shù)組A中的全部?jī)?nèi)容寫(xiě)回到散列表文件f1中
   f1.seekg(0);
   f1.write((char*)A, (m+1)*b1);
  //刪除動(dòng)態(tài)數(shù)組A和關(guān)閉所有文件
   END:
    delete [] A;
    f1.close();
    f2.close();
}
//把數(shù)組x中n個(gè)元素插入到按桶散列的文件中
template<class T>
void HFile<T>::THFInsertB(char* fn1,char* fn2,T x[],int n)
{fstream f1(fn1, ios::in|ios::out|ios::binary);
 if(!f1) {cerr<<fn1<<' '<<"不能打開(kāi)!"<<endl;
	  exit(1);}
 fstream f2(fn2, ios::in|ios::out|ios::binary);
 if(!f2) {cerr<<fn2<<' '<<"不能打開(kāi)!"<<endl;
          exit(1);}
 int* A=new int[m+1];
 if(!A) {cerr<<"申請(qǐng)堆內(nèi)存失敗!"<<endl;
	 exit(1);}
 f1.read((char*)A, (m+1)*b1);
 for(int i=0; i<n; i++)
  {int d=x[i].key%m;
   int j;
   FLNode temp;
   if(A[d]!=-1)
    {f2.seekg(A[d]*b2);
     f2.read((char*)&temp, b2);
     for(j=0; j<km; j++)
      if(temp.data[j].key==NullTag) break;
      if(j<km) {
       temp.data[j]=x[i];
       f2.seekg(-b2, ios::cur);
       f2.write((char*)&temp, b2);
       continue;}}
      temp.data[0]=x[i];
      for(j=1;j<km;j++)
	temp.data[j].key=NullTag;
      temp.next=A[d];
      if(A[m]==-1) {
       f2.seekg(0,ios::end);
       int len=f2.tellg()/b2;
       f2.write((char*)&temp,b2);
       A[d]=len;}
      else {int p=A[m];
	f2.seekg(p*b2);
	FLNode pn;
	f2.read((char*)&pn, b2);
	A[m]=pn.next;
	f2.seekg(-b2, ios::cur);
	f2.write((char*)&temp, b2);
	A[d]=p;}}
    f1.seekg(0);
    f1.write((char*)A, (m+1)*b1);
    delete [] A;
    f1.close();f2.close();
}
//從按桶散列的文件中刪除關(guān)鍵字為x.key的元素,并由x帶回該
//元素,若刪除成功則返回1,否則返回0
template<class T>
bool HFile<T>::THFDelete(char* fn1,char* fn2,T& x)
{fstream f1(fn1,ios::in|ios::out|ios::binary);
 int k;
 if(!f1) {cerr<<fn1<<' '<<"不能打開(kāi)!"<<endl;
	  exit(1);}
 fstream f2(fn2,ios::in|ios::out|ios::binary);
 if(!f2) {cerr<<fn2<<' '<<"不能打開(kāi)!"<<endl;
	  exit(1);}
 int* A=new int[m+1];
 if(!A) {cerr<<"申請(qǐng)堆內(nèi)存失敗!"<<endl;
	 exit(1);}
 f1.read((char*)A, (m+1)*b1);
 int DeleteTag=0;  //用DeleteTag作為刪除是否成功的標(biāo)記
 int d=x.key%m;
 int p=A[d],i=0;  //用p保存d單鏈表的表頭結(jié)點(diǎn)的位置序號(hào)，
 //用i保存該結(jié)點(diǎn)中被刪除元素的下標(biāo)或第一個(gè)空元素的下標(biāo)
 FLNode temp;
 //從d單鏈表的表頭結(jié)點(diǎn)中刪除關(guān)鍵字為x.key的元素
 if(p!=-1)
  {f2.seekg(p*b2);
   f2.read((char*)&temp, b2);
   while(i<km && temp.data[i].key!=NullTag)
    if(temp.data[i].key==x.key) break;
    else i++;
    if(i<km && temp.data[i].key==x.key) {
     x=temp.data[i]; //由x帶回被刪除的元素值
    for(k=i+1; k<km; k++)
     if(temp.data[k].key!=NullTag)
       temp.data[k-1]=temp.data[k];
     else break;
   temp.data[k-1].key=NullTag;
   if(k-1==0) { //刪除d單鏈表中表頭空結(jié)點(diǎn)
    A[d]=temp.next;
    temp.next=A[m];
    A[m]=p;}
    f2.seekg(-b2, ios::cur);
    f2.write((char*)&temp, b2);
    DeleteTag=1;//被賦值1表示刪除成功
    goto END;  //轉(zhuǎn)去做結(jié)束處理
  }}
 //若d單鏈表為空,則轉(zhuǎn)去做結(jié)束處理
  else goto END;
  //從d單鏈表的第二個(gè)結(jié)點(diǎn)起順序查找被刪除的元素
  int j,q;
  q=temp.next;  //q初始指向第二個(gè)結(jié)點(diǎn)
  FLNode tq;//用tq保存散列主文件中位置為q的結(jié)點(diǎn)
  while(q!=-1)
    {f2.seekg(q*b2);
     f2.read((char*)&tq, b2);
     for(j=0; j<km; j++)
       if(tq.data[j].key==x.key) {
	 x=tq.data[j];break;}
     if(j<km) break;
     q=tq.next;}
 //若找到了被刪除的元素,則將第一個(gè)結(jié)點(diǎn)中的最后一個(gè)元素
 //移動(dòng)到被刪除元素的位置
  if(q!=-1) {tq.data[j]=temp.data[i-1];
    temp.data[i-1].key=NullTag;
    f2.seekg(q*b2);
    f2.write((char*)&tq, b2);
    if(i==1) {//把空的表頭結(jié)點(diǎn)鏈接到空閑表的表頭
     A[d]=temp.next;
     temp.next=A[m];
     A[m]=p;}
     f2.seekg(p*b2);
     f2.write((char*)&temp, b2);
     DeleteTag=1;}  //置刪除成功標(biāo)志
  //做刪除操作的結(jié)束處理操作
  END:
   if(DeleteTag==1) {
     f1.seekg(0);
     f1.write((char*)A,(m+1)*b1);}
     delete [] A;
     f1.close();
     f2.close();
     if(DeleteTag==1) return true;
     else return false;
}
//從按桶散列的文件中查找關(guān)鍵字為x.key的元素,
//并由x帶回該元素,若查找成功則返回1,否則返回0
template<class T>
bool HFile<T>::THFSearch(char* fn1,char* fn2,T& x)
{//以輸入和不新建方式打開(kāi)散列表文件
 ifstream f1(fn1, ios::in|ios::binary);
 if(!f1) {cerr<<fn1<<' '<<"不能打開(kāi)!"<<endl;
       	exit(1);}
 //以輸入和不新建方式打開(kāi)散列主文件
 ifstream f2(fn2, ios::in|ios::binary);
 if(!f2) {cerr<<fn2<<' '<<"不能打開(kāi)!"<<endl;
	exit(1);}
  //定義數(shù)組A并將f1文件讀入A中
 int* A=new int[m+1];
 if(!A) {cerr<<"申請(qǐng)堆內(nèi)存失敗!"<<endl;
	exit(1);}
 f1.read((char*)A, (m+1)*b1);
  //計(jì)算x元素在散列表中的地址
 int i,d=x.key%m;
  //從d單鏈表中順序查找關(guān)鍵字為x.key的元素
 int p=A[d];
  //從d單鏈表中順序查找關(guān)鍵字為x.key的元素
 FLNode temp;
 while(p!=-1)
   {f2.seekg(p*b2);
    f2.read((char*)&temp, b2);
    for(i=0;i<km;i++)
     if(temp.data[i].key==x.key)
      {x=temp.data[i];//被查找到的元素由x帶回
       	break;}
    if(i<km) break;
    else  p=temp.next;}
  //進(jìn)行查找結(jié)束處理
 delete [] A;
 f1.close();f2.close();
 if(p==-1) return false; else return true;
}
//按單鏈表順序打印出按桶散列主文件中每個(gè)結(jié)點(diǎn)的所有元素值
template<class T>
void HFile<T>::THFPrint(char* fn1, char* fn2)
{ifstream f1(fn1, ios::in|ios::binary);
 if(!f1) {cerr<<fn1<<' '<<"不能打開(kāi)!"<<endl;
   exit(1);}
 ifstream f2(fn2, ios::in|ios::binary);
 if(!f2) {cerr<<fn2<<' '<<"不能打開(kāi)!"<<endl;
   exit(1);}
  int* A=new int[m+1];
  if(!A) {cerr<<"申請(qǐng)堆內(nèi)存失敗!"<<endl;
   exit(1);}
  f1.read((char*)A, (m+1)*b1);
  int p;
  FLNode pn;
  for(int i=0; i<m+1; i++)
    {cout<<setw(2)<<i<<':';
     p=A[i];
     while(p!=-1) {
      f2.seekg(p*b2);
      f2.read((char*)&pn, b2);
      //輸出結(jié)點(diǎn)的位置序號(hào)
      cout<<setw(2)<<p<<"->";
      //輸出結(jié)點(diǎn)中每個(gè)元素的關(guān)鍵字，以此代替結(jié)點(diǎn)的值
      for(int j=0; j<km; j++)
        cout<<pn.data[j].key<<"  ";
      //使p指向下一個(gè)結(jié)點(diǎn)
	p=pn.next;}
     cout<<endl;}
}
//散列文件的類(lèi)實(shí)現(xiàn)的測(cè)試
void main()
{ cout<<"HashFM.cpp運(yùn)行結(jié)果:\n";
  //定義保存記錄的數(shù)組a并初始化
  ElemType a[15]={{13,"li"},{18,"liu"},{17,"wphp"},{37,"menrm"},
  {8,"ytong"},{22,"zhua"},{24,"push"},{48,"qian"},{34,"tang"},
  {57,"shdm"},{55,"kang"},{30,"liuli"},{25,"qiaoh"},
  {31,"dukun"},{17,"haiang"}};
  //定義保存記錄的數(shù)組b并初始化
  ElemType b[16]={{23,"tang"},{38,"suan"},{56,"kony"},
  {55,"shao"},{80,"caik"},{70,"ganwu"},{65,"dukun"},{42,"sini"},
  {29,"liuda"},{43,"xitu"},{71,"taoto"},{77,"shouw"},
  {93,"shum"},{69,"liyz"},{45,"xuyang"},{19,"wxy"}};
  //定義散列表文件和主文件的名字，并由字符指針p1和p2所指向
  char *p1=".\\HFile.idx", *p2=".\\HFile.dat";
  //初始化散列表文件和主文件	
  HFile<ElemType> myfile(p1,p2);
  //向散列文件插入數(shù)組a和b中保存的記錄  
  myfile.THFInsertB(p1,p2,a,15);
  myfile.THFInsertB(p1,p2,b,16);
  //設(shè)mark用于保存刪除或查找函數(shù)返回的值
  int mark;
  //定義x保存一個(gè)待插入的元素值或保存待刪除或查找元素的關(guān)鍵字
  ElemType x;
  //利用鍵盤(pán)輸入操作散列文件
  while(1) {
    cout<<endl<<"功能號(hào)表："<<endl;
    cout<<"1---向散列文件插入一個(gè)元素"<<endl;
    cout<<"2---從散列文件中刪除一個(gè)元素"<<endl;
    cout<<"3---從散列文件中查找一個(gè)元素"<<endl;
    cout<<"4---輸出散列主文件"<<endl;
    cout<<"5---結(jié)束運(yùn)行"<<endl;
    char ch;
    cout<<"請(qǐng)輸入你的選擇(1-5): ";cin>>ch;
    switch (ch)
     {case '1':
	cout<<"輸入待插入元素x的值(一個(gè)整數(shù)和一個(gè)字符串):";
	  cin>>x.key>>x.rest;
        myfile.THFInsertA(p1,p2,x);break;
      case '2':
        cout<<"輸入待刪除元素x的關(guān)鍵字:";
          cin>>x.key;
	mark=myfile.THFDelete(p1,p2,x);
        if(mark==1) cout<<"刪除成功!"<<x.key<<' '<<x.rest<<endl;
	else cout<<"刪除失敗!"<<endl;break;
      case '3':cout<<"輸入待查找元素x的關(guān)鍵字:";
	        cin>>x.key;
	mark=myfile.THFSearch(p1,p2,x);
        if(mark==1)
	  cout<<"查找成功!"<<x.key<<' '<<x.rest<<endl;
        else cout<<"查找失敗!"<<endl;break;
      case '4':myfile.THFPrint(p1,p2);break;
      case '5':return;
      default:cout<<"輸入選擇錯(cuò)誤,請(qǐng)重輸!"<<endl;
}}}