B (1038) : DS哈希查找—二次探测再散列

本文主要是介绍B (1038) : DS哈希查找—二次探测再散列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

一、题目描述

定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。

---

二、输入与输出

1.输入

3
11 8
18 25 11 19 20 3 10 13
7
17
26
2
0
25
24
11
11 6
9 23 26 10 16 18
9
10
24
16
13
6
4
8
10
24
11 3
0 3 28
14
27
27
21
14
22
24
7
7
28
16
1
25
1
3
19 17
27 28 26 25 6 11 18 22 29 20 0 19 14 13 10 23 15
9
16
5
21
14
26
18
10
21
8
11 7

---

2.输出

对每组测试数据，输出以下信息：

构造的哈希表信息，数组中没有关键字的位置输出NULL

对k个待查关键字，分别输出：

0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）

11 NULL 13 25 3 NULL NULL 18 19 20 10
0 1
0 2
0 3
0 2
1 1 4
0 3
1 1 1
NULL 23 NULL NULL 26 16 NULL 18 NULL 9 10
1 1 11
0 1
1 1 6
0 1
0 1
0 3
0 1
1 1 11
0 1
0 NULL NULL 3 NULL NULL 28 NULL NULL NULL NULL
0 1
0 1
0 1
0 2
0 2
0 1
0 1
0 1
1 1 7
0 1
0 1
0 2
0 1
1 1 4

---

三、参考代码

#include <iostream>
#include <string>
#include<queue>
using namespace std;class HashList
{
public:int sum1, sum2;//sum1 表长  sum2 数据个数int* arr;HashList(){}HashList(int s1 ,int s2):sum1(s1),sum2(s2){arr = new int[s1];for (int i = 0; i < s1; i++){arr[i] = -1;}while (sum2--)//插入数据{int num;cin >> num;int di = 1;int index = num % 11;if (arr[index] == -1){arr[index] = num;continue;}while (1){int t1 = ((index + di * di) % sum1) % sum1;int t2 = ((index - di * di) % sum1) % sum1;while (t2 < 0){t2 += sum1;}//t2可能为负数，防止爆表if (arr[t1] == -1){arr[t1] = num;break;}else if (arr[t2] == -1){arr[t2] = num;break;}else{di++;}}}}void pri(){for (int i = 0; i < sum1; i++){if (arr[i] == -1){cout << "NULL";}else{cout << arr[i];}if (i == sum1 - 1){cout << endl;}else{cout << " ";}}}void FindNum(){int num;cin >> num;int findi = num % 11;int di = 1;int times = 1;if (arr[findi] == -1){cout << "0 1" << endl;}else if(arr[findi] == num){cout << "1 1 " << findi + 1 << endl;}else{while (1){times++;int t1 = ((findi + di * di) % sum1) % sum1;int t2 = ((findi - di * di) % sum1) % sum1;while (t2 < 0){t2 += sum1;}//t2可能为负数，防止爆表if (arr[t1] == num){cout << "1 " << times << " " << t1 + 1 << endl;break;}else if (arr[t1] == -1){cout << "0 " << times << endl;break;}times++;if (arr[t2] == num){cout << "1 " << times << " " << t2 + 1 << endl;break;}else if (arr[t2] == -1){cout << "0 " << times << endl;break;}di++;if (di > (sum1 / 2)){cout << "0 " << times << endl;break;}}}}
};int main()
{int sum;cin >> sum;while (sum--){int s1, s2;cin >> s1 >> s2;HashList h(s1, s2);h.pri();int s3;cin >> s3;while (s3--){h.FindNum();}}
}

---

这篇关于B (1038) : DS哈希查找—二次探测再散列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---