跳表项目 Posted on 2023-03-01 19:37:47 2023-03-01 19:37:47 by Author 摘要 跳表项目----根据carl的跳表项目，分享一些自己的理解。 # C++跳表项目 ## 全局互斥锁mtx ## 模板类---Node节点 ### 成员变量 - K key - V value - Node<K,V>** forward - int node_level ### 成员函数 - 构造函数 - 析构函数 - get_key - get_val - set_val ### 实现成员函数 - 构造函数 - forward = new Node<K,V>*[level+1] - 表示有level+1个Node类型的指针数组 - memset(forward,0,sizeof(Node<K,V>*)*(level+1)) - 析构函数 - delete[] forward ## 模板类---SkipList ### 成员变量 - _max_level - _skip_list_level - Node<K,V>*_header; - _file_writer - _file_reader; - _element_count ### 成员函数 - 析构函数 - 构造函数 - Node<K,V>*create_node(K,V,int) - int insert_element(K,V) - display_list() - search_element(K) - dump_filer() - load_file() - int size() - get_key_value_from_string(str,key,vlaue) - is_valid_string(str) ### 实现成员函数 - 构造函数 - _header = new Node<K,V>(k,v,_max_level - Node<K,V>* create_node(k,v,level) - return new Node<K,V>(k,v,level); - insert_element(k,v) - 首先mtx.lock() - 的到跳表的_header赋值给current - 创建一个[_max_level+1]个Node<k,v>类型的指针为update,并且分配空间 - 从最高的level变量查找 - 找到每一层要改的update所找到的位置 - current= current->forward[0]从最底层开始查找，如果key已经存在释放锁并且直接返回 - 如果current为空或者current->key!=key - 随机生成一个插入节点的level - 如果随机生成的level大于当前的跳表的level，那么大于当前level的指针的值为header - 即为:for (int i = _skip_list_level+1; i <random_level+1; i++) {update[i] = _header;} - 创建一个将要插入的节点 inserted_node(k,v random_level - 从0到random_level插入节点，插入节点即为链表形式的插入，先接后面，在接前面 - for (int i = 0; i <= random_level; i++){inserted_node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = inserted_node; } - 跳表元素加1并且释放锁mtx.lock() - delete_element(K key) - 上锁mtx.lock() - 定义一个current指向_header,并且定义一个_max_level+1个node类型的指针数组 - 遍历找到key所在的位置，并且遍历过程中更改update数组指针，找到删除key的节点前一个节点 - for (int i = _skip_list_level; i >= 0; i--) { while (current->forward[i] !=NULL && current->forward[i]->get_key() < key) { current = current->forward[i]; } update[i] = current; } - current指向最底层即为0层 - current = current->forward[0]; - 如果当前节点current不为空，并且当前节点current的值等于key,删除节点 - 从0层开始删除一直到当前跳表的层 - 如果更改的update[i]和current不相等，那么后续节点不用删除，直接break - 否则删除当前节点 - update[i]->forward[i] = current->forward[i]; - 移除元素后更改跳表的skip_list_level - while (_skip_list_level > 0 && _header->forward[_skip_list_level] == 0) { _skip_list_level --; } - 释放锁mtx.lock() - search_element(K key) - 定义一个current指针指向_header - 循环遍历从_skip_list_level到0找到current所在的位置 - 如果current不为空并且其forward[0]等于当前key说明找到了，否则没有找到 - get_random_level - int k = 1; while (rand() % 2) { k++; } k = (k < _max_level) ? k : _max_level; return k; - 析构函数 - _file_writer.close(); - _file_reader.close(); - delete _header; - display_list - 从0层到跳表skip_list_level循环遍历 - 即为对每一层链表遍历即可 - Node<K, V> *node = this->_header->forward[i]; std::cout << "Level " << i << ": "; while (node != NULL) { std::cout << node->get_key() << ":" << node->get_value() << ";"; node = node->forward[i]; } - dump_file() - 首先打开文件：_file_write.open("path") - 从header->forward[0]开始 - 遍历第0层的节点即可 - node = node->forward[0]; - 关闭文件 - load_file() - 打开文件:_file_reader.open("path") - 定义key和value - 每一行为key和value对，从文件循环遍历读取key和value - 调用insert_element(key,value)函数，插入节点即可 - 关闭文件:_file_reader.close() - get_key_value_from_string(string str,string key, string val) - delimiter=":" - key = str.substr(0, str.find(delimiter)); - value = str.substr(str.find(delimiter)+1, str.length()); - is_valid_string(string str) - 查看str是否有delimiter - find函数在找不到delimiter的时候，会返回npos - if (str.find(delimiter) == std::string::npos) { return false; } 
{{ item.content }}
{{ child.content }}