数据结构散列线性开型寻址（C++实现）插入，删除，查找

种花家的奋斗兔

发布于 2020-11-13 09:50:23

9180

发布于 2020-11-13 09:50:23

文章被收录于专栏：NLP小白的学习历程

1. OJ平台题目描述

问题描述

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

有以下三种操作：

插入x，若散列表已存在x，输出“Existed”，否则插入x到散列表中，输出所在的下标。查询x，若散列表不含有x，输出“-1”，否则输出x对应下标。删除x，若散列表不含有x，输出“Not Found”，否则输出删除x过程中移动元素的个数。输入格式第一行两个整数D(1≤\leq≤ D ≤\leq≤ 3000)和m(1≤\leq≤ m ≤\leq≤ 3000)，其中D为散列函数的除数，m为操作数。接下来的m行，每行两个整数opt和x，分别代表操作类型和操作数。若opt为0，则代表向散列表中插入x；若opt为1，代表查询散列表中x是否存在；若opt为2，(如果散列表中含有x)，删除x。数据保证散列表不会溢出。输出格式

m行，每行一个整数，代表对应查询的答案。

样例输入1

7 15 2 10 0 10 0 10 2 10 1 10 0 10 1 10 0 17 0 2 0 16 0 11 2 2 2 10 1 11 1 17

样例输出2

Not Found 3 Existed 0 -1 3 3 4 2 5 6 2 2 4 3

2.Hash关键部分代码

template<class K, class E>
class HashTable {
public:
	HashTable(int theDivisor = 11); //自定义除数的值为11
	~HashTable() {
		delete[] table;    //析构函数
	}

	bool empty() const {
		return dSize == 0;    //判断表是否为空
	}
	int size() const {
		return dSize;    //返回表的长度
	}
	pair<const K, E>* find(const K&) const;//定义查找函数
	void insert(const pair<const K, E>&);//定义插入函数
	pair<const K, E>* erase(const K& theKey) ;//定义删除函数
	void output(ostream& out) const;//定义输出函数

protected:
	int search(const K&) const;
	pair<const K, E>** table;  // Hash table
	Hash1<K> Hash;              // maps type K to nonnegative integer
	int dSize;                 // number of pairs in dictionary
	int divisor;               // Hash 函数 divisor
};

template<class K, class E>
HashTable<K, E>::HashTable(int theDivisor) {
	divisor = theDivisor;
	dSize = 0;

	//分配和初始化散列表数组
	table = new pair<const K, E>*[divisor];
	for (int i = 0; i < divisor; i++)
		table[i] = NULL;
}

template<class K, class E>
int HashTable<K, E>::search(const K& theKey) const {
	// 查找一个开地址表
// 如果存在，返回k的位置
// 否则返回插入点（如果有足够空间）

	int i = (int)Hash(theKey) % divisor;  // 起始桶
	int j = i;    // 从起始桶开始
	do {
		if (table[j] == NULL || table[j]->first == theKey)
			return j;
		j = (j + 1) % divisor;  // 下一个bucket  用j+1和用theKay+1效果一致
	} while (j != i);        // 返回起始桶?

	return j;  // 表已经满
}

template<class K, class E>
pair<const K, E>* HashTable<K, E>::find(const K& theKey) const {
	// 搜索与k匹配的元素并放入
	// 搜索散列表
	int b = search(theKey);

	//看对应的元素是否在散列表中
	if (table[b] == NULL || table[b]->first != theKey) {
		cout << -1 << endl;
		//return NULL;           // 如果不存在这样的元素，则返回null。
	}
	else cout << b << endl;
	return table[b];  //匹配成功，返回
}


