山东大学数据结构与算法实验8散列表（线性开型寻址/链表散列）_数据结构

a : 线性开型寻址

题目描述

要求

使用线性开型寻址实现

描述

给定散列函数的除数 d 和操作数 m，输出每次操作后的状态。
有以下三种操作：

插入 x，若散列表已存在 x，输出“existed”，否则插入 x 到散列表中，输出所在的下标。
查询 x，若散列表不含有 x，输出“-1”，否则输出 x 对应下标。
删除 x，若散列表不含有 x，输出“not found”，否则输出删除 x 过程中移动元素的个数。

实验目的

1、掌握散列表结构的定义和实现。

2、掌握散列表结构的应用。

输入输出格式

输入：

第一行两个整数d，m。分别代表散列函数的除数d和操作数m。

接下来m行，每行两个整数opt和x，分别代表操作类型和操作数。

若opt为0，代表插入x；

若opt为1，代表查询x；

若opt为2，代表删除x。

输出：

按需输出。

数据结构与算法描述

先构造一个散列表类，插入函数先判断该数散列表中是否存在，如果不存在则从插入数的起始桶开始遍历，找到空桶后插入。

class hashtable {
private:
	int divisor;//除数
	int* table;//散列表
public:
	hashtable(int thedivisor ) {
		divisor = thedivisor;
		table = new int[divisor];
		for (int i = 0; i < divisor; i++) {//初始化为-1
			table[i] = -1;
		}
	}
	~hashtable() { delete[] table; }
	void insert(int x); 
	void find(int x);
	void deletes(int x);
};
void hashtable::insert(int x) {//插入
	for (int i = 0; i < divisor; i++) {//是否存在
		if (x == table[i]) {
			cout << "existed" << endl;
			return;
		}
	}
	int s;
	s = x % divisor;//起始桶
	int i = s;
	do {
		if (table[i] == -1) {//找到空桶插入，输出下标
			table[i] = x;
			cout << i << endl;
			break;
		}
		else {
			i = (i + 1) % divisor;
		}
	} while (i != s);
}

查询函数从输入数的起始桶开始编列判断是否有。

void hashtable::find(int x) {//查询
	int s = x % divisor;//起始桶
	int j = s;
	int b = 0;//判断是否有x
	do {
		if (table[j] == x) {//有输出下标
			cout << j << endl;
			b = 1;
			break;
		}
		else {
			j = (j + 1) % divisor;
		}
	} while (j != s && table[j] != -1);
	if (b==0) {//没有输出-1
		cout << -1 << endl;
	}
}

删除函数，先判断散列表中是否存在，如果存在将要删除的数改为-1，并记录删除的位置。从删除的位置的下一个开始循环遍历。如果遇到空桶则直接跳出循环，如果是一下几种情况则用continue结束本轮循环，进行下一个循环。（1）遍历到的数恰好在起始桶；（2）删除的遍历到的数的起始桶在删除空位之后，且遍历到的数位置在自己的起始桶之后；（3）遍历的位置在删除空位的前面，遍历的位置在删除数的起始桶前；（4）删除数的起始桶在删除的空位后，删除的空位在遍历的数前。

void hashtable::deletes(int x) {//删除
	int s = x % divisor;//起始桶
	int j = s;
	int b = 0;//判断是否存在
	do {
		if (table[j] == x) {//如果存在删除x，即改为-1
			table[j] = -1;
			b = 1;
			break;
		}
		else {
			j = (j + 1) % divisor;
		}
	} while (j != s && table[j] != -1);
	if (b==0) {//如果没有输出 "not found"
		cout << "not found" << endl;
		return;
	}
	s = j;//删除后的空位（-1处）
	j = (j + 1) % divisor;//删除的下一个位置
	int k = s;//删除数的下标
	int sum = 0;
	for (int i = j; i != (j + divisor-1)%divisor; i=(i+1)%divisor) {//从删除的下一个位置，遍历整个散列表
		if (table[i] == -1) {//遇到空桶直接跳出循环
			break;
		}
		int x2 = table[i];//遍历到的数
		if (i == (x2 % divisor) || ((x2%divisor)> s)&&i> (x2 % divisor)) {
			continue;//当该数恰好在起始桶||删除的遍历到的数的起始桶在删除空位之后，且x2在起始桶之后
		}
		else {
			if ( i < s&& i>(x2 % divisor)) {
				continue;//遍历的位置在删除空位的前面，遍历的位置在删除数的起始桶前
			}
			if ((x2 % divisor) > s && s > i) {
				continue;//删除数的起始桶在删除的空位后，删除的空位在遍历的数前
			}
			int a = i;
			sum++;//除了以上的情况都要移动所以++
			while (table[(a + divisor-1) % divisor]!=-1  ) {
				a = (a + divisor - 1) % divisor;//从i开始向前遍历，直到有空位置
			}
			table[(a + divisor - 1) % divisor] = x2;//移动到该空位置
			table[i] = -1;//原位置改为空
			s = i;//将删除后空的位置改为此处
		}
	}
	cout << sum << endl;//循环结束输出统计的移动个数
}

