116.txt

第二个搜索函数为私有成员函数S a v e S e a r c h

template<class E, class K>
int SkipList<E,K>::Level()
{// 产生一个随机级号，该级号<= MaxLevel
int lev = 0;
while (rand() <= CutOff )
l e v + + ;
return (lev <= MaxLevel) ? lev : MaxLevel;
}
template<class E, class K>
SkipList<E,K>& SkipList<E,K>::Insert(const E& e)
{// 如果不存在重复，则插入e
K k = e; // 抽取关键值
if (k >= TailKey) throw BadInput(); // 关键值太大
// 检查是否重复
SkipNode<E,K> *p = SaveSearch(k);
if (p->data == e) throw BadInput(); // 重复
// 不重复, 为新节点确定级号
int lev = Level(); // 新节点的级号
// fix lev to be <= Levels + 1
if (lev > Levels) {lev = ++Levels; last[lev] = head;}
// 产生新节点，并将新节点插入p之后
SkipNode<E,K> *y = new SkipNode<E,K> (lev+1);
y->data = e;
for (int i = 0; i <= lev; i++) {
// 插入到第i级链
y->link[i] = last[i]->link[i];
last[i]->link[i] = y;
}
return *this;
}
template<class E, class K>
SkipList<E,K>& SkipList<E,K>::Delete(const K& k, E& e)
{// 删除与k相匹配的元素，并将所删除的元素放入e
// 如果不存在与k匹配的元素，则引发异常B a d I n p u t
if (k >= TailKey) throw BadInput(); // 关键值太大
// 检查是否存在与k相匹配的元素
SkipNode<E,K> *p = SaveSearch(k);
if (p->data != k) throw BadInput(); // 不存在
// 从跳表中删除节点
for (int i = 0; i <= Levels && last[i]->link[i] == p; i++)
last[i]->link[i] = p->link[i];
// 修改级数
while (Levels > 0 && head->link[Levels] == tail)
L e v e l s - - ;
e = p->data;
delete p;
return *this;
}