本文共 2437 字，大约阅读时间需要 8 分钟。
线性开型寻址实现
描述
给定散列函数的除数D和操作数m，输出每次操作后的状态。
有以下三种操作：
插入x，若散列表已存在x，输出“Existed”，否则插入x到散列表中，输出所在的下标。
查询x，若散列表不含有x，输出“-1”，否则输出x对应下标。
删除x，若散列表不含有x，输出“Not Found”，否则输出删除x过程中移动元素的个数。
格式
输入格式
第一行两个整数D，m。分别代表散列函数的除数D和操作数m。
接下来m行，每行两个整数opt和x，分别代表操作类型和操作数。
若opt为0，代表插入x。
若opt为1，代表查询x。
若opt为2，代表删除x。
输出格式
按要求输出。
样例1
输入
7 12
1 21
0 1
0 13
0 5
0 23
0 26
0 33
1 33
1 33
1 13
1 5
1 1
输出
-1
1
6
5
2
0
3
3
3
6
5
1
样例二
输入
20 30
0 84
0 15
0 54
2 15
2 84
1 54
2 54
0 89
1 89
0 13
0 48
2 89
0 60
0 24
1 13
0 6
1 24
0 31
2 60
2 48
0 49
0 9
1 6
1 13
0 33
2 49
0 60
1 6
2 9
1 60
输出
4
15
14
0
0
14
0
9
9
13
8
0
0
4
13
6
4
11
0
0
9
10
6
13
14
1
0
6
0
0
限制
1s, 1024KiB for each test case.
#include using namespace std;template class HashTable{ public: HashTable(int theDivisor);//构造函数 ~HashTable(){ //析构函数 delete []table; delete []empty; } int search(const K &theKey); int insert(const E & e); int erase(const K &theKey);private: int hSearch(const K &k)const; int divisor; E *table;//散列表 bool *empty;};template HashTable ::HashTable(int theDivisor) { divisor=theDivisor; table=new E[divisor]; empty=new bool[divisor]; for(int i=0;i int HashTable ::hSearch(const K &theKey) const { int i=theKey % divisor; //起始桶 int j=i; do{ if(empty[j]||table[j]==theKey) return j; j=(j+1)%divisor; //表为环形的，找到下一个桶 }while(j!=i); return j; //回到起始桶}template int HashTable ::search(const K &theKey) { int b=hSearch(theKey); if(empty[b]||table[b]!=theKey) //b表示可插入的空位置索引或者起始桶时 return -1; //如果找到了元素,输出元素下标 else return b;}template int HashTable ::insert(const E &e) { K theKey=e; int b=hSearch(theKey); if(empty[b]){ //空桶的情况 empty[b]=false; table[b]=e; return b;//返回元素存在的位置 } if(!empty[b]&&table[b]==theKey){ return -1; } else if(!empty[b]&&table[b]!=theKey){ //返回的是起始桶 for(;!empty[b];b=(b+1)%divisor); //不断往后找空桶 empty[b]=false; table[b]=e; return b; } }template int HashTable ::erase(const K &theKey) { int b=hSearch(theKey); //找到想要删除的元素所在的位置 if(empty[b]||table[b]!=theKey) return -1; else if(table[b]==theKey){ empty[b]=true; //显性置空 int swapTimes=0; int move=b; //定义一个移动位置move int index=b; int a; do{ move=(move+1)%divisor; if(empty[move]) //遇到空值，那么跳出循环 break; a=table[move]%divisor; //a表示x理论上所在的位置的索引 if((a<=index&&index <=index)||(index >D>>m; HashTable h(D); for(int i=0;i >opt>>x; switch(opt) { case 0: tag=h.insert(x); if(tag == -1) cout<<"Existed"<
转载地址：http://sfwzi.baihongyu.com/