除了以上几种情况都要移动，从遍历所在的位置一次向前找到空位插入，并将删除后的空位置改为此处被移动的原位置。整个循环结束后输出统计的移动的个数。

测试结果

完整代码（含注释）

#include<iostream>
using namespace std;
class hashtable {
private:
	int divisor;//除数
	int* table;//散列表
public:
	hashtable(int thedivisor ) {
		divisor = thedivisor;
		table = new int[divisor];
		for (int i = 0; i < divisor; i++) {//初始化为-1
			table[i] = -1;
		}
	}
	~hashtable() { delete[] table; }
	void insert(int x); 
	void find(int x);
	void deletes(int x);
};
void hashtable::insert(int x) {//插入
	for (int i = 0; i < divisor; i++) {//是否存在
		if (x == table[i]) {
			cout << "existed" << endl;
			return;
		}
	}
	int s;
	s = x % divisor;//起始桶
	int i = s;
	do {
		if (table[i] == -1) {//找到空桶插入，输出下标
			table[i] = x;
			cout << i << endl;
			break;
		}
		else {
			i = (i + 1) % divisor;
		}
	} while (i != s);
}
void hashtable::find(int x) {//查询
	int s = x % divisor;//起始桶
	int j = s;
	int b = 0;//判断是否有x
	do {
		if (table[j] == x) {//有输出下标
			cout << j << endl;
			b = 1;
			break;
		}
		else {
			j = (j + 1) % divisor;
		}
	} while (j != s && table[j] != -1);
	if (b==0) {//没有输出-1
		cout << -1 << endl;
	}
}
void hashtable::deletes(int x) {//删除
	int s = x % divisor;//起始桶
	int j = s;
	int b = 0;//判断是否存在
	do {
		if (table[j] == x) {//如果存在删除x，即改为-1
			table[j] = -1;
			b = 1;
			break;
		}
		else {
			j = (j + 1) % divisor;
		}
	} while (j != s && table[j] != -1);
	if (b==0) {//如果没有输出 "not found"
		cout << "not found" << endl;
		return;
	}
	s = j;//删除后的空位（-1处）
	j = (j + 1) % divisor;//删除的下一个位置
	int k = s;//删除数的下标
	int sum = 0;
	for (int i = j; i != (j + divisor-1)%divisor; i=(i+1)%divisor) {//从删除的下一个位置，遍历整个散列表
		if (table[i] == -1) {//遇到空桶直接跳出循环
			break;
		}
		int x2 = table[i];//遍历到的数
		if (i == (x2 % divisor) || ((x2%divisor)> s)&&i> (x2 % divisor)) {
			continue;//当该数恰好在起始桶||删除的遍历到的数的起始桶在删除空位之后，且x2在起始桶之后
		}
		else {
			if ( i < s&& i>(x2 % divisor)) {
				continue;//遍历的位置在删除空位的前面，遍历的位置在删除数的起始桶前
			}
			if ((x2 % divisor) > s && s > i) {
				continue;//删除数的起始桶在删除的空位后，删除的空位在遍历的数前
			}
			int a = i;
			sum++;//除了以上的情况都要移动所以++
			while (table[(a + divisor-1) % divisor]!=-1  ) {
				a = (a + divisor - 1) % divisor;//从i开始向前遍历，直到有空位置
			}
			table[(a + divisor - 1) % divisor] = x2;//移动到该空位置
			table[i] = -1;//原位置改为空
			s = i;//将删除后空的位置改为此处
		}
	}
	cout << sum << endl;//循环结束输出统计的移动个数
}
int main() {
	int d, m;
	cin >> d >> m;
	hashtable h(d);
	for (int i = 0; i < m; i++) {
		int opt, x;
		cin >> opt >> x;
		if (opt == 0) {
			h.insert(x);
		}
		else if (opt == 1) {
			h.find(x);
		}
		else if (opt == 2) {
			h.deletes(x);
		}
	}
	return 0;
}

b : 链表散列

题目描述

要求

使用链表散列方式

描述

给定散列函数的除数 d 和操作数 m，输出每次操作后的状态。

有以下三种操作：

插入 x，若散列表已存在 x，输出"existed"
查询 x，若散列表不含有 x，输出"not found"，否则输出 x 所在的链表长度
删除 x，若散列表不含有 x，输出"delete failed"，否则输出 x 所在链表删除 x 后的长度