template<class K, class E>
void HashTable<K, E>::insert(const pair<const K, E>& thePair) {
	// Insert thePair into the dictionary. Overwrite existing
// pair, if any, with same key.
// Throw HashTableFull exception in case table is full.
// search the table for a matching pair
	int b = search(thePair.first);

	// check if matching pair found
	if (table[b] == NULL) {
		// no matching pair and table not full
		table[b] = new pair<const K, E>(thePair);
		dSize++;
		cout << b << endl;
		//cout << table[b]->first<<"测试"<<endl;
		//cout << table[b]->second << "测试" << endl;
	}
	else {
		// check if duplicate or table full
		if (table[b]->first == thePair.first) {
			// duplicate, change table[b]->second
			table[b]->second = thePair.second;
			cout << "Existed" << endl;
		}
		else // table is full
			throw HashTableFull();
	}
}
template<class K, class E>
pair<const K, E>* HashTable<K, E>::erase(const K& theKey) 
{
	int b = search(theKey);
	int ct = 0;
	// check if matching pair found
	if (table[b] == NULL || table[b]->first != theKey)
	{
		// no matching pair and table not full
		cout << "Not Found" << endl;
	}
	else
	{			// duplicate, change table[b]->second
		table[b] = NULL;
		int i = b; // 起始桶
		int j = (i + 1)%divisor;    // 从起始桶d的下一个桶开始
		while(table[j] != NULL && j != i)// 返回起始桶?	
		{
			int k=(table[j]->first) % divisor ;
			if ((k!= j)&&(((k<=b)&&(j>b))||((k>j)&&((b<j)||(b>=k)))))
			{
				table[b] = table[j];
				table[j] = NULL;
				b = j;
				ct++;
			}
		j = (j + 1) % divisor; // 下一个bucket  用j+1和用theKay+1效果一致			 
		}
		cout << ct << endl;//输出移动次数 				
	}
	//dSize--;
	return NULL;
}

template<class K, class E>
void HashTable<K, E>::output(ostream& out) const {
	// 将散列表中的元素放入输出流
	for (int i = 0; i < divisor; i++) {
		cout << "NO." << i << " bucket:";
		if (table[i] == NULL)
			cout << "NULL" << endl;
		else
			cout << table[i]->first << " "
			<< table[i]->second << endl;
	}
}

关键在删除操作！！！

线性开型寻址：

1）建立HashTable类，public中含有：自定义构造函数，析构函数，empty（）函数，size()函数，find函数，insert函数，erase函数以及output函数。Protected内有search函数，pair类型的table，以及dSize，divisor和hash。

2）search函数，如果表中存在该元素，返回k的位置，否则，返回插入点（在有足够空间的前提下）。从起始桶开始查找，如果桶为空或者桶中对应的元素不是关键值为key 的，那么返回桶的标号，并查找下一个桶，直到一个循环结束，找到则中途返回，否则，返回起始桶的标号。

3）find函数，调用protected中的search函数，搜索对应的元素是否在散列表，如果存在，返回下标，否则，输出-1；

4）insert函数，如果要插入的位置的桶为空，那么直接插入，并将dSize加一，并输出，否则，输出Existed。如果桶已经满，则抛出异常。

5）erase函数，删除操作的关键在于判断哪些元素需要移动，哪些不需要被移动，移动到何位置结束。调用search函数查找到起始桶的位置b ，然后向后进行遍历，如果满足当前桶j中的元素和实际应该放置的位置k不同，并且满足b在k和j之间或者0<=b<j||b>=k那么则需要将它进行移动。移动的方法为，将要删除的置空，然后将该移动的元素移到该位置，并将被移动元素的起始位置置空。并将计数用变量ct++；

完整代码

//#include"pch.h"
#include<iostream>
#include<string>
#include<fstream>
using namespace std;
class illegalParameterValue {
public:
	illegalParameterValue(string theMessage = "Illegal parameter value") {
		message = theMessage;
	}
	void outputMessage() {
		cout<< message << endl;
	}
private:
	string message;
};

