0001 template <typename K, typename V> bool Skiplist<K, V>::put ( K k, V v ) { //跳转表词条插入算法 0002 Entry<K, V> e = Entry<K, V> ( k, v ); //待插入的词条(将被随机地插入多个副本) 0003 if ( empty() ) insertAsFirst ( new Quadlist<Entry<K, V>> ); //插入首个Entry 0004 ListNode<Quadlist<Entry<K, V>>*>* qlist = first(); //从顶层四联表的 0005 QuadlistNode<Entry<K, V>>* p = qlist->data->first(); //首节点出发 0006 if ( skipSearch ( qlist, p, k ) ) //查找适当的插入位置(不大于关键码k的最后一个节点p) 0007 while ( p->below ) p = p->below; //若已有雷同词条,则需强制转到塔底 0008 qlist = last(); //以下,紧邻于p的右侧,一座新塔将自底而上逐层生长 0009 QuadlistNode<Entry<K, V>>* b = qlist->data->insertAfterAbove ( e, p ); //新节点b即新塔基座 0010 while ( rand() & 1 ) { //经投掷硬币,若确定新塔需要再长高一层,则 0011 while ( qlist->data->valid ( p ) && !p->above ) p = p->pred; //找出不低于此高度的最近前驱 0012 if ( !qlist->data->valid ( p ) ) { //若该前驱是header 0013 if ( qlist == first() ) //且当前已是最顶层,则意味着必须 0014 insertAsFirst ( new Quadlist<Entry<K, V>> ); //首先创建新的一层,然后 0015 p = qlist->pred->data->first()->pred; //将p转至上一层Skiplist的header 0016 } else //否则,可径自 0017 p = p->above; //将p提升至该高度 0018 qlist = qlist->pred; //上升一层,并在该层 0019 b = qlist->data->insertAfterAbove ( e, p, b ); //将新节点插入p之后、b之上 0020 }//课后:调整随机参数,观察总体层高的相应变化 0021 return true; //Dictionary允许重复元素,故插入必成功——这与Hashtable等Map略有差异 0022 }