输入输出格式

输入：

第一行两个整数d(1<=d<=3000)和m(1<=m<=3000)，其中d为散列函数的除数，m为操作数。

接下来的m行，每行两个整数opt和x，分别代表操作类型和操作数。

若opt为0，则代表向散列表中插入x；

若opt为1，代表查询散列表中x是否存在；

若opt为2，(如果散列表中含有x)，删除x。

输出：

按需输出。

数据结构与算法描述

构造一个节点结构体，和一个节点类，散列表类。将一个链表类chain* table作为散列表的私有成员，方便调用。

struct chainnode {//节点
	int element;
	chainnode* next;
};
class chain {//链表类
private:
	int listsize;//链表长度
	chainnode* firstnode;//首节点
public:
	chain() {
		listsize = 0;
		firstnode = null;
	}
	void insert(int val);
	int seek(int val);
	int erase(int val);
};
void chain::insert(int val) {//链表插入
	if (listsize == 0) {//插入的第一个数
		chainnode* newnode = new chainnode();
		newnode->element = val;
		newnode->next = firstnode;
		firstnode = newnode;
	}
	else {
		chainnode* p = firstnode;
		while (p->next != null) {//找到最后节点
			p = p->next;
		}
		chainnode* newnode = new chainnode();
		newnode->element = val;
		newnode->next = null;
		p->next = newnode;
	}
	listsize++;
}
int chain::seek(int val) {//链表查找
	chainnode* seeknode = firstnode;
	while (seeknode != null && seeknode->element != val) {
		seeknode = seeknode->next;
	}
	if (seeknode == null) {
		return -1;//找不到返回-1
	}
	else {
		return listsize;//找到返回链表长度
	}
}
int chain::erase(int val) {//链表删除
	if (firstnode->element == val) {//如果删除的是首节点
		chainnode* c = firstnode;
		firstnode = firstnode->next;
		delete c;
		listsize--;
		return listsize;//返回删除后的链表长度
	}
	chainnode* deletenode = firstnode;
	while (deletenode->next != null && deletenode->next->element != val) {//找到删除节点的前一个节点
		deletenode = deletenode->next;
	}
	if (deletenode->next == null) {
		return -1;//找不到返回-1
	}
	else {
		chainnode* p = deletenode->next;//要删除的节点
		chainnode* q = p->next;//删除节点的下一个节点
		deletenode->next = q;
		delete p;
		listsize--;
		return listsize;//返回删除后的链表藏毒
	}
}
class hashchain {//散列表类
private:
	chain* table;//链表
	int divisor;//除数
public:
	hashchain(int d) {
		divisor = d;
		table = new chain[divisor];
	}
	~hashchain() { delete[] table; }
	void dinsert(int x);
	void dfind(int x);
	void deletes(int x);
};

在散列表类的插入函数中先找到桶的位置为s然后调用table[s]链表的查找函数，如果不存在再调用table[s]链表的插入函数。

void hashchain::dinsert(int x) {//插入
	int s = x % divisor;
	if (table[s].seek(x) != -1) {//如果已经存在
		cout << "existed" << endl;
		return;
	}
	else {
		table[s].insert(x);
	}
}

散列表类的查询函数，先找到桶的位置为s然后调用table[s]链表的查找函数，如果存在则输出链表查找函数的返回值。

void hashchain::dfind(int x) {//查询
	int s = x % divisor;
	if (table[s].seek(x) == -1) {//如果不存在
		cout << "not found" << endl;
	}
	else {
		cout << table[s].seek(x) << endl;
	}
}

在散列表类的删除函数中先找到桶的位置为s然后调用table[s]链表的查找函数，如果存在再调用table[s]链表的删除函数，并输出返回值。

void hashchain::deletes(int x) {//删除
	int s = x % divisor;
	if (table[s].seek(x) == -1) {//如果不存在
		cout << "delete failed" << endl;
	}
	else {
		cout << table[s].erase(x) << endl;
	}
}

测试结果

完整代码（含注释）

