VC++2012编程演练数据结构散列文件
散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。它类似于散列表[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），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
我们创建一个工程
类实现如下
[cpp]
//散列文件的插入、删除和查找操作
#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[i]=-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) {