// illegal input data
class illegalInputData {
public:
	illegalInputData(string theMessage = "Illegal data input") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// illegal index
class illegalIndex {
public:
	illegalIndex(string theMessage = "Illegal index") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// matrix index out of bounds
class matrixIndexOutOfBounds {
public:
	matrixIndexOutOfBounds
	(string theMessage = "Matrix index out of bounds") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// matrix size mismatch
class matrixSizeMismatch {
public:
	matrixSizeMismatch(string theMessage =
		"The size of the two matrics doesn't match") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// stack is empty
class stackEmpty {
public:
	stackEmpty(string theMessage =
		"Invalid operation on empty stack") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// queue is empty
class queueEmpty {
public:
	queueEmpty(string theMessage =
		"Invalid operation on empty queue") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// Hash table is full
class HashTableFull {
public:
	HashTableFull(string theMessage =
		"The Hash table is full") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// edge weight undefined
class undefinedEdgeWeight {
public:
	undefinedEdgeWeight(string theMessage =
		"No edge weights defined") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

// method undefined
class undefinedMethod {
public:
	undefinedMethod(string theMessage =
		"This method is undefined") {
		message = theMessage;
	}
	void outputMessage() {
		cout << message << endl;
	}
private:
	string message;
};

template <class K> class Hash1;

template<>
class Hash1<string> { //string ÀàÐÍµÄhash
public:
	size_t operator()(const string theKey) const {
		// Convert theKey to a nonnegative integer.
		unsigned long HashValue = 0;
		int length = (int)theKey.length();
		for (int i = 0; i < length; i++)
			HashValue = 5 * HashValue + theKey.at(i);

		return size_t(HashValue);
	}
};

template<>
class Hash1<int> { //intÀàÐÍµÄhash
public:
	size_t operator()(const int theKey) const {
		return size_t(theKey);
	}
};

template<>
class Hash1<long> { //long intÐÍµÄhash
public:
	size_t operator()(const long theKey) const {
		return size_t(theKey);
	}
};

template<class K, class E>
class HashTable {
public:
	HashTable(int theDivisor = 11); //×Ô¶¨Òå³ýÊýµÄÖµÎª11
	~HashTable() {
		delete[] table;    //Îö¹¹º¯Êý
	}

