skiplist.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//跳表类
#ifndef SKIPLIST_H
#define SKIPLIST_H
#include <iostream>
using namespace std;
const int DefaultSize = 200;

template <class E, class K>
struct SkipNode {						//跳表结点类定义
	E data;								//数据域
	SkipNode<E,K> **link;				//指针数组域
	SkipNode(int size = DefaultSize) {  //构造函数
		link = new SkipNode<E,K> *[size];
		if (link == NULL) {cerr << "存储分配失败！" << endl; exit(1);}
	}
	~SkipNode() {delete [] link;} //析构函数
};
template <class E, class K>
class SkipList { //跳表类定义
public:
	SkipList(K large, int maxLev = DefaultSize);	//构造函数
	~SkipList();									//析构函数
	bool Search(const K k1, E& e1)const;			//搜索函数
	E& getData(SkipNode<E,K> *current) {
		if (current != NULL) return &current->data;
		else return NULL;
	}
	bool Insert(const K k1, E& e1);					//插入函数
	bool Remove(const K k1, E& e1);				    //删除函数
	void show();									//输出各链的值
private:
	int maxLevel;									//所允许的最大级数
	int Levels;										//当前非空链的级数
	K TailKey;										//在TailKey中存有一个大值
	SkipNode<E,K> *head;							//附加头结点
	SkipNode<E,K> *tail;							//附加尾结点
	SkipNode<E,K> **last;							//指针数组
	int Level();
	SkipNode<E,K> *SaveSearch(const K k1);
};

template <class E, class K>
SkipList<E,K>::SkipList(K large, int maxLev) {
	//构造函数：建立空的多级链
	maxLevel = maxLev; //最大级链数目
	TailKey = large; //控制扫描的最大关键码
	Levels = 0;
	head = new SkipNode<E,K>(maxLevel+1); //附加头结点,有maxLevel+1指针
	tail = new SkipNode<E,K>(0); //附加尾结点,有0个指针
	last = new SkipNode<E,K> *[maxLevel+1]; //跳表的多级链的头指针
	tail->data = large;
	for (int i = 0; i <= maxLevel; i++) head->link[i] = tail;
};


template <class E, class K>
SkipList<E,K>::~SkipList() {
	//析构函数：释放链表所有元素结点
	SkipNode<E,K> *next;
	while (head != tail) {
		next = head->link[0];
		delete head;
		head = next;
	}
	delete tail;
	delete [] last;
};


template <class E, class K>
bool SkipList<E,K>::Search(const K k1, E& e1) const{
	if (k1 > TailKey) return false;
	SkipNode<E,K> *p = head;
	for (int i = Levels; i >= 0; i--) //逐级向下搜索
		while (p->link[i]->data < k1) //重载：元素关键码判小于
			p = p->link[i];
	e1 = p->link[0]->data;
	return (e1 == k1) ? true : false; //重载：元素关键码判等于
};


template <class E, class K>
SkipNode<E,K> *SkipList<E,K>::SaveSearch(const K k1) {
	if (k1 > TailKey) return NULL;
	SkipNode<E,K> *p = head;
	for (int i = Levels; i >= 0; i--) { //逐级向下搜索
		while (p->link[i]->data < k1) //重载：元素关键码判小于
			p = p->link[i];
		last[i] = p; //记下最后比较结点
	}
	return p->link[0]; //返回找到的结点地址
};


template <class E, class K>
int SkipList<E,K>::Level() {
	//产生一个随机的级别，该级别 < maxLevel
	int lev = 0;
	while (rand() <= RAND_MAX/2) lev++;
	return (lev < maxLevel) ? lev : maxLevel;
};


template <class E, class K>
bool SkipList<E,K>::Insert(const K k1, E& e1) {
	if (k1 >= TailKey)
	{cerr << "关键码太大！" << endl; return false;}
	SkipNode<E,K> *p = SaveSearch(k1); //检查是否重复
	if (p->data == e1) //重载：元素间判等于
	{cerr << "关键码重复！" << endl; return false;}
	int lev = Level(); //随机产生一个级别
	if (lev > Levels) //调整级别
	{lev = ++Levels; last[lev] = head;}
	SkipNode<E,K> *newNode = new SkipNode<E,K>(lev+1);
	newNode->data = e1;  //重载：元素赋值
	for (int i = 0; i <= lev; i++) { //各级链入
		newNode->link[i] = last[i]->link[i]; //第i级链入
		last[i]->link[i] = newNode;
	}
	return true;
};



template <class E, class K>
bool SkipList<E,K>::Remove(const K k1, E& e1) {
	if (k1 > TailKey) //关键码太大
	{cerr << "关键码太大！" << endl; return false;}
	SkipNode<E,K> *p = SaveSearch(k1); //搜索与k1匹配的元素->p
	if (p->data != k1) //重载：元素关键码判不等
	{cout << "被删除元素不存在！" << endl; return false;}
	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)
		Levels--; //修改级数
	e1 = p->data; delete p;
	return true;
};


template<class E,class K> void SkipList<E,K>::show()
{
	cout<<"maxLevel : "<<maxLevel<<endl;
	cout<<"Levels : "<<Levels<<endl;
	for(int i=Levels-1;i>=0;i--)
	{
		SkipNode<E,K> * p=head->link[i];
		cout<<"Level "<<i<<" : head -- ";
		while(p!=tail)
		{
			cout<<p->data<<" -- ";
			p=p->link[i];
		}
		cout<<"tail"<<endl;
	}
}


#endif;