三个小时写一个限制扩容的哈希表

话不多说直接贴代码。

说真的，今天听到这个任务的时候我心里一惊，感触颇多。

我想，该把下一个项目（毕设）尽早提上日程了（是时候找老师了）。

#include<vector>

/*
* 设计思路：哈希表构造时需要传入预期哈希表长度，以及开链法最长链表长度，建议设置8
* 存储哈希节点的数组里存放的是链表的长度，直接开链
* 当链表长度过长的时候将链表转化为AVL树，当链表长度缩减回可容纳范围时将AVL树切换回链表
*/


//链表类
class List_Node {

public:
	List_Node(int value) {
		this->value = value;
		this->next = NULL;
	}

	int get_value() {
		return this->value;
	}

	void set_value(int val) {
		this->value = val;
	}

	void* get_next() {
		return this->next;
	}

	//这个给链表定制的
	void set_next(int val) {
		List_Node* node = new List_Node(val);
		this->next = node;
	}

	void set_next(void* node) {	//为了兼容树和链表节点，这里需要用void*
		this->next = node;
	}
	
private:
	int value;	//值域
	void* next;	//指针域，为了后面链表转树，这里就设定为通用指针域
};


//树节点
class TreeNode {

private:
	int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡
	int val;
	TreeNode* left;
	TreeNode* right;
public:
	TreeNode(int x) : val(x), depth(0), left(NULL), right(NULL) {}
	TreeNode() : val(0), depth(0), left(NULL), right(NULL) {}

	int getnode() {
		return this->val;
	}

	void setnode(int val) {
		this->val = val;
	}

	TreeNode* getleft() {
		return this->left;
	}

	TreeNode* getright() {
		return this->right;
	}

	void setleft(TreeNode* node) {
		this->left = node;
	}

	void setright(TreeNode* node) {
		this->right = node;
	}
};



//AVL树
class AVL_Tree {
public:
	AVL_Tree() {
		
	}

	TreeNode* get_head() {
		return head;
	}

	TreeNode* create_tree(std::vector<int>& vec) {
		//初始化即构造
		for (int v : vec) {
			insert_node(head, v);
		}
		return head;
	}

	//先假设这个二叉树足够高
	TreeNode* insert_node(TreeNode* head, int val) {	//插入一个节点，不管三七二十一先插到叶子节点再说

		if (head != NULL) {
			if (val < head->getnode()) {
				head->setleft(insert_node(head->getleft(), val));
			}
			else {
				head->setleft(insert_node(head->getright(), val));
			}
		}
		else {	//这里不放else等着失败
			head = new TreeNode(val);
		}

		//插入之后就该旋转了
		if (getbalance(head) == 2) {	//如果需要旋转（左边高）
			if (getbalance(head->getleft()) == 1) {	//左左，需要右右旋转
				return right_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->getleft()) == -1) {	//左右，这里需要右左旋转
				return right_left_rotate(head);
			}
		}
		else if (getbalance(head) == -2) {	//如果需要旋转（右边高）
			if (getbalance(head->getright()) == -1) {	//右右，需要左左旋转
				return left_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->getright()) == -1) {	//左右，这里需要右左旋转
				return left_right_rotate(head);
			}
		}

		return head;
	}

	TreeNode* delete_node(TreeNode* head, int val) {

		if (head != NULL) {
			if (val < head->getnode()) {
				head->setleft(delete_node(head->getleft(), val));
			}
			else if (val > head->getnode()) {
				head->setleft(delete_node(head->getright(), val));
			}
			else {
				TreeNode* temp = head->getleft();
				while (temp && temp->getright()) {
					temp->setright(temp->getright());
				}
				
				head->setnode(temp->getnode());
				if (temp->getleft()) {	//如果最右子节点还有左子节点
					//那顶多就一个节点
					temp->setnode(temp->getleft()->getnode());
					//temp->left = temp->left->left;
					//temp->right = temp->left->right;
					temp->getleft()->setnode(NULL);
					delete temp->getleft();
				}
				else {
					temp->setnode(NULL);
					delete temp;
				}
			}
		}
		else {
			return NULL;
		}

		if (getbalance(head) == 2) {	//如果需要旋转（左边高）
			if (getbalance(head->getleft()) == 1) {	//左左，需要右右旋转
				return right_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->getleft()) == -1) {	//左右，这里需要右左旋转
				return right_left_rotate(head);
			}
		}
		else if (getbalance(head) == -2) {	//如果需要旋转（右边高）
			if (getbalance(head->getright()) == -1) {	//右右，需要左左旋转
				return left_rotate(head);	//这里还需要向上衔接
			}
			else if (getbalance(head->getright()) == -1) {	//左右，这里需要右左旋转
				return left_right_rotate(head);
			}
		}
		return head;
	}

	//查找树节点
	bool search_node(int val) {
		TreeNode* temp = head;

		while (temp) {
			if (val == temp->getnode()) {
				return true;
			}
			else if (val < temp->getnode()) {
				temp = temp->getleft();
			}
			else {
				temp = temp->getright();
			}
		}
		return false;
	}

