![](https://csdnimg.cn/release/download_crawler_static/11226372/bg9.jpg)
class Sk ipLis t
{
public :
SkipLis t(T la rge, int mLe v);
~SkipLis t();
ResultCo de Inse rt(T x); // 函 数 定 义 见 3.1.1 节
priva te:
int Le vel();
SNode <T>* Sa veSea rc h(T x);
int ma xLe vel, le vels;
SNode <T> * head, * ta il, ** last;
};
【 程 序 3-6 】 构 造 函 数
templa te<c lass T>
SkipLis t<T >::Sk ipLis t(T la rge, int mLe v)
{
maxLe vel=mLe v; le vels=0 ;
hea d=ne w SNo de<T>(ma xLe vel+1 ); // 指 向 包 括 元 素 域 和 maxLe vel+1 个 指 针 的 头 结 点
ta il=new S No de<T>(0 ); // 指 向 只 有 元 素 域 , 不 包 含 指 针 域 的 尾 结 点
last=new SNo de<T>* [ma xLe vel+1 ]; //ma xLe vel+1 个 指 针
ta il->e le ment.ke y=la rge ; // 尾 结 点 中 保 存 作 为 哨 兵 值 的 最 大 值 la rge
for (int i=0 ;i<=ma xLe vel;i++)
hea d->link [i]=ta il; // 头 结 点 的 所 有 指 针 指 向 尾 结 点
}
【 程 序 3-7 】 级 数 分 配
templa te <c lass T >
int Sk ipLis t<T >::Le vel()
{
int le v=0 ;
while (ra nd()<= RAND_MAX/2 ) le v++;
return (le v<=ma xLe vel) ? lev:ma xLe vel;
}
【 程 序 3-8 】 插 入 运 算
enum Res ultCo de{Unde rflow,Ove rflow,S uccess,Duplicate ,Ra ngeE rro r,NotP resent};
templa te<c lass T, c lass K>
SNode <T>* Sk ipLis t<T, K>: :Sa veSearc h(T x)
{ //假 定 T 类 已 重 载 了 关 系 运 算 符 或 类 型 转 换 运 算 符
SNode <T>* p=hea d;
for(int i=le vels;i>=0 ;i --){
while (p->link [i]->ele me nt <x) p=p->link [i];
last[i]=p; //将 最 后 搜 索 到 的 第 i 层 结 点 的 地 址 保 存 在 last[i] 中
}
return (p->link [0 ]);
}