当前位置：首页 > news >正文

散列查找实验（开散列）题目编号:583

news 2025/8/6 2:51:46

题目描述

请设计一个整型开散列表，散列函数为除留余数法，其中散列表的长度、除留余数法的模和关键码的个数由键盘输入，再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中进行查找，输出查找结果采用头插法。

输入描述

各个命令以及相关数据的输入格式如下：
第一行输入闭散列表的长度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
内存阀值:102400K 耗时阀值:5000MS

代码

#include <iostream>#define MAXSIZE 100using 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) ;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 ;}}return 0;