0001 template <typename K, typename V> bool Skiplist<K, V>::remove( K k ) { //跳转表词条删除算法 0002 QNodePosi< Entry<K, V> > p = search ( k ); //查找目标词条 0003 if ( !p->pred || (k != p->entry.key) ) return false; //若不存在,直接返回 0004 ListNodePosi< Quadlist< Entry<K, V> >* > qlist = last(); //从底层Quadlist开始 0005 while ( p->above ) { qlist = qlist->pred; p = p->above; } //升至塔顶 0006 do { //逐层拆塔 0007 QNodePosi< Entry<K, V> > lower = p->below; //记住下一层节点,并 0008 qlist->data->remove( p ); //删除当前层节点,再 0009 p = lower; qlist = qlist->succ; //转入下一层 0010 } while ( qlist->succ ); //直到塔基 0011 while ( (1 < height()) && (first()->data->_size < 1) ) { //逐层清除 0012 List::remove( first() ); 0013 first()->data->header->above = NULL; 0014 } //已不含词条的Quadlist(至少保留最底层空表) 0015 return true; //删除成功 0016 } //体会:得益于哨兵的设置,哪些环节被简化了?