首页 > 编程语言 >山东大学数据结构与算法实验8散列表（线性开型寻址/链表散列）

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

时间：2024-07-20 11:57:12浏览次数：16  
标签：divisor 删除 int 开型 next 链表 table 散列

A : 线性开型寻址

题目描述

要求

使用线性开型寻址实现

描述

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

  1. 插入 x，若散列表已存在 x，输出“Existed”，否则插入 x 到散列表中，输出所在的下标。
  2. 查询 x，若散列表不含有 x，输出“-1”，否则输出 x 对应下标。
  3. 删除 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，输出每次操作后的状态。

有以下三种操作：

  1. 插入 x，若散列表已存在 x，输出"Existed"
  2. 查询 x，若散列表不含有 x，输出"Not Found"，否则输出 x 所在的链表长度
  3. 删除 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;
}

标签：divisor,删除,int,开型,next,链表,table,散列
From： https://blog.csdn.net/Water_Star1/article/details/140566489

相关文章

  • 数据结构-线性表、链表
    一、线性表介绍1、线性结构​ 在数据元素存在非空有限集中：存在唯一的一个被称为“第一个”的数据元素存在唯一的一个被称为“最后一个”的数据元素除了第一个外，集合中每个数据元素都只有一个前趋元素除了最后一个外，集合中每个数据元素都只有一个后继元素2、线性表线性表......
  • 链表带环问题简单讲解
     #带环链表解题思路对于这道题我们可以定义两个指针，一个快指针，一个慢指针。快指针一次走两步，慢指针一次走一步。这样快指针就会比慢指针先进入环内。慢指针进入环后，这个问题就会演变成一个追击问题，即：快指针能否追上慢指针并与之重合。假设，慢指针进入环后与快指针的距......
  • 算法第十一天：leetcode707.设计链表
    一、设计链表的题目描述与链接  707.设计链表的链接如下表所示，您可直接复制下面网址进入力扣学习，在观看下面的内容之前一定要先做一遍哦，这样才能印象深刻！https://leetcode.cn/problems/design-linked-list/https://leetcode.cn/problems/design-linked-list/题目描述：你......
  • 数据结构—双向链表
    文章目录1.双向链表的概念和结构1.1双向链表的概念1.2双向链表与单链表的对比1.3双向链表的结构2.双向链表的接口实现2.1申请一个新结点2.2初始化2.3打印2.4尾插2.5头插2.6判断链表是否为空2.7尾删2.8头删2.9查找2.10在指定位置之后插入数据2.11在指定位......
  • 线性表——链表（c语言）
    链表概念篇示意图1.单向链表2.双向链表3.循环链表4.链表的元素插入5.链表的元素删除代码篇1.链表的定义2.链表的创建3.链表的销毁4.链表的元素插入5.链表的元素删除6.链表的元素查找7.链表下标对应的结点8.链表元素的修改9.链表的打印10.完整代码代码运行效果概......
  • 链表（Linked List）-Python实现-使用类和使用函数
    链表链表（LinkedList）单链表（SinglyLinkedList）节点类（NodeClass）链表类（LinkedListClass）使用链表类不用类的方法实现链表实现单链表使用函数实现链表具体讲解类的方法实现链表Node类LinkedList类不用类的方法实现链表创建节点添加节点删除节点搜索节点显示链表总......
  • 链表。。。
    模板题AcWing826.单链表实现一个单链表，链表初始为空，支持三种操作：向链表头插入一个数；删除第k个插入的数后面的数；在第k个插入的数后插入一个数。现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。注意:题目中第k个插入的数并不是指当前链表的第......
  • 02线性表 - 链表
    这里是只讲干货不讲废话的炽念，这个系列的文章是为了我自己以后复习数据结构而写，所以可能会用一种我自己能够听懂的方式来描述，不会像书本上那么枯燥和无聊，且全系列的代码均是可运行的代码，关键地方会给出注释^_^全文1W+字版本：C++17编译器：Clion2023.3.24暂时只给出代码，不会涉......
  • 【代码随想录训练营第42期 Day3打卡 LeetCode 203.移除链表元素，707.设计链表，206.反转
    一、做题感受今天是打卡的第三天，前两天题目主要考察数组相关知识，现在已经来到了链表的学习。题目共有三道，都是以考察单链表为主，整体来说难度不大，但是思路很灵活，尤其是反转链表的考察，双指针的新用法。今天做题总体感觉不错，能有自己的思考和理解。二、链表相关知识1.常见链表......
  • 单链表，双链表和内核链表的比较
    首先贴上几个链接，来自一些大佬，这些文章详细易懂，可以帮助我们快速全面了解单双链表以及Linux内核链表list.h。1.C语言链表超详解；作者：rivencode；图文并茂，炒鸡详细2.链表基础知识详解；作者：不秃也很强；代码详细，条理清晰3.拒绝造轮子！如何移植并使用Linux内核的通用链表（附完整代码实现）；作......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99