SWUSTOJ #1013 哈希表（开放定址法处理冲突）
SWUSTOJ #1013 哈希表（开放定址法处理冲突）
- 题目
- 输入
- 输出
- 样例输入
- 样例输出
- 源代码
题目
采用除留余数法（H（key）=key %n）建立长度为n的哈希表，处理冲突用开放定址法的线性探测。
输入
第一行为哈希表的长度n；
第二行为关键字的个数；
第三行为关键字集合；
第四行为要查找的数据。
输出
如果查找成功，输出关键字所哈希表中的地址和比较次数；
如果查找不成功，输出-1。
样例输入
13
11
16 74 60 43 54 90 46 31 29 88 77
16
样例输出
3,1
源代码
#include <iostream>
#include <vector>
#include <list>using namespace std;int flag = 0;
int Count = 1;
class hashmap
{
public:hashmap(int size = 1000){arr.resize(size);sizement = size;currentsize = 0;}int hash(int n){int hashval = n%sizement;return hashval;}void put(int n){int pos = hash(n);if (arr[pos]==NULL)arr[pos]=n;else{while (arr[pos] != NULL){pos++;if (pos > sizement - 1)pos = 0;}arr[pos] = n;}currentsize++;}int get(int n){int x;int pos = hash(n);for (int i = pos; i < sizement;i++){x = arr[i];if (x == n){break;}else{Count++;}}if (x == n){flag = 1;return pos;}else{return -1; }}
private:int currentsize;int sizement;vector<int> arr;
};int main()
{int m;cin >> m;int n;cin >> n;hashmap H(m);int x;for (int i = 0; i < n; i++){cin >> x;H.put(x);}int k;cin >> k;int pos = H.get(k);if (flag == 1){cout << pos << "," << Count;}else{cout << -1;}return 0;
}
SWUSTOJ #1013 哈希表（开放定址法处理冲突）
SWUSTOJ #1013 哈希表（开放定址法处理冲突）
- 题目
- 输入
- 输出
- 样例输入
- 样例输出
- 源代码
题目
采用除留余数法（H（key）=key %n）建立长度为n的哈希表，处理冲突用开放定址法的线性探测。
输入
第一行为哈希表的长度n；
第二行为关键字的个数；
第三行为关键字集合；
第四行为要查找的数据。
输出
如果查找成功，输出关键字所哈希表中的地址和比较次数；
如果查找不成功，输出-1。
样例输入
13
11
16 74 60 43 54 90 46 31 29 88 77
16
样例输出
3,1
源代码
#include <iostream>
#include <vector>
#include <list>using namespace std;int flag = 0;
int Count = 1;
class hashmap
{
public:hashmap(int size = 1000){arr.resize(size);sizement = size;currentsize = 0;}int hash(int n){int hashval = n%sizement;return hashval;}void put(int n){int pos = hash(n);if (arr[pos]==NULL)arr[pos]=n;else{while (arr[pos] != NULL){pos++;if (pos > sizement - 1)pos = 0;}arr[pos] = n;}currentsize++;}int get(int n){int x;int pos = hash(n);for (int i = pos; i < sizement;i++){x = arr[i];if (x == n){break;}else{Count++;}}if (x == n){flag = 1;return pos;}else{return -1; }}
private:int currentsize;int sizement;vector<int> arr;
};int main()
{int m;cin >> m;int n;cin >> n;hashmap H(m);int x;for (int i = 0; i < n; i++){cin >> x;H.put(x);}int k;cin >> k;int pos = H.get(k);if (flag == 1){cout << pos << "," << Count;}else{cout << -1;}return 0;
}
发布评论