滴水逆向联盟

标题: VC++2012编程演练数据结构《19》散列文件 [打印本页]

---

作者: 大灰狼    时间: 2014-8-26 08:15
标题: VC++2012编程演练数据结构《19》散列文件
散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。它类似于散列表[1]，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。
　　与散列表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶(Bucket)。假如一个桶能存放m个记录，则当桶中已有m个同义词的记录时，存放第m+1个同义词会发生"溢出"。处理溢 出虽可采用散列表中处理冲突的各种方法，但对散列文件而言，主要采用拉链法。
　　在散列文件中进行查找时，首先根据给定值求出散列桶地址，将基桶的记录读入内存，进行顺序查找，若找到关键字等于给定值的记录，则检索成功；否则，读入溢出桶的记录继续进行查找。
　　在散列文件中删去一个记录，仅需对被删除记录标记即可。

文件优缺点

散列文件的优点是：文件随机存放，记录不需进行排序；插入、删除方便；存取速度快；不需要索引区，节省存储空间。其缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次插入、删除后，也可能造成文件结构不合理，需要重新组织文件。

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
　* 若结构中存在关键字和K相等的记录，则必定在f(K）的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function），按这个思想建立的表为散列表。
　　* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当重载因子不超过75%，查找效率最高。
　　* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

打开IDE

我们创建一个工程

类实现如下

[cpp] view plaincopy

• //散列文件的插入、删除和查找操作  
•   
• #include<iostream>  
• #include<stdlib.h>  
• #include<fstream>  
• #include<iomanip>  
• using namespace std;  
• //m为散列表的长度,确定取值为16  
•   const int m=16;   
• //km为散列主文件中每个结点所含的元素个数，  
• //取值大于等于1,暂取为3  
•   const int km=3;   
• //定义关键字类型为整型  
•   typedef int KeyType;  
• //索引主文件中的记录元素类型  
• struct ElemType {  
• int key;    //关键字域  
• char rest[10];//其他域,暂用字符数组表示  
• };  
• //索引主文件中的结点类型  
• struct FLNode {  
•   ElemType data[km];//值域  
•   int next; //指向下一个结点的指针域  
• };  
• //b1为索引表文件中的记录长度  
•   const int b1=sizeof(int);  
• //b2为索引主文件中的记录长度  
•   const int b2=sizeof(FLNode);   
• //NullTag作为空关键字的标记,假定用-10表示  
•   const int NullTag=-10;  
• //散列文件的类定义  
• template<class T>  
• class HFile  
• {public:  
•   //构造函数,初始化散列表文件和主文件  
•   HFile(char* fn1,char* fn2);  
•   //把元素x插入到按桶散列的文件中  
•   void THFInsertA(char* fn1,char* fn2,T x);  
•   //把数组x中n个元素插入到按桶散列的文件中  
•   void THFInsertB(char* fn1,char* fn2,T x[],int n);  
•   //从按桶散列的文件中删除关键字为x.key的元素,  
•   //并由x带回该元素,若删除成功则返回1,否则返回0  
•   bool THFDelete(char* fn1, char* fn2, T& x);  
•   //从按桶散列的文件中查找关键字为x.key的元素,  
•   //并由x带回该元素,若查找成功则返回1,否则返回0  
•   bool THFSearch(char* fn1,char* fn2,T& x);  
•   //按单链表顺序打印出按桶散列主文件中每个结点的所有元素值  
•   void THFPrint(char* fn1,char* fn2);  
• };  
• //散列文件的类实现  
• //初始化散列表文件和主文件  
• template<class T>  
• HFile<T>::HFile(char* fn1,char* fn2)  
• {//以输出方式打开并建立空的散列表文件  
• ofstream f1(fn1, ios::out|ios::binary);  
• if(!f1) {  
•    cerr<<fn1<<' '<<"不能打开!"<<endl;  
•    exit(1);}  
• //以输出方式打开并建立空的散列主文件  
• ofstream f2(fn2, ios::out|ios::binary);  
• if(!f2) {cerr<<fn2<<' '<<"不能打开!"<<endl;  
•       exit(1);}  
• //动态分配具有m+1个整型存储空间的数组A  
• int* A=new int[m+1];  
• if(!A){cerr<<"申请堆内存失败!"<<endl;  
•         exit(1);}  
• //给数组A中的每个元素赋初值-1，表示空指针  
• for(int i=0; i<m+1; i++)  
•    A=-1;  
• //初始化散列表文件  
•   f1.write((char*)A, (m+1)*b1);  
• //删除数组A并关闭文件  
•   delete [] A;  
•   f1.close();  
•   f2.close();  
• }  
• //把元素x插入到按桶散列的文件中  
• template<class T>  
• void HFile<T>::THFInsertA(char* fn1, char* fn2, T x)  
• {//以输入输出和不新建方式打开散列表文件  
• fstream f1(fn1,ios::in|ios::out|ios::binary);  
• if(!f1) {cerr<<fn1<<' '<<"不能打开!"<<endl;  
•       exit(1);}  
• //以输入输出和不新建方式打开散列主文件  
• fstream f2(fn2, ios::in|ios::out|ios::binary);  
• if(!f2){cerr<<fn2<<' '<<"不能打开!"<<endl;  
•          exit(1);}  
• //给数组A中的每个元素赋初值-1，表示空指针  
• int* A=new int[m+1];  
• if(!A) {cerr<<"申请堆内存失败!"<<endl;  
•      exit(1);}  
• //将散列表文件中的内容全部读入到数组A中  
• f1.read((char*)A, (m+1)*b1);  
• //以关键字x.key计算x的散列地址  
• int d=x.key%m;  
• //将x插入到d单链表的表头结点中  
• 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;  //插入表头结点后，转去做结束处理  
•   }}  
•   //当d单链表为空或头结点中没有空闲位置时向下执行  
•   //建立待插入d单链表表头的内存结点temp  
•   temp.data[0]=x;  
•   for(j=1; j<km; j++)  
•    temp.data[j].key=NullTag;  
•   temp.next=A[d];  
•   //将temp结点的值写入到f2文件尾并被链接到d单链表的表头  
•   if(A[m]==-1) {  
•   //将f2中的文件指针移至文件尾  
•    f2.seekg(0,ios::end);  
•   //计算出文件尾的结点位置序号  
•    int len=f2.tellg()/b2;  
•   //将temp结点的值写入文件尾  
•    f2.write((char*)&temp,b2);  
•   //使A[d]指向新插入的结点  
•    A[d]=len;}  
•   //将temp结点的值写入到f2文件的一个空闲结点中  
•   //并被链接到d单链表的表头  
•    else {//p指向空闲单链表的表头结点  
•      int p=A[m];  
•    //使空闲单链表的表头指针指向其下一个结点  
•      f2.seekg(p*b2);  
•      FLNode pn;  
•      f2.read((char*)&pn, b2);  
•      A[m]=pn.next;  
•    //使temp的值写入到p位置的结点上  
•      f2.seekg(-b2, ios::cur);  
•      f2.write((char*)&temp, b2);  
•    //使A[d]指向新插入的p结点  
•      A[d]=p;}  
•   //将数组A中的全部内容写回到散列表文件f1中  
•    f1.seekg(0);  
•    f1.write((char*)A, (m+1)*b1);  
•   //删除动态数组A和关闭所有文件  
•    END:  
•     delete [] A;  
•     f1.close();  
•     f2.close();  
• }  
• //把数组x中n个元素插入到按桶散列的文件中  
• 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<<' '<<"不能打开!"<<endl;  
•       exit(1);}  
• fstream f2(fn2, ios::in|ios::out|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);  
• for(int i=0; i<n; i++)  
•   {int d=x.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;  
•        f2.seekg(-b2, ios::cur);  
•        f2.write((char*)&temp, b2);  
•        continue;}}  
•       temp.data[0]=x;  
•       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();  
• }  
• //从按桶散列的文件中删除关键字为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<<' '<<"不能打开!"<<endl;  
•       exit(1);}  
• fstream f2(fn2,ios::in|ios::out|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 DeleteTag=0;  //用DeleteTag作为删除是否成功的标记  
• int d=x.key%m;  
• int p=A[d],i=0;  //用p保存d单链表的表头结点的位置序号，  
• //用i保存该结点中被删除元素的下标或第一个空元素的下标  
• FLNode temp;  
• //从d单链表的表头结点中删除关键字为x.key的元素  
• if(p!=-1)  
•   {f2.seekg(p*b2);  
•    f2.read((char*)&temp, b2);  
•    while(i<km && temp.data.key!=NullTag)  
•     if(temp.data.key==x.key) break;  
•     else i++;  
•     if(i<km && temp.data.key==x.key) {  
•      x=temp.data; //由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单链表中表头空结点  
•     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;  //转去做结束处理  
•   }}  
• //若d单链表为空,则转去做结束处理  
•   else goto END;  
•   //从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.key==x.key)  
•       {x=temp.data;//被查找到的元素由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;  
•      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;}  
• }  
  

类调用如下

[cpp] view plaincopy

• //散列文件的类实现的测试  
• void main()  
• { cout<<"运行结果:\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;  
• }}}  
  

效果如下

---

欢迎光临 滴水逆向联盟 (http://dtdebug.com/)

Powered by Discuz! X3.2