跳 表

#ifndef SKIPLIST_H
#define SKIPLIST_H

#include<iostream>
#include<assert.h>

const int DefaultSize = 100;
template<typename E,typename K>
class SkipNode{
    E data;
    SkipNode<E,K> **link;
    SkipNode(int size=DefaultSize){
        link = new SkipNode<E,K>*[size];
        assert(link!=NULL);
    }
};

template<typename E,typename 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);
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<typename E,typename 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);
    last = new SkipNode<E,K> *[maxLevel+1];
    tail->data = large;
    for(int i=0;i<=maxLevel;i++)
        head->link[i]=tail;
}

template<typename E,typename 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<typename E,typename 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];
    }
    el = p->link[0]->data;
    return e1==k1?true:false;
}

template<typename E,typename 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<typename E,typename K>
int SkipList<E,K>::Level()
{
    int lev=0;
    while(rand()<=RAND_MAX/2)
        lev++;
    return lev<maxLevel?lev:maxLevel;
}

template<typename E,typename 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;
    }
    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];
        last[i]->link[i] = newNode;
    }
    return true;
}

template<typename E,typename K>
bool SkipList<E,K>::Remove(const K k1, E &e1)
{
    if(k1>TailKey){
        cerr << "关键码太大!" << endl;
        return false;
    }
    SkipNode<E,K> *p = SaveSearch(k1);
    if(p->data!=k1){
        cerr << "被删除元素不存在!"<<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;
}

#endif // SKIPLIST_H