OJ刷题记录：散列查找实验
散列查找实验（闭散列） 题目编号:582
题目描述： 请设计一个整型闭散列表，散列函数为除留余数法，处理冲突时的探查方法为线性探查法，其中散列表的长度、除留余数法的模和关键码的个数由键盘输入，再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中进行查找，如果找到了输出位置，如果没找到，输出“none”并把该待查值插入到散列表中，如果散列表满输出“full”。
输入描述 各个命令以及相关数据的输入格式如下： 第一行输入闭散列表的长度n 第二行输入除留余数法的模m 第三行输入关键码的个数num 第四行输入num个整型关键码 第五行输入三个待查整型值 输出描述 输出三行，每行格式为： 如果找到待查值，输出找到待查值的位置，如果没找到，输出“none”，并将待查值插入到散列表中，如果散列表满，则输出“full”，每个待查值占一行 输入样例 11 11 9 2 6 8 9 13 17 10 12 20 3 7 11 输出样例 none none full
解题思路： 略。
通关代码：
#include <iostream>
#define MAXSIZE 100
using namespace std;
class Hash {
public:
Hash(int max, int mod);
public:
int Find(int key);
void Insert(int key);
private:
bool isFull();
private:
int arr_[MAXSIZE];
int max_;
int len_;
int mod_;
};
Hash::Hash(int max, int mod):max_(max), mod_(mod) {
len_ = 0;
for (int i = 0; i < max_; i++) {
arr_[i] = -1;
}
}
bool Hash::isFull() {
return len_ == max_ ? true : false;
}
void Hash::Insert(int key) {
if (isFull()) throw "full";
int in = key % mod_;
if (arr_[in] == -1) {
arr_[in] = key;
len_++;
} else {
if (arr_[in] != key) {
while (arr_[in] != -1) {
in = (in + 1) % max_;
if (arr_[in] == key) {
cout << in << endl;
return ;
}
}
arr_[in] = key;
len_++;
}
}
}
int Hash::Find(int key) {
int in = key % mod_;
int res;
if (arr_[in] != -1 && arr_[in] == key) {
res = in;
} else {
Insert(key);
throw "none";
}
return res;
}
int main() {
int max, mod, n, key;
cin >> max >> mod >> n;
Hash h(max, mod);
for (int i = 0; i < n; i++) {
cin >> key;
h.Insert(key);
}
for (int i = 0; i < 3; i++) {
cin >> key;
try {
cout << h.Find(key) << endl;
} catch (const char* str) {
cout << str << endl;
}
}
return 0;
}散列查找实验（开散列） 题目编号:583
题目描述： 请设计一个整型开散列表，散列函数为除留余数法，其中散列表的长度、除留余数法的模和关键码的个数由键盘输入，再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中进行查找，输出查找结果采用头插法。
输入描述 各个命令以及相关数据的输入格式如下： 第一行输入闭散列表的长度n 第二行输入除留余数法的模m 第三行输入关键码的个数num 第四行输入num个整型关键码 第五行输入三个待查整型值 输出描述 输出三行，每行格式为： 如果找到待查值，输出找到待查值的位置，先输出待查值在散列表指针数组中的下标， 再输出待查值在关键码链表中的位置，从1开始，如果没找到，输出“none”，并把待查值 插入到开散列表中 输入样例 11 11 9 2 6 8 9 13 17 10 12 20 11 13 9 输出样例 none 2 1 9 2
解题思路： 同上。
通关代码：
#include <iostream>
#define MAXSIZE 100
using namespace std;
struct KeyNode {
int _key;
KeyNode* _next;
KeyNode(int key):_key(key), _next(NULL) {}
};
class Hash {
public:
Hash(int len, int mod);
~Hash();
public:
void Insert(int key);
void Find(int key);
private:
int getPos(int key);
private:
int len_;
int mod_;
KeyNode* bucket_[MAXSIZE];
};
Hash::Hash(int len, int mod):len_(len), mod_(mod) {
for (int i = 0; i < len_; i++) {
bucket_[i] = NULL;
}
}
Hash::~Hash() {
for (int i = 0; i < len_; i++) {
KeyNode* temp;
for (KeyNode* p = bucket_[i]; p != NULL; p = temp) {
temp = p->_next;
delete p;
}
}
}
void Hash::Insert(int key) {
int in = key % mod_;
KeyNode* temp = new KeyNode(key);
temp->_next = bucket_[in];
bucket_[in] = temp;
}
void Hash::Find(int key) {
int in = key % mod_;
if (bucket_[in] == NULL) {
Insert(key);
throw "none";
}
bool isFind = false;
for (KeyNode* p = bucket_[in]; p != NULL; p = p->_next) {
if (p->_key == key) {
isFind = true;
cout << in << ' ' << getPos(key) << endl;
break;
}
}
if (isFind == false) {
Insert(key);
throw "none";
}
}
int Hash::getPos(int key) {
int in = key % mod_;
int count = 1;
for (KeyNode* p = bucket_[in]; p->_key != key; p = p->_next) {
count++;
}
return count;
}
int main() {
int len, mod, n, key;
cin >> len >> mod >> n;
Hash h(len, mod);
for (int i = 0; i < n; i++) {
cin >> key;
h.Insert(key);
}
for (int i = 0; i < 3; i++) {
cin >> key;
try {
h.Find(key);
} catch (const char* str) {
cout << str << endl;
}
}
return 0;
}