數據結構散列線性開型尋址(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;
}
關聯標簽:
华东15选5彩票奖结果 120期香港六合彩 菠萝彩票 (^ω^)MG花粉之国在线客服 江苏7位数走势图 (★^O^★)MG极速抢钱如何爆大奖 网络彩票重庆时时彩 15选5必中技巧 奇人透码三期必中 黑龙江p62开奖结果 (★^O^★)MG财富小姐_稳赢版 (^ω^)MG花粉之国技巧介绍 (-^O^-)MG丧尸来袭爆分打法 平特精料板2018 招财鞭炮老虎机 博易彩票平台怎么样 (★^O^★)MG海底捞鱼app