#include<iostream> #include<time.h> #include<string> #include<math.h> #include<stdio.h> #define m 15//哈希表的表长 #define NullKey 0 //单元为空的标记 using namespace std; int HT[m] = {}, HC[m] = {};//HT是哈希表，HC是统计每个元素的插入时候的查找次数。并且初始化。 int H(int key) {//哈希函数 return key % 13; } //线性探测，既可以找到空的地方，没空的地方也可以找到是哈希表之前是否有这个值，查找中，如果第一次没找到，则调用这个函数，继续往下查找。 int Linedetece(int HT[], int H0, int key, int& cnt) {//线性探测法 参数：哈希表，之前哈希函数计算出来的下标值，关键字，查找次数 int HI; for (int i = 1; i < m; ++i) { cnt++; HI = (H0 + i) & m;//按照线性探测法计算下一个哈希地址HI if (HT[HI] == NullKey) { return HI; } else if(HT[HI]==key)//如果找到和这个关键字重复的值，返回该下标 ,,若单元HI中元素的关键字为Key //查找会用到，插入的话不会用到这一步，因为如果插入有重复的会插入失败； { return HI; } } return -1; } //二次探测，既可以找到空的地方，没空的地方也可以找到是哈希表之前是否有这个值，查找中，如果第一次没找到，则调用这个函数，继续往下查找。 int Seconddetect(int HT[], int H0, int key, int& cnt) {//二次探测法。 int HI; for (int i = 1; i <= m/2; ++i) { int i1 = i * i;//右边 int i2 = -i1;//左边 cnt++; HI = (H0 + i1) % m;//按照线性探测法计算下一个哈希地址 if (HT[HI] == NullKey) {//若单元HI为空，则所查元素不存在。 return HI; } else if (HT[HI] == key) {//若单元HI中元素的关键字为Key return HI; } cnt++;//因为一个下标要查左右两次，所以需要两次++; HI = (H0 + i2) % m; if (HI < 0) HI += m;//如果超出左边界。右边界不可能超出，左边界可能变为负数 if (HT[HI] == NullKey) { return HI; } if (HT[HI] == key) { return HI; } } return -1; } //查找，第一种情况：第一次的位置为空， 则插入 第二种情况，第一次位置不为空，被占据，按线性往后找空的插入。都没找到返回0； bool InsertHash(int HT[], int key) { int H0 = H(key); int HI = -1, cnt = 1; if (HT[H0] == NullKey) { HC[H0] = 1;//统计查找次数 HT[H0] = key;//若单元H0为空，放入 return true; } else { HI = Linedetece(HT, H0, key, cnt);//找到后面空的下标，或者和自己数字相等的下标，相等的下标情况会在下面的if去掉。 //HI = Seconddetect(HT, H0, key, cnt);线性查找 if ((HI != -1) && (HT[HI] == NullKey)) {//哈希表里面有空值，如果没有空值，则失败， //如果哈希表没满或者该元素没有插入 //因为上面的探测函数有可能找到key值，也会将其下标返回。哈希表不能有重复的值。 HC[HI] = cnt; HT[HI] = key;//若单元H0为空，放入 return true; } } return 0; } void print(int HT[]) { for (int i = 0; i < m; i++) { cout << HT[i] << "\t"; } cout << endl; } //查找，第一种情况，查是不是空，第二种情况，查第一次有没有找到，第三种情况，查哈希表其他位置有没有，第四种情况 返回失败。 int SerachHasn(int HT[], int key) { //在哈希表HT中查找关键字为key的元素，若查找成功，则返回哈希表的单元序号。 int H0 = H(key);//根据哈希函数key计算哈希地址。 int HI, cnt = 1; if (HT[H0] == NullKey) {//若单元H0为空，则所查元素不存在 return -1; } else if(HT[H0]==key){//若单元HO中元素的关键字为key，则查找成功。 cout << "查找成功，比较次数：" << cnt << endl; return 0; } else {//第一次查找不为空，也没找到（是因为之前的元素占据了这个元素应该初始所在位置） HI = Linedetece(HT, H0, key, cnt); if (HT[HI] == key) {//若单元HO中元素的关键字为key，则查找成功。 cout << "查找成功，比较次数：" << cnt << endl; return HI; } else { return -1;//若单元H0为空，则所查元素不存在 } } } int main() { int x;
//memset(HT, 0, sizeof(HT));//将哈希表HT的sizeof（HT）个字节用0替换。 //memset(HT, 0, sizeof(HC)); print(HT); cout << "输入12个关键字，存入哈希表中" << endl; for (int i = 0; i < 12; i++) { cin >> x; if (!InsertHash(HT, x)) { cout << "创建哈希表失败" << endl; return 0; } } cout << "输出哈希表" << endl; print(HT);//输出哈希表 print(HC);//输出记录每个元素查找次数的数组。 cout << "输入要查找的关键字" << endl; cin >> x; int result = SerachHasn(HT, x); if (result == -1) { cout << "没找到"; } else { cout << "在第" << result + 1 << "的位置找到" << endl; } return 0;
}
