散列查找实验（开散列） 题目编号: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
内存阀值:102400K 耗时阀值:5000MS

代码

#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) ;
			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;