數據結構散列線性開型尋址（C++實現）插入，刪除，查找

小編:啊南 52閱讀 2020.11.17

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 ààDíμ?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ààDíμ?hash
public:
	size_t operator()(const int theKey) const {
		return size_t(theKey);
	}
};

template<>
class Hash1<long> { //long intDíμ?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); //×??¨ò?3yêyμ??μ?a11
	~HashTable() {
		delete[] table;    //??11oˉêy
	}

	bool empty() const {
		return dSize == 0;    //?D??±íê?·??a??
	}
	int size() const {
		return dSize;    //·μ??±íμ?3¤?è
	}
	pair<const K, E>* find(const K&) const;//?¨ò?2é?òoˉêy
	void insert(const pair<const K, E>&);//?¨ò?2?è?oˉêy
	pair<const K, E>* erase(const K& theKey) ;//?¨ò?é?3yoˉêy
	void output(ostream& out) const;//?¨ò?ê?3?oˉêy

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 oˉêy divisor
};

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

	//·???oí3?ê??ˉé￠áD±íêy×é
	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 {
	// 2é?òò????aμ??·±í
// è?1?′??ú￡?·μ??kμ?????
// ·??ò·μ??2?è?μ?￡¨è?1?óD×?1?????￡?

	int i = (int)Hash(theKey) % divisor;  // ?eê?í°
	int j = i;    // ′ó?eê?í°?aê?
	do {
		if (table[j] == NULL || table[j]->first == theKey)
			return j;
		j = (j + 1) % divisor;  // ??ò???bucket  ó?j+1oíó?theKay+1D§1?ò???
	} while (j != i);        // ·μ???eê?í°?

	return j;  // ±íò??-?ú
}

template<class K, class E>
pair<const K, E>* HashTable<K, E>::find(const K& theKey) const {
	// ???÷ó?k?￥??μ??a??2￠·?è?
	// ???÷é￠áD±í
	int b = search(theKey);

	//?′??ó|μ??a??ê?·??úé￠áD±í?D
	if (table[b] == NULL || table[b]->first != theKey) {
		cout << -1 << endl;
		//return NULL;           // è?1?2?′??ú?a?ùμ??a??￡??ò·μ??null?￡
	}
	else cout << b << endl;
	return table[b];  //?￥??3é1|￡?·μ??
}


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<<"2aê?"<<endl;
		//cout << table[b]->second << "2aê?" << 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; // ?eê?í°
		int j = (i + 1)%divisor;    // ′ó?eê?í°dμ???ò???í°?aê?
		while(table[j] != NULL && j != i)// ·μ???eê?í°?	
		{
			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+1oíó?theKay+1D§1?ò???			 
		}
		cout << ct << endl;//ê?3?ò??ˉ′?êy 				
	}
	//dSize--;
	return NULL;
}

template<class K, class E>
void HashTable<K, E>::output(ostream& out) const {
	// ??é￠áD±í?Dμ??a??·?è?ê?3?á÷
	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;
	}
}

// ???? <<2ù×÷·?
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;
}

全國[切換]∨

首頁

找工作

找人才

找兼職

查企業

查工資

看趨勢

職場知識

百科

更多>

數據結構散列線性開型尋址（C++實現）插入，刪除，查找

小編:啊南 52閱讀 2020.11.17

關聯標簽：

QQ客服

E-mail:market#hunt007.cn