#include<iostream>
using namespace std;
struct chainnode {//节点
	int element;
	chainnode* next;
};
class chain {//链表类
private:
	int listsize;//链表长度
	chainnode* firstnode;//首节点
public:
	chain() {
		listsize = 0;
		firstnode = null;
	}
	void insert(int val);
	int seek(int val);
	int erase(int val);
};
void chain::insert(int val) {//链表插入
	if (listsize == 0) {//插入的第一个数
		chainnode* newnode = new chainnode();
		newnode->element = val;
		newnode->next = firstnode;
		firstnode = newnode;
	}
	else {
		chainnode* p = firstnode;
		while (p->next != null) {//找到最后节点
			p = p->next;
		}
		chainnode* newnode = new chainnode();
		newnode->element = val;
		newnode->next = null;
		p->next = newnode;
	}
	listsize++;
}
int chain::seek(int val) {//链表查找
	chainnode* seeknode = firstnode;
	while (seeknode != null && seeknode->element != val) {
		seeknode = seeknode->next;
	}
	if (seeknode == null) {
		return -1;//找不到返回-1
	}
	else {
		return listsize;//找到返回链表长度
	}
}
int chain::erase(int val) {//链表删除
	if (firstnode->element == val) {//如果删除的是首节点
		chainnode* c = firstnode;
		firstnode = firstnode->next;
		delete c;
		listsize--;
		return listsize;//返回删除后的链表长度
	}
	chainnode* deletenode = firstnode;
	while (deletenode->next != null && deletenode->next->element != val) {//找到删除节点的前一个节点
		deletenode = deletenode->next;
	}
	if (deletenode->next == null) {
		return -1;//找不到返回-1
	}
	else {
		chainnode* p = deletenode->next;//要删除的节点
		chainnode* q = p->next;//删除节点的下一个节点
		deletenode->next = q;
		delete p;
		listsize--;
		return listsize;//返回删除后的链表藏毒
	}
}
class hashchain {//散列表类
private:
	chain* table;//链表
	int divisor;//除数
public:
	hashchain(int d) {
		divisor = d;
		table = new chain[divisor];
	}
	~hashchain() { delete[] table; }
	void dinsert(int x);
	void dfind(int x);
	void deletes(int x);
};
void hashchain::dinsert(int x) {//插入
	int s = x % divisor;
	if (table[s].seek(x) != -1) {//如果已经存在
		cout << "existed" << endl;
		return;
	}
	else {
		table[s].insert(x);
	}
}
void hashchain::dfind(int x) {//查询
	int s = x % divisor;
	if (table[s].seek(x) == -1) {//如果不存在
		cout << "not found" << endl;
	}
	else {
		cout << table[s].seek(x) << endl;
	}
}
void hashchain::deletes(int x) {//删除
	int s = x % divisor;
	if (table[s].seek(x) == -1) {//如果不存在
		cout << "delete failed" << endl;
	}
	else {
		cout << table[s].erase(x) << endl;
	}
}
int main() {
	int d, m;
	cin >> d >> m;
	hashchain h(d);
	for (int i = 0; i < m; i++) {
		int opt, x;
		cin >> opt >> x;
		if (opt == 0) {
			h.dinsert(x);
		}
		else if (opt == 1) {
			h.dfind(x);
		}
		else if (opt == 2) {
			h.deletes(x);
		}
	}
	return 0;
}

山东大学数据结构与算法实验8散列表（线性开型寻址/链表散列）

2024年08月02日 • 数据结构 •我要评论

a : 线性开型寻址

题目描述

要求

描述

实验目的

输入输出格式

数据结构与算法描述

测试结果

完整代码（含注释）

b : 链表散列

题目描述

要求

描述

输入输出格式

数据结构与算法描述

测试结果

完整代码（含注释）

相关文章:

数据结构与算法：7种必须会的排序以及3种非基于比较排序

12. 【数据结构】冒泡插入希尔选择堆快排归并非递归计数基数排序

【数据结构与算法】3.(单向、无向、带权)图，广度、深度优先搜索，贪心算法

刷题计划 day4 【双指针、快慢指针、环形链表】链表下

【数据结构】汇总二、线性表（逻辑结构、物理（存储）结构、基本操作、1.顺序表2.单链表3.双链表4.循环链表5.静态链表6.顺序表与链表的对比不同）

发表评论


验证码：

山东大学数据结构与算法实验8散列表（线性开型寻址/链表散列）

2024年08月02日 • 数据结构 •我要评论

a : 线性开型寻址

题目描述

要求

描述

实验目的

输入输出格式

数据结构与算法描述

测试结果

完整代码（含注释）

b : 链表散列

题目描述

要求

描述

输入输出格式

数据结构与算法描述

测试结果

完整代码（含注释）

相关文章:

数据结构与算法：7种必须会的排序以及3种非基于比较排序

12. 【数据结构】 冒泡插入希尔选择堆快排归并非递归计数基数排序

【数据结构与算法】3.(单向、无向、带权)图，广度、深度优先搜索，贪心算法

刷题计划 day4 【双指针、快慢指针、环形链表】链表下

【数据结构】汇总二、线性表（逻辑结构、物理（存储）结构、基本操作、1.顺序表2.单链表3.双链表4.循环链表5.静态链表6.顺序表与链表的对比不同）

发表评论

12. 【数据结构】冒泡插入希尔选择堆快排归并非递归计数基数排序