[Day21]程序菜鸟自学C++资料结构演算法 – 杂凑搜寻法实作

前言：昨天讲解完了杂凑法的定义和，今天要来把它实际创建出来，这次用到的杂凑法要用之前学过的链结串列来实现，如果忘记相关技术的可以回去看看喔！

废话不多说，开始实作！！！

先建立杂凑函式的整体架构函式。

接着建立链结串列的节点。

第三步要撰写杂凑表，查询、插入、修改、删除都写在这里面，所以这一整段比较复杂。

首先是第一个查询的部分。

插入和修改比较类似，所以都写在put里面。

最後一个就是删除。

整体的架构完成得差不多了，可以先执行看看结果跑不跑得出来。

将五笔资料存入後，先用程序码显示第二三笔资料，然後把第四笔资料删除後就无法显示出来，所以刚刚撰写的基本功能都可以正常运作。

接着来尝试做做看学生杂凑表。

这样的做法可以比较统一资料储存的格式，先写好输出的模板也可以少写东西在主程序码中。

接下来简单测试一下！

储存三笔学生的资料，先显示二号林同学的资料，将它修改成蔡同学程序也能执行。

本日小结：今天的实作内容先到这边为止，虽然只有一个基本的概念，但是就有不少程序码，当初在研究的时候也花了很多时间。其实在第一次接触到杂凑的时後，我觉得是资料结构和演算法中比较令我头痛的，很多复杂的名词和概念让我在学习时吃了不少苦头，经过这两篇文章的整理，确实有对杂凑更了解一些。在实作杂凑法的时候，想想要怎麽利用杂凑函式得到杂凑值，并寻找出我们要的value，以这样的方式思考会必较好喔٩(✿∂‿∂✿)۶

template<typename K>
struct KeyHash {
	KeyHash(const unsigned long table_size) //建立杂凑函式的构造函数
		:table_size(table_size) {}
	unsigned long operator()(const K& key) const {
		return static_cast<unsigned long>(key) % table_size; //将key强制转换成unsigned long型别
	}                                                        //并取除以table_size的余数
private:
	unsigned long table_size; //unsigned long资料型别的一种，类似於int
};

template<typename K,typename V>
class HashNode { //建立链结串列的节点
public:
	K key; //宣告杂凑值
	V value; //宣告资料
	HashNode *next; //宣告下一个节点的指针
	HashNode(const K &key, const V &value) :
	key(key), value(value), next(nullptr) {
	}
};

template<typename K, typename V,typename F=KeyHash<K>> //传递杂凑函数的类型typename F=KeyHash<K>
class HashMap { //建立杂凑表
	int table_size;
	HashNode<K, V> * *table; //*table指向HashNode<K, V>这种类型的变量
	F hashFunc;
public:
	HashMap(F hashF, const int table_size = 10) : //建立HashMap的构造函式
		//宣告杂凑函数的类型和table_size的大小
		table_size(table_size), hashFunc(hashF) { //传回各自的值
		table = new HashNode<K, V> * [table_size](); //创建动态数组
		for (int i = 0; i < table_size; i++)
			table[i] = 0; //初始化table
	}
	~HashMap() { //删除每个链结串列table[i]中的所有节点
		for (int i = 0; i < table_size;i++) {
			HashNode<K, V>* entry = table[i];
			while (entry) {
				HashNode<K, V>* p = entry;
				entry = entry->next;
				delete p;
			}
			table[i] = 0;
		}
		delete[] table; //删除table数组
	}
	bool get(const K& key, V& value) { //编写查询方法，给定一个key，查询一个value
		unsigned long hashValue = hashFunc(key); //将hashFunc里面的杂凑值传入hashValue，可以想成杂凑表的地址
		HashNode<K, V>* entry = table[hashValue]; //资照杂凑表的下标table[hashValue]，取代成第一个节点的指针*entry 

		while (entry) { //当entry不是空指针
			if (entry->key == key) { //如果key是我们要找的
				value = entry->value; //则将value传回entry所指向的value
				return true;
			}
	    entry = entry->next; //如果没有找到，则把entry往下一个移，继续此步骤
		}
		return false;
	}
	void put(const K& key, const V& value) { //编写插入或修改的 函式
		unsigned long hashValue = hashFunc(key);
		HashNode<K, V>* prev = nullptr; //将prev指向空指针
		HashNode<K, V>* entry = table[hashValue]; //将entry指向table[hashValue]
		while (entry && entry->key != key) { //如果entry所指向的key不是我们要找的值
			prev = entry; //在entry指向下一个节点前先让prev = entry，也就是让prev保持在entry的前一个节点
			entry = entry->next;
		}
		if (!entry) { //如果都没有找到
			entry = new HashNode<K, V>(key, value); //则将entry做一个新节点的插入
			if (!prev) { //如果prev为空的，代表一开始是空的表
				table[hashValue] = entry; //把entry放到之杂凑表内
			}
			else {
				prev->next = entry;
			}
		}
		else {
			entry->value = value; //更新其他value
		}
	}
	void remove(const K&key) { //编写删除杂凑值的函式
		unsigned long hashValue = hashFunc(key);
		HashNode<K, V>* prev = 0;
		HashNode<K, V>* entry = table[hashValue];
		while (entry && entry->key != key) {
			prev = entry;
			entry = entry->next;
		}
		if (!entry) //当entry是空指针，则说明没找到
			return;
		else {
			if (!prev) //如果prev是空指针，代表耀珊的节点是第一个节点
				table[hashValue] = entry->next; //把entry的下一个节点修改成table[hashValue]
			else
				prev->next = entry->next;
			delete entry;
		}
		
	}
};

#include <iostream>
#include <string>
using namespace std;
struct student { //定义学生的数据类型
	string name, phone;
	unsigned int age;
	student(string name = "no", string phone = "000", unsigned age = 0) :
		name(name), phone(phone), age(age) {}
};
ostream& operator<<(ostream& o, const student& stu) { //可以输出学生类型的资料
	o << stu.name << "," << stu.phone << "," << stu.age << endl;
	return o;
 }

int main() {
	const int table_size = 10;
	HashMap<int, string, KeyHash<int>>hamp(KeyHash<int>(table_size), table_size); 
	//创建一个hamp为HashMap的构造对象，并存入HashMap的模板参数
	hamp.put(1, "Allen");
	hamp.put(2, "Hank");
	hamp.put(3, "Rudy");
	hamp.put(4, "Nick");
	hamp.put(5, "Edward");
	string value;
	hamp.get(2, value);
	cout << value << endl;
	bool res = hamp.get(3, value);
	if(res)
		cout << value << endl;
	hamp.remove(4);
	res = hamp.get(4, value);
	if (res)
		cout << value << endl;


	HashMap<int, student, KeyHash<int>>hamp2(KeyHash<int>(table_size), table_size);
	hamp2.put(1, student("Chen", "0989267", 20));
	hamp2.put(2, student("Lin", "0929403", 22));
	hamp2.put(3, student("Wang", "0962771", 18));
	student stu;
	hamp2.get(2, stu);
	cout << stu;
	hamp2.put(2, student("Tsai", "0917364", 24));
	hamp2.get(2, stu);
	cout << stu << endl;
}