前一篇博客中提到解决散列冲突的方法为分离链接法，它的装填因子为1，每次插入一个元素就申请一个空间，但是，开放定址不一样， 所谓的开放定址就是散列一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入，具体寻找空地址的方法有线性探测法，平方探测法，双散列等等，注意，对于开放定址来说，装填因子应该小于0.5.
使用平方探测解决冲突，代码如下：
#includeusing namespace std;#define MinTablesize 10typedef unsigned int Index;typedef Index Position;struct Hashtal;typedef struct Hashtal *Hashtable;enum KindOfEntry //枚举类型，只能是其中的一个值{ Legitimate,Empty,Delete};struct HashEntry{ int Element; enum KindOfEntry Info;};typedef struct HashEntry Cell;struct Hashtal{ int TableSize; Cell *Thecells;};int Hash (int x,Hashtable H) //散列函数{ return x % H->TableSize;}int NextPrime (int Key) // 寻找Key后的第一个素数{ if(Key == 1 || Key == 2) return Key; bool flag = 0; int pre_Key; while(!flag) { pre_Key = Key; for(int i = 2; i != Key; ++i) { if(Key % i == 0) //Key不是素数 { Key++; break; } } if(pre_Key == Key) //说明Key没有改变 flag = 1; else flag = 0; } return Key;}Hashtable InitTable(int Tablesize){ Hashtable H; if(Tablesize < MinTablesize) { cout << "Table is too small" << endl; return NULL; } //创建散列表 H = (Hashtable)malloc(sizeof(struct Hashtal)); if(H == NULL) cout << "out of space " << endl; H->TableSize = NextPrime(Tablesize); //大小为Tablesize后的第一个素数 H->Thecells = (Cell*)malloc(sizeof(Cell) * H->TableSize ); if(H->Thecells == NULL) cout << "out of space " << endl; for (int i = 0; i != H->TableSize; ++i) H->Thecells[i].Info = Empty; //每个元素都标记为空 return H; }Position Find (int Key , Hashtable H){ Position CurrPos; int CollNum; CollNum = 0; CurrPos = Hash(Key,H); while(H->Thecells[CurrPos].Info != Empty && H->Thecells[CurrPos].Element != Key) //找不到时返回一个空单元 { CurrPos += 2 * (++CollNum) - 1; //使用平方探测散列法 if(CurrPos >= H->TableSize ) CurrPos -= H->TableSize; } return CurrPos;}void Insert(int Key,Hashtable H){ Position Pos; Pos = Find(Key,H); //看找不找的到，找到就算了，找不到就插入 if(H->Thecells[Pos].Info != Legitimate) // { H->Thecells[Pos].Element = Key; H->Thecells[Pos].Info = Legitimate; }}Hashtable Rehash (Hashtable H) //再散列，把表的大小放大到原来的2倍，再把原来的元素插入到新散列表中{ int Oldsize; Cell *Oldcells; Oldcells = H->Thecells; Oldsize = H->TableSize; H = InitTable(2 * Oldsize); for (int i = 0; i != Oldsize; ++i) { if(Oldcells[i].Info == Legitimate) Insert(Oldcells[i].Element, H); } free(Oldcells); return H;}int main (){ Hashtable H = InitTable(10); Insert(10,H); cout << H->Thecells [Find(10,H)].Element << endl; return 0;}
这些数据结构的思想都值得我们借鉴。
夜深了，，，
我们都是方鸿渐，不讨人厌，但也全无用。