	bool empty() const {
		return dSize == 0;    //ÅÐ¶Ï±íÊÇ·ñÎª¿Õ
	}
	int size() const {
		return dSize;    //·µ»Ø±íµÄ³¤¶È
	}
	pair<const K, E>* find(const K&) const;//¶¨Òå²éÕÒº¯Êý
	void insert(const pair<const K, E>&);//¶¨Òå²åÈëº¯Êý
	pair<const K, E>* erase(const K& theKey) ;//¶¨ÒåÉ¾³ýº¯Êý
	void output(ostream& out) const;//¶¨ÒåÊä³öº¯Êý

protected:
	int search(const K&) const;
	pair<const K, E>** table;  // Hash table
	Hash1<K> Hash;              // maps type K to nonnegative integer
	int dSize;                 // number of pairs in dictionary
	int divisor;               // Hash º¯Êý divisor
};

template<class K, class E>
HashTable<K, E>::HashTable(int theDivisor) {
	divisor = theDivisor;
	dSize = 0;

	//·ÖÅäºÍ³õÊ¼»¯É¢ÁÐ±íÊý×é
	table = new pair<const K, E>*[divisor];
	for (int i = 0; i < divisor; i++)
		table[i] = NULL;
}

template<class K, class E>
int HashTable<K, E>::search(const K& theKey) const {
	// ²éÕÒÒ»¸ö¿ªµØÖ·±í
// Èç¹û´æÔÚ£¬·µ»ØkµÄÎ»ÖÃ
// ·ñÔò·µ»Ø²åÈëµã£¨Èç¹ûÓÐ×ã¹»¿Õ¼ä£©

	int i = (int)Hash(theKey) % divisor;  // ÆðÊ¼Í°
	int j = i;    // ´ÓÆðÊ¼Í°¿ªÊ¼
	do {
		if (table[j] == NULL || table[j]->first == theKey)
			return j;
		j = (j + 1) % divisor;  // ÏÂÒ»¸öbucket  ÓÃj+1ºÍÓÃtheKay+1Ð§¹ûÒ»ÖÂ
	} while (j != i);        // ·µ»ØÆðÊ¼Í°?

	return j;  // ±íÒÑ¾Âú
}

template<class K, class E>
pair<const K, E>* HashTable<K, E>::find(const K& theKey) const {
	// ËÑË÷ÓëkÆ¥ÅäµÄÔªËØ²¢·ÅÈë
	// ËÑË÷É¢ÁÐ±í
	int b = search(theKey);

	//¿´¶ÔÓ¦µÄÔªËØÊÇ·ñÔÚÉ¢ÁÐ±íÖÐ
	if (table[b] == NULL || table[b]->first != theKey) {
		cout << -1 << endl;
		//return NULL;           // Èç¹û²»´æÔÚÕâÑùµÄÔªËØ£¬Ôò·µ»Ønull¡£
	}
	else cout << b << endl;
	return table[b];  //Æ¥Åä³É¹¦£¬·µ»Ø
}


template<class K, class E>
void HashTable<K, E>::insert(const pair<const K, E>& thePair) {
	// Insert thePair into the dictionary. Overwrite existing
// pair, if any, with same key.
// Throw HashTableFull exception in case table is full.
// search the table for a matching pair
	int b = search(thePair.first);

	// check if matching pair found
	if (table[b] == NULL) {
		// no matching pair and table not full
		table[b] = new pair<const K, E>(thePair);
		dSize++;
		cout << b << endl;
		//cout << table[b]->first<<"²âÊÔ"<<endl;
		//cout << table[b]->second << "²âÊÔ" << endl;
	}
	else {
		// check if duplicate or table full
		if (table[b]->first == thePair.first) {
			// duplicate, change table[b]->second
			table[b]->second = thePair.second;
			cout << "Existed" << endl;
		}
		else // table is full
			throw HashTableFull();
	}
}
template<class K, class E>
pair<const K, E>* HashTable<K, E>::erase(const K& theKey) 
{
	int b = search(theKey);
	int ct = 0;
	// check if matching pair found
	if (table[b] == NULL || table[b]->first != theKey)
	{
		// no matching pair and table not full
		cout << "Not Found" << endl;
	}
	else
	{			// duplicate, change table[b]->second
		table[b] = NULL;
		int i = b; // ÆðÊ¼Í°
		int j = (i + 1)%divisor;    // ´ÓÆðÊ¼Í°dµÄÏÂÒ»¸öÍ°¿ªÊ¼
		while(table[j] != NULL && j != i)// ·µ»ØÆðÊ¼Í°?	
		{
			int    k=(table[j]->first) % divisor ;
			if ((k!= j)&&(((k<=b)&&(j>b))||((k>j)&&((b<j)||(b>=k)))))
			{
				table[b] = table[j];
				table[j] = NULL;
				b = j;
				ct++;
			}
		j = (j + 1) % divisor; // ÏÂÒ»¸öbucket  ÓÃj+1ºÍÓÃtheKay+1Ð§¹ûÒ»ÖÂ			 
		}
		cout << ct << endl;//Êä³öÒÆ¶¯´ÎÊý 				
	}
	//dSize--;
	return NULL;
}

template<class K, class E>
void HashTable<K, E>::output(ostream& out) const {
	// ½«É¢ÁÐ±íÖÐµÄÔªËØ·ÅÈëÊä³öÁ÷
	for (int i = 0; i < divisor; i++) {
		cout << "NO." << i << " bucket:";
		if (table[i] == NULL)
			cout << "NULL" << endl;
		else
			cout << table[i]->first << " "
			<< table[i]->second << endl;
	}
}

// ÖØÔØ <<²Ù×÷·û
template <class K, class E>
ostream& operator<<(ostream& out, const HashTable<K, E>& x) {
	x.output(out);
	return out;
}
/*void readtext()
{

	ifstream infile;
	infile.open("car15.in", ios::in);
	int n; int m;
	infile >> n;
	infile >> m;
	//cout << n << m;
	HashTable<int, int> z(n);
	pair<int, int> p;
	int opt, x;

	for (int i = 0; i < m; i++)
	{
		infile >> opt; infile >> x;
		switch (opt)
		{
		case(0):
			p.first = x;
			p.second = x;
			z.insert(p);
			break;
		case(1):
			z.find(x);
			break;
		case(2):
			z.erase(x);
		default:
			break;
		}
	}
}*/
int main() 
{
	//readtext();
    int n;
	int m;
	cin >> n;
	cin >> m;
	//cout << n << m;
	HashTable<int, int> z(n);
	pair<int, int> p;
	int opt, x;

	for (int i = 0; i < m; i++) {
		cin >> opt;
		cin >> x;
		switch (opt) {
		case(0):
			p.first = x;
			p.second = x;
			z.insert(p);
			break;
		case(1):
			z.find(x);
			break;
		case(2):
			z.erase(x);
			break;
		default:
			break;
		}
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/11/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

sql

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

sql

登录后参与评论

0 条评论

热度