【数据结构】哈希表

Alex_Shen
2020-12-30 / 0 评论 / 0 点赞 / 78 阅读 / 4,580 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: DS哈希查找—线性探测再散列

题目描述

定义哈希函数为H(key) = key%11,输入表长(大于、等于11)。输入关键字集合,用线性探测再散列构建哈希表,并查找给定关键字。
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求

输入

测试次数t
每组测试数据为:
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字

输出

对每组测试数据,输出以下信息:
构造的哈希表信息,数组中没有关键字的位置输出NULL
对k个待查关键字,分别输出:0或1(0—不成功,1—成功)、比较次数、查找成功的位置(从1开始)

样例输入

1
12 10
22 19 21 8 9 30 33 4 15 14
4
22
56
30
17

样例输出

22 30 33 14 4 15 NULL NULL 19 8 21 9
1 1 1
0 6
1 6 2
0 1

题解

#include<iostream>
using namespace std;

int* HashTable;

void insert(int data, int m) {
	int index = data % 11;
	while (HashTable[index] != -1)
		index = (index + 1) % m;
	HashTable[index] = data;
}

void search(int num, int m) {
	int cnt = 1;
	int index = num % 11;
	bool isFind = true;
	while (HashTable[index] != num) {
		if (HashTable[index] == -1) {
			isFind = false;
			break;
		}
		cnt++;
		index = (index + 1) % m;
	};
	if (isFind)
		cout << 1 << ' ' << cnt << ' ' << index + 1 << endl;
	else
		cout << 0 << ' ' << cnt << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int m, n;
		cin >> m >> n;
		HashTable = new int[m];
		for (int i = 0; i < m; i++)
			HashTable[i] = -1;
		while (n--) {
			int data;
			cin >> data;
			insert(data, m);
		}
		for (int i = 0; i < m; i++) {
			if (HashTable[i] == -1)
				cout << "NULL ";
			else
				cout << HashTable[i] << ' ';
		}
		cout << endl;
		int k;
		cin >> k;
		while (k--) {
			int num;
			cin >> num;
			search(num, m);
		}
	}
	return 0;
}

问题 B: DS哈希查找—二次探测再散列

题目描述

定义哈希函数为H(key) = key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。

输入

测试次数t
每组测试数据格式如下:
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字

输出

对每组测试数据,输出以下信息:
构造的哈希表信息,数组中没有关键字的位置输出NULL
对k个待查关键字,分别输出:
0或1(0—不成功,1—成功)、比较次数、查找成功的位置(从1开始)

样例输入

1
12 10
22 19 21 8 9 30 33 4 41 13
4
22
15
30
41

样例输出

22 9 13 NULL 4 41 NULL 30 19 8 21 33
1 1 1
0 3
1 3 8
1 6 6

题解

#include<iostream>
#include<cmath>
using namespace std;

int* HashTable;

void insert(int data, int m) {
	int cnt = 1;
	int index = data % 11;
	int temp = index;
	while (HashTable[temp] != -1) {
		int i = pow(-1, cnt + 1) * pow((int)(cnt + 1) / 2, 2);
		cnt++;
		temp = (index + i + m) % m;
	}
	HashTable[temp] = data;
}

void search(int num, int m) {
	int cnt = 1;
	int index = num % 11;
	int temp = index;
	bool isFind = true;
	while (HashTable[temp] != num) {
		if (HashTable[temp] == -1) {
			isFind = false;
			break;
		}
		int i = pow(-1, cnt + 1) * pow((int)(cnt + 1) / 2, 2);
		cnt++;
		temp = (index + i + m) % m;
	};
	if (isFind)
		cout << 1 << ' ' << cnt << ' ' << temp + 1 << endl;
	else
		cout << 0 << ' ' << cnt << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int m, n;
		cin >> m >> n;
		HashTable = new int[m];
		for (int i = 0; i < m; i++)
			HashTable[i] = -1;
		while (n--) {
			int data;
			cin >> data;
			insert(data, m);
		}
		for (int i = 0; i < m; i++) {
			if (HashTable[i] == -1)
				cout << "NULL ";
			else
				cout << HashTable[i] << ' ';
		}
		cout << endl;
		int k;
		cin >> k;
		while (k--) {
			int num;
			cin >> num;
			search(num, m);
		}
	}
	return 0;
}

问题 C: DS哈希查找--链地址法

题目描述

给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和表头插入
如果首次查找失败,就把数据插入到相应的位置中
实现哈希查找功能

输入

第一行输入n,表示有n个数据
第二行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第三行输入t,表示要查找t个数据
从第四行起,每行输入一个要查找的数据,都是正整数

输出

每行输出对应数据的查找结果

样例输入

6
11 23 39 48 75 62
6
39
52
52
63
63
52

样例输出

6 1
error
8 1
error
8 1
8 2

题解

#include<iostream>
#include<cmath>
using namespace std;

class node {
public:
	int key;
	node* next;
	node() {
		next = NULL;
	}
};

node** HashTable;

void insert(int data) {
	int index = data % 11;
	node* temp = new node;
	temp->key = data;
	temp->next = HashTable[index]->next;
	HashTable[index]->next = temp;
}

void search(int data) {
	int index = data % 11;
	int cnt = 0;
	node* p = HashTable[index];
	while (p) {		
		if (p->key == data)
			break;
		else {
			p = p->next;
		}
		cnt++;
	}
	if (p)
		cout << index << ' ' << cnt << endl;
	else {
		cout << "error" << endl;
		insert(data);
	}
}

int main() {
	int n;
	cin >> n;
	HashTable = new node*[11];
	for (int i = 0; i < 11; i++)
		HashTable[i] = new node;
	while (n--) {
		int data;
		cin >> data;
		insert(data);
	}
	int t;
	cin >> t;
	while (t--) {
		int data;
		cin >> data;
		search(data);
	}
	return 0;
}

问题 D: DS哈希查找与增补

题目描述

给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和表尾插入
如果首次查找失败,就把数据插入到相应的位置中
实现哈希查找与增补功能

输入

第一行输入n,表示有n个数据
第二行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第三行输入t,表示要查找t个数据
从第四行起,每行输入一个要查找的数据,都是正整数

输出

每行输出对应数据的查找结果,每个结果表示为数据所在位置[0,11)和查找次数,中间用空格分开

样例输入

6
11 23 39 48 75 62
6
39
52
52
63
63
52

样例输出

6 1
error
8 1
error
8 2
8 1

题解

#include<iostream>
#include<cmath>
using namespace std;

class node {
public:
	int key;
	node* next;
	node() {
		next = NULL;
	}
};

node** HashTable;

void insert(int data) {
	int index = data % 11;
	node* temp = new node;
	temp->key = data;
	node* p = HashTable[index];
	while (p->next)
		p = p->next;
	p->next = temp;
}

void search(int data) {
	int index = data % 11;
	int cnt = 0;
	node* p = HashTable[index];
	while (p) {		
		if (p->key == data)
			break;
		else {
			p = p->next;
		}
		cnt++;
	}
	if (p)
		cout << index << ' ' << cnt << endl;
	else {
		cout << "error" << endl;
		insert(data);
	}
}

int main() {
	int n;
	cin >> n;
	HashTable = new node*[11];
	for (int i = 0; i < 11; i++)
		HashTable[i] = new node;
	while (n--) {
		int data;
		cin >> data;
		insert(data);
	}
	int t;
	cin >> t;
	while (t--) {
		int data;
		cin >> data;
		search(data);
	}
	return 0;
}

0

评论区