hashfm.txt

一本数据结构的经典书籍-数据结构算法程序集里

  //从d单链表的第二个结点起顺序查找被删除的元素
  int j,q;
  q=temp.next;  //q初始指向第二个结点
  FLNode tq;//用tq保存散列主文件中位置为q的结点
  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;}
 //若找到了被删除的元素,则将第一个结点中的最后一个元素
 //移动到被删除元素的位置
  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) {//把空的表头结点链接到空闲表的表头
     A[d]=temp.next;
     temp.next=A[m];
     A[m]=p;}
     f2.seekg(p*b2);
     f2.write((char*)&temp, b2);
     DeleteTag=1;}  //置删除成功标志
  //做删除操作的结束处理操作
  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;
}
//从按桶散列的文件中查找关键字为x.key的元素,
//并由x带回该元素,若查找成功则返回1,否则返回0
template<class T>
bool HFile<T>::THFSearch(char* fn1,char* fn2,T& x)
{//以输入和不新建方式打开散列表文件
 ifstream f1(fn1, ios::in|ios::binary);
 if(!f1) {cerr<<fn1<<' '<<"不能打开!"<<endl;
       	exit(1);}
 //以输入和不新建方式打开散列主文件
 ifstream f2(fn2, ios::in|ios::binary);
 if(!f2) {cerr<<fn2<<' '<<"不能打开!"<<endl;
	exit(1);}
  //定义数组A并将f1文件读入A中
 int* A=new int[m+1];
 if(!A) {cerr<<"申请堆内存失败!"<<endl;
	exit(1);}
 f1.read((char*)A, (m+1)*b1);
  //计算x元素在散列表中的地址
 int i,d=x.key%m;
  //从d单链表中顺序查找关键字为x.key的元素
 int p=A[d];
  //从d单链表中顺序查找关键字为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;}
  //进行查找结束处理
 delete [] A;
 f1.close();f2.close();
 if(p==-1) return false; else return true;
}
//按单链表顺序打印出按桶散列主文件中每个结点的所有元素值
template<class T>
void HFile<T>::THFPrint(char* fn1, char* fn2)
{ifstream f1(fn1, ios::in|ios::binary);
 if(!f1) {cerr<<fn1<<' '<<"不能打开!"<<endl;
   exit(1);}
 ifstream f2(fn2, ios::in|ios::binary);
 if(!f2) {cerr<<fn2<<' '<<"不能打开!"<<endl;
   exit(1);}
  int* A=new int[m+1];
  if(!A) {cerr<<"申请堆内存失败!"<<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);
      //输出结点的位置序号
      cout<<setw(2)<<p<<"->";
      //输出结点中每个元素的关键字，以此代替结点的值
      for(int j=0; j<km; j++)
        cout<<pn.data[j].key<<"  ";
      //使p指向下一个结点
	p=pn.next;}
     cout<<endl;}
}
//散列文件的类实现的测试
void main()
{ cout<<"HashFM.cpp运行结果:\n";
  //定义保存记录的数组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"}};
  //定义保存记录的数组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);
  //向散列文件插入数组a和b中保存的记录  
  myfile.THFInsertB(p1,p2,a,15);
  myfile.THFInsertB(p1,p2,b,16);
  //设mark用于保存删除或查找函数返回的值
  int mark;
  //定义x保存一个待插入的元素值或保存待删除或查找元素的关键字
  ElemType x;
  //利用键盘输入操作散列文件
  while(1) {
    cout<<endl<<"功能号表："<<endl;
    cout<<"1---向散列文件插入一个元素"<<endl;
    cout<<"2---从散列文件中删除一个元素"<<endl;
    cout<<"3---从散列文件中查找一个元素"<<endl;
    cout<<"4---输出散列主文件"<<endl;
    cout<<"5---结束运行"<<endl;
    char ch;
    cout<<"请输入你的选择(1-5): ";cin>>ch;
    switch (ch)
     {case '1':
	cout<<"输入待插入元素x的值(一个整数和一个字符串):";
	  cin>>x.key>>x.rest;
        myfile.THFInsertA(p1,p2,x);break;
      case '2':
        cout<<"输入待删除元素x的关键字:";
          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的关键字:";
	        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<<"输入选择错误,请重输!"<<endl;
}}}
HashFM.cpp运行结果:
功能号表：
1---向散列文件插入一个元素
2---从散列文件中删除一个元素
3---从散列文件中查找一个元素
4---输出散列主文件
5---结束运行
请输入你的选择(1-5):1
输入待插入元素x的值(一个整数和一个字符串):88 Houlin
功能号表：
1---向散列文件插入一个元素
2---从散列文件中删除一个元素
3---从散列文件中查找一个元素
4---输出散列主文件
5---结束运行
请输入你的选择(1-5):3
输入待查找元素x的关键字:88
查找成功!88 Houlin
功能号表：
1---向散列文件插入一个元素
2---从散列文件中删除一个元素
3---从散列文件中查找一个元素
4---输出散列主文件
5---结束运行
请输入你的选择(1-5):4
 0: 6->48  80  -10  
 1: 2->17  17  65  
 2: 1->18  34  -10  
 3: 0->13  29  77  
 4:
 5: 3->37  69  -10  
 6: 5->22  38  70  
 7:13->71  -10  -10   8->55  23  55  
 8:15->88  -10  -10   4->8  24  56  
 9: 7->57  25  -10  
10:11->42  -10  -10  
11:12->43  -10  -10  
12:
13:14->93  -10  -10   0->13  29  77  
14: 9->30  -10  -10  
15:10->31  -10  -10  
16:
功能号表：
1---向散列文件插入一个元素
2---从散列文件中删除一个元素
3---从散列文件中查找一个元素
4---输出散列主文件
5---结束运行
请输入你的选择(1-5):2
输入待删除元素x的关键字:88
删除成功!88 Houlin
功能号表：
1---向散列文件插入一个元素
2---从散列文件中删除一个元素
3---从散列文件中查找一个元素
4---输出散列主文件
5---结束运行
请输入你的选择(1-5):4
 0: 6->48  80  -10  
 1: 2->17  17  65  
 2: 1->18  34  -10  
 3: 0->13  29  77  
 4:
 5: 3->37  69  -10  
 6: 5->22  38  70  
 7:13->71  -10  -10   8->55  23  55  
 8: 4->8  24  56  
 9: 7->57  25  -10  
10:11->42  -10  -10  
11:12->43  -10  -10  
12:
13:14->93  -10  -10   0->13  29  77  
14: 9->30  -10  -10  
15:10->31  -10  -10  
16:15->88  -10  -10   4->8  24  56  
功能号表：
1---向散列文件插入一个元素
2---从散列文件中删除一个元素
3---从散列文件中查找一个元素
4---输出散列主文件
5---结束运行
请输入你的选择(1-5): 5