indexlistutil_;const integer skipstep_;};
二、重建索引
已知有数据层链表datalinklist ，长度为 n，那么第 level层需要建立的索引数是 datalistsize /pow(skipstep_,level ) 个，每隔skipstep个数据节点就建立一个索引，直到第level层需要建立的节点数是0就不再键索引。在此过程中，如果层级要大于原有索引层级需要扩充索引层，否则再原来索引层进行修改。
/*** 从第数据链表的startelem开始重建立链表* @tparam elemtype* @param startelem*/
template
void smartdonglib::skiplist::rebuildindex(elemtype startelem) {//获取数据总数int datalistsize = datalistutil_.listlenth(datalinklist_);//要重建数据索引的个数
// int rebulddatacount = datalistsize - startindex 1;//索引层应建立索引的节点数int indexlevelcount = datalistsize / skipstep_;int indexlevel=0;while (indexlevelcount !=0){//如果层级要大于 indexlinklist_.size(),需要扩充indexlist，否则再原来的基础上修改，还需要判断是不是第0索引层if(indexlevel >= indexlinklist_.size()){boost::shared_ptr> currentindexlist (new linklist());//头指针也进行关联if (indexlevel ==0){currentindexlist->data.pointer_.datapointer = datalinklist_;
// currentindexlist->data.position_ =datalinklist_->data;}else{currentindexlist->data.pointer_.indexpointer = indexlinklist_[indexlevel-1];
// currentindexlist->data.position_ =indexlinklist_[indexlevel-1]->data.position_;}bool isfirst = true;boost::shared_ptr> linkdatanode;boost::shared_ptr> linkindexnode;//扩展 indexlevel 层的后面的索引for (int i = 1; i <=indexlevelcount; i) {
// boost::shared_ptr> currentindexnode (new linklist);indexstruct currentindexnode;//第0索引层指向data数据，其他指向下层索引数据。优化：第一次从头节点确定指向的位置，之后再此基础上在 上skipstep_if (indexlevel == 0) {if (isfirst){linkdatanode = datalistutil_.listgetnode(datalinklist_,i * skipstep_);isfirst= false;}else{linkdatanode = datalistutil_.listgetnode(linkdatanode, skipstep_);}currentindexnode.position_ =linkdatanode->data;currentindexnode.pointer_.datapointer = linkdatanode;}else{if (isfirst){linkindexnode =indexlistutil_.listgetnode(indexlinklist_[indexlevel - 1], i * skipstep_);isfirst= false;}else{linkindexnode =indexlistutil_.listgetnode(linkindexnode, skipstep_);}currentindexnode.position_ =linkindexnode->data.position_;currentindexnode.pointer_.indexpointer = linkindexnode;}indexlistutil_.listorderinsert(currentindexlist,currentindexnode);}indexlinklist_.push_back(currentindexlist);} else{//如果在原来的索引层上进行修改，那么确认要修改的索引节点进行重建boost::shared_ptr> currentindexlist=indexlinklist_[indexlevel];//找到startelem前一个元素的位置boost::shared_ptr> startindexnode;int startidx = findindexlistposition(indexlevel, startelem,startindexnode);//重键startindexnode之后的索引startindexnode->next = null;boost::shared_ptr> linkdatanode;boost::shared_ptr> linkindexnode;bool isfirst = true;//第indexlevel层从startidx开始重建索引for (int i = startidx 1; i <=indexlevelcount; i){
// boost::shared_ptr> currentindexnode (new linklist);
// linklist currentindexnode;indexstruct currentindexnode;//优化：第0索引层指向data数据，其他指向下层索引数据，第一次从头节点确定指向的位置，之后再此基础上在 上skipstep_if (indexlevel == 0) {if (isfirst){linkdatanode = datalistutil_.listgetnode(datalinklist_,i * skipstep_);isfirst= false;}else{linkdatanode = datalistutil_.listgetnode(linkdatanode, skipstep_);}currentindexnode.position_ =linkdatanode->data;currentindexnode.pointer_.datapointer = linkdatanode;}else{if (isfirst){linkindexnode =indexlistutil_.listgetnode(indexlinklist_[indexlevel - 1], i * skipstep_);isfirst= false;}else{linkindexnode =indexlistutil_.listgetnode(linkindexnode, skipstep_);}currentindexnode.position_ =linkindexnode->data.position_;currentindexnode.pointer_.indexpointer = linkindexnode;}indexlistutil_.listorderinsert(currentindexlist,currentindexnode);}}indexlevel ;indexlevelcount /= skipstep_;}}
三、根据位置确定数据节点
在level层移动一次next 对应的数据层节点数增加pow(skipstep_,currentindexlevel)位置。
/*** 获取节点(已优化)* @tparam elemtype* @param pos data的位置* @return 获取pos对应的元素节点*/
template
boost::shared_ptr> smartdonglib::skiplist::findnodebypos(size pos) {int indexlistsize = indexlinklist_.size();int currentindexlevel = indexlistsize-1;boost::shared_ptr> currentindexnode = indexlinklist_[currentindexlevel];int currentpos = 0;int posincrement =1;boost::shared_ptr> ret = datalinklist_;while(currentpos <= pos && currentindexlevel >=0){posincrement = std::pow(skipstep_,currentindexlevel 1);if ( currentindexnode->next!=null && currentpos posincrement <=pos ){//如果查在后面currentindexnode=currentindexnode->next;currentpos =posincrement;}else{//如果当前层确定了位置，就下一层直到第indexlevel结束if ( currentindexlevel == 0 ){ret = currentindexnode->data.pointer_.datapointer;currentindexlevel --;break;}else{currentindexnode = currentindexnode->data.pointer_.indexpointer;currentindexlevel --;}}}while (pos - currentpos >0 && currentindexlevel<0){ret = ret->next;currentpos ;}return ret;
}
四、根据元素data信息来查询元素位置
/*** 根据元素寻找在datalinklist中的位置(已优化)* @tparam elemtype* @param elem* @return 位找到是-1 ，头节点是第0个位置*/
template
int smartdonglib::skiplist::findposbyelem(elemtype elem) {int indexlistsize = indexlinklist_.size();int currentindexlevel = indexlistsize-1;boost::shared_ptr> idxlist=indexlinklist_[currentindexlevel];int pos = 0;while (currentindexlevel >= 0){if ( idxlist->next && idxlist->next->data.position() <= elem ){//如果查在后面idxlist=idxlist->next;pos =pos std::pow(skipstep_,currentindexlevel 1 );}else{//如果当前层确定了位置，就下一层直到第indexlevel结束if ( currentindexlevel == 0 ){break;}else{idxlist = idxlist->data.pointer_.indexpointer;currentindexlevel --;}}}boost::shared_ptr> datanode = idxlist->data.pointer_.datapointer;if (datanode ->data == elem){return pos;} else{int rslt =datalistutil_.listgetindex(datanode,elem);if (rslt == -1 )return -1;elsereturn pos datalistutil_.listgetindex(datanode,elem);}
}
五、插入和删除
查询到要插入的节点位置后，进行普通有序链表的插入和删除即可
总结
以上是凯发k8官方网为你收集整理的c :跳表数据结构的实现原理的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。
