三个小时写一个限制扩容的哈希表
话不多说直接贴代码。
说真的，今天听到这个任务的时候我心里一惊，感触颇多。
我想，该把下一个项目（毕设）尽早提上日程了（是时候找老师了）。
#include
/*
* 设计思路：哈希表构造时需要传入预期哈希表长度，以及开链法最长链表长度，建议设置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& 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
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 vec_;
private:
//哈希方法
int hash_func(int val) {
return val % total_len;
}
//再哈希方法
int rehash_func() {
}
//链表转树
AVL_Tree* list_to_tree(List_Node* head) {
std::vector 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) {
}
};
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
暂时没有评论，来抢沙发吧~