Description
使用线性探测法(Linear Probing)可以解决哈希中的冲突问题，其基本思想是：设哈希函数为h(key) = d, 并且假定哈希的存储结构是循环数组, 则当冲突发生时, 继续探测d+1, d+2…, 直到冲突得到解决.
例如, 现有关键码集为 {47，7，29，11，16，92，22，8，3}，
设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；采用线性探测法处理冲突。建哈希表如下：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
11 |
22 |
47 |
92 |
16 |
3 |
7 |
29 |
8 |
现在给定哈希函数为Hash(key)= key mod m，要求按照上述规则, 使用线性探测法处理冲突.要求建立起相应哈希表，并按要求打印。
Input
仅有一个测试用例, 第1行为整数n与m（1 <= n, m <= 10000）， n代表key的总数, m代表哈希表的长度, 并且令哈希函数为: Hash(key) = key mod m.
接下来n行，每行一个整数，代表一个key。Key与key两两不相同 ( 0 <= key <= 10, 000)。
Output
输出建立好的hash表，比如下表
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
11 |
22 |
47 |
92 |
16 |
3 |
7 |
29 |
8 |
应输出
0#11
1#22
2#NULL
3#47
4#92
5#16
6#3
7#7
8#29
9#8
10#NULL
想法：要注意的地方就是循环数组那里。。。。其他的就很基本了。。
#include <iostream> using namespace std; int main(int argc, char const *argv[])
{
int n, m, modNum, temp;
int* hash;
int * num; cin >> n >> m;
hash = new int[m];
num = new int[n + ]; for (int i = ; i != m; i++)
hash[i] = -; for (int i = ; i != n; i++) {
cin >> temp;
int modNum = temp % m;
if (hash[modNum] == -) {
hash[modNum] = temp;
} else {
int j = modNum + ;
j %= m;//循环数组
for (;j != m; j++) {
if (hash[j] == -) {
hash[j] = temp;
break;
}
j %= m;
}
}
} for (int i = ; i != m; i++) {
if (hash[i] != -)
cout << i << "#" << hash[i] << endl;
else
cout << i << "#NULL" << endl;
}
delete []hash;
return ;
}