基于开放地址法的哈希表（散列表）

#include<iostream>
#include<string>
#include<cctype>
#include<fstream>
#include<algorithm>
using namespace std;
const int MaxSize = 97;
typedef struct Element {
	int info;//info的用处是用来标记元素是否被删除过
	int num;
}Element;
typedef struct HashTable {
	int tablesize;//散列表的大小
	Element *restore;
}H,*Hash;
Hash create(int size) { //创建一个大小为size的散列表
	Hash hr = new struct HashTable;
	if (hr == NULL) cout << "空间溢出";
	hr->tablesize = size;
	hr->restore = (Element*)malloc(size * sizeof(Element));
	for (int i = 0; i < hr->tablesize; i++) {
		hr->restore[i].info = 0;//info=1时表示表被占用，info=0时表示空，info=-1时表示元素被删除
	}
	return hr;
}
int hash_search(int number, Hash h)//构造散列函数
{
	return number % (h->tablesize);
}
int find_position(int key, Hash h)//平方探测
{
	int cnum = 0;//记录冲突次数
	int judge = 0;
	for (int i = 0; i < h->tablesize; i++) {
		if (h->restore[i].info == 0||h->restore[i].info==-1) {
			judge = 1; break;
		}
	}
	int pos1, pos2;
	int position = hash_search(key, h);
	int newpos = position;
	while (h->restore[newpos].info == 1) {
		cnum++;
		if (cnum % 2 == 0) {
			newpos = position + (cnum + 1) / 2 * (cnum + 1) / 2;
			while (newpos >= h->tablesize) newpos -= h->tablesize;
		}
		else {
			newpos = position - (cnum) / 2 * (cnum) / 2;
			while (newpos < 0) newpos += h->tablesize;
		}
	}
	if (judge==0) cout << "散列表已满无法找到空位" << endl;
	return newpos;
}
void insert(int key, Hash h) {
	int pos = find_position(key, h);
	h->restore[pos].num = key;
	h->restore[pos].info = 1;

}
void delete_number(int key, Hash h) {
	for (int i = 0; i < h->tablesize; i++) {
		if (h->restore[i].num == key) {
			h->restore[i].info = -1;
			break;
		}
	}
}
int find_a_key(int key, Hash h) {//查找一个元素是否在散列表中
	int position = hash_search(key, h);
	int newpos = position;
	int cnum = 0;
	while (h->restore[newpos].num != key) {
		cnum++;
		if( (h->restore[newpos].info == 0)||(h->restore[newpos].info==-1&&h->restore[newpos].num==key) ){
			cout << "该元素不在表中"; break;
		}
		if (cnum % 2 == 0) {
			newpos = position + (cnum + 1) / 2 * (cnum + 1) / 2;
			while (newpos >= h->tablesize) newpos -= h->tablesize;
		}
		else {
			newpos = position - (cnum) / 2 * (cnum) / 2;
			while (newpos < 0) newpos += h->tablesize;
		}
	}
	return newpos;
}
int main()
{
	Hash h = create(97);
	int n; 
	cout << "请输入数字数目 ";
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		insert(a, h);
	}
	delete_number(32, h);
	cout << find_a_key(204, h);
}