WizenZhang
10/4/2018 - 2:49 PM

## 【随机化算法】跳跃表【7.3.3】舍伍德(Sherwood)算法

``````//随机化算法 跳跃表
#include "stdafx.h"
#include "RandomNumber.h"
#include <cmath>
#include <iostream>
using namespace std;

template<class EType,class KType> class SkipList;
template<class EType,class KType>
class SkipNode
{
friend SkipList<EType,KType>;
private:
SkipNode(int size)
{
next = new SkipNode<EType,KType>*[size];
}
~SkipNode()
{
delete []next;
}
EType data;//集合中的元素
SkipNode<EType,EType> **next;//指针数组 next[i]是第i级指针
};

template<class EType,class KType>
class SkipList
{
public:
SkipList(KType Large,int MaxE = 10000,float p = 0.5);
~SkipList();
bool Search(const KType& k,EType& e) const;
SkipList<EType,KType>& Insert(const EType& e);
SkipList<EType,KType>& Delete(const KType& k,EType& e);
void Output();
private:
int Level();
SkipNode<EType,KType> *SaveSearch(const KType& k);
int MaxLevel;					//跳跃表级别上界
int Levels;						//当前最大级别
RandomNumber rnd;				//随机数产生器
float Prob;						//用于分配节点级别
KType TailKey;					//元素键值上界
SkipNode<EType,KType> *NIL;		//尾节点指针
SkipNode<EType,KType> **last;	//指针数组
};

//构造函数
template<class EType,class KType>
SkipList<EType,KType>::SkipList(KType Large,int MaxE,float p)
{
Prob = p;
MaxLevel = ceil(log(float(MaxE))/log(1/p))-1;		//初始化跳跃表级别上界
TailKey = Large;							//元素键值上界
Levels = 0;									//初始化当前最大级别

//创建头、尾节点和数组 last
NIL = new SkipNode<EType,KType>(0);
last = new SkipNode<EType,KType> *[MaxLevel+1];
NIL->data = Large;

//将跳跃表初始化为空表
for(int i=0; i<=MaxLevel; i++)
{
}
}

//析构函数
template<class EType,class KType>
SkipList<EType,KType>::~SkipList()
{
SkipNode<EType,KType> *next;

//删除所有节点
{
}

delete NIL;
delete []last;
}

class element
{
friend int main(void);
public:
operator long() const
{
return key;
}
element& operator = (long y)
{
key = y;
return *this;
}
private:
int data;
long key;
};

//搜索指定元素k
template<class EType,class KType>
bool SkipList<EType,KType>::Search(const KType& k,EType& e) const
{
if(k>=TailKey)
{
return false;
}
//位置p恰好位于指定元素k之前
for(int i=Levels; i>=0; i--)//逐渐向下搜索
{
while(p->next[i]->data<k)//在第i级链中搜索
{
p = p->next[i];//每次搜索尽可能滴接近要搜索的元素
}
}
e = p->next[0]->data;
return (e==k);
}

//搜索指定元素k,并将每一级中遇到的上一个节点存放在数组last中
template<class EType,class KType>
SkipNode<EType,KType> *SkipList<EType,KType>::SaveSearch(const KType& k)
{
//位置p恰好位于指定元素k之前
for(int i = Levels; i>=0; i--)
{
while(p->next[i]->data<k)
{
p = p->next[i];
}
last[i] = p;	//上一个第i级结点
}
return (p->next[0]);
}

//产生不超过MaxLevel 的随机级别
template<class EType,class KType>
int SkipList<EType,KType>::Level()
{
int lev = 0;
while(rnd.fRandom()<Prob)
{
lev++;
}
return (lev<=MaxLevel)?lev:MaxLevel;
}

//插入指定元素e
template<class EType,class KType>
SkipList<EType,KType>& SkipList<EType,KType>::Insert(const EType& e)
{
KType k = e;//取得元素键值
if(k>=TailKey)
{
cout<<"元素键值超界!"<<endl;
return *this;
}
//检查元素是否已存在
SkipNode<EType,KType> *p = SaveSearch(k);
if(p->data == e)
{
cout<<"元素已存在!"<<endl;
return *this;
}

//元素不存在，确定新节点级别
int lev = Level();
//调整个级别指针
if(lev>Levels)
{
for(int i=Levels+1; i<=lev; i++)
{
}
Levels = lev;
}

//产生新节点，并将新节点插入p之后
SkipNode<EType,KType> *y = new SkipNode<EType,KType>(lev+1);
y->data = e;

for(int i=0; i<=lev; i++)
{
//插入第i级链
y->next[i] = last[i]->next[i];
last[i]->next[i] = y;
}
return *this;
}

//删除键值为k的元素，并将所删除的元素存入e
template<class EType,class KType>
SkipList<EType,KType>& SkipList<EType,KType>::Delete(const KType& k,EType& e)
{
if(k>=TailKey)
{
cout<<"元素键值超界!"<<endl;
}
//搜索待删除元素
SkipNode<EType,KType> *p = SaveSearch(k);
if(p->data!=k)
{
cout<<"未找到待删除元素!"<<endl;
}
//从跳跃表中删除节点
for(int i=0; i<=Levels && last[i]->next[i] == p; i++)
{
last[i]->next[i] = p->next[i];
}
//更新当前级别
{
Levels--;
}
e = p->data;
delete p;
return *this;
}

//输出集合中的元素
template<class EType,class KType>
void SkipList<EType,KType>::Output()
{
for(;y!=NIL; y=y->next[0])
{
cout<<y->data<<' ';
}
cout<<endl;
}

int main()
{
SkipList<int,int> *s = new SkipList<int,int>(100,10,0.5);

//创建
cout<<"=========创建==========="<<endl;

int a[] = {5,3,2,11,7,13,19,17,23};

for(int i=0; i<9; i++)
{
s->Insert(a[i]);
}
s->Output();

//搜索
cout<<"=========搜索==========="<<endl;
int k=17,e;
cout<<"搜索元素k="<<k<<"如下:"<<endl;
if(s->Search(17,e))
{
cout<<"位置搜索结果为：k="<<k<<",e="<<e;
}
cout<<endl;

//删除
cout<<"=========删除==========="<<endl;
cout<<"删除跳跃表元素k="<<k<<"剩余元素如下:"<<endl;
s->Delete(k,e);
s->Output();

delete s;
return 0;
}
``````
``````#include"time.h"
//随机数类
const unsigned long maxshort = 65536L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;

class RandomNumber
{
private:
//当前种子
unsigned long randSeed;
public:
RandomNumber(unsigned long s = 0);//构造函数，默认值0表示由系统自动产生种子
unsigned short Random(unsigned long n);//产生0：n-1之间的随机整数
double fRandom(void);//产生[0,1)之间的随机实数
};

RandomNumber::RandomNumber(unsigned long s)//产生种子
{
if(s == 0)
{
randSeed = time(0);//用系统时间产生种子
}
else
{
randSeed = s;//由用户提供种子
}
}

unsigned short RandomNumber::Random(unsigned long n)//产生0：n-1之间的随机整数
{
randSeed = multiplier * randSeed + adder;//线性同余式
return (unsigned short)((randSeed>>16)%n);
}

double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数
{
return Random(maxshort)/double(maxshort);
}
``````