private:
	TreeNode* head;

	TreeNode* right_rotate(TreeNode* root) {
		TreeNode* temp = root->getleft();
		root->setleft(temp->getright());
		temp->setright(root);

		return temp;
	}

	TreeNode* left_rotate(TreeNode* root) {
		TreeNode* temp = root->getright();
		root->setright(temp->getleft());
		temp->setleft(root);

		return temp;
	}

	TreeNode* right_left_rotate(TreeNode* root) {
		root->setright(right_rotate(root->getright()));
		return left_rotate(root);
	}

	TreeNode* left_right_rotate(TreeNode* root) {
		root->setleft(left_rotate(root->getleft()));
		return right_rotate(root);
	}

	int get_depth(TreeNode* node) {

		if (!node) {
			return 0;
		}

		int maxL = 0;
		int maxR = 0;

		//2.计算左子树的最大深度； 
		if (node->getleft() != NULL)
			maxL = get_depth(node->getleft());

		//3.计算右子树的最大深度； 
		if (node->getright() != NULL)
			maxR = get_depth(node->getright());

		//4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1 
		return maxL > maxR ? maxL + 1 : maxR + 1;
	}

	int getbalance(TreeNode* node) {
		return get_depth(node->getleft()) - get_depth(node->getright());
	}
};


//template<typename T>
class MyHash {
public:
	MyHash(/*T* a,*/ int total_len, int list_len) 
		:total_len(total_len),list_len(list_len),vec_(total_len)
	{
		for (int i = 0; i < total_len; i++) {
			vec_[i] = new List_Node(0);	//数组里记录链表长度，如果超过指定长度就转为树
		}
	}

	~MyHash() {

	}

	void insert_(int val) {
		int site = hash_func(val);
		int new_val = vec_[site]->get_value();

		if (new_val == list_len) {
			vec_[site]->set_next(list_to_tree((List_Node*)vec_[site]->get_next()));	//链表转树
			((AVL_Tree*)vec_[site]->get_next())->insert_node(((AVL_Tree*)vec_[site]->get_next())->get_head(),val);	//插入节点
		}
		else {
			List_Node* temp = vec_[site];
			while (temp->get_next()) {
				temp = (List_Node*)temp->get_next();
			}
			temp->set_next(val);
			vec_[site]->set_value(--new_val);	//更新数组中 链表/树 长度值
		}
	}

	bool search_(int val) {
		int site = hash_func(val);

		if (vec_[site]->get_value() > list_len) {
			//按树的方法查找
			return ((AVL_Tree*)vec_[site]->get_next())->search_node(val);
		}
		else {
			List_Node* temp = vec_[site];
			while (temp->get_next()) {
				temp = (List_Node*)temp->get_next();
				if (temp->get_value() == val) {
					return true;
				}
			}
			return false;
		}
	}

	bool delete_(int val) {
		int site = hash_func(val);
		int new_val = vec_[site]->get_value();

		if (new_val > list_len) {
			//按树的方法删除
			if (((AVL_Tree*)vec_[site]->get_next())->delete_node(((AVL_Tree*)vec_[site]->get_next())->get_head(),val) == NULL) {
				return false;
			}
			return true;
		}
		else {
			List_Node* temp = vec_[site];
			while (temp->get_next()) {
				temp = (List_Node*)temp->get_next();
				if (temp->get_value() == val) {
					List_Node* free = (List_Node*)temp->get_next();
					temp->set_next((List_Node*)(free->get_next()));

					vec_[site]->set_value(--new_val);	//更新数组中 链表/树 长度值
					
					if (new_val == list_len) {
						//将树转回链表
					}

					return true;
				}
			}
			return false;
		}
	}

private:
	//T* a;
	int total_len;	//底层数组总长度
	int list_len;	//开链·链表最大长度

	std::vector<List_Node*> vec_;

private:
	//哈希方法
	int hash_func(int val) {
		return val % total_len;
	}

	//再哈希方法
	int rehash_func() {

	}

	
	//链表转树
	AVL_Tree* list_to_tree(List_Node* head) {
		std::vector<int> temp(list_len,0);
		while (head) {
			temp.push_back(head->get_value());
		}
		AVL_Tree* avl = new AVL_Tree();
		avl->create_tree(temp);
		return avl;
	}

	//树转链表
	void tree_to_list(TreeNode* head) {

	}
};