算法导论——跳跃表的实现

在麻省理工的算法导论视频中，已对跳跃表讲述的很清晰，并且国内也有很多文章关于跳跃表的原理讲述的很明白，但是，在实现时，代码都是各种拷贝，看的云里雾里，自己写了一份，供大家参考（共计两个文件），感觉跳跃表实现的关键就是在查找目标元素时，能将“跳”体现处理，有不少网上给的参考代码，没有体现出跳跃的处理：

// skip_list.h

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

const int skip_list_max_level = 32;

class SkipListNode
{
    public:
        SkipListNode(int k = -1, int v = -1) : key(k), value(v)
        {
            for (int uli = 0; uli < skip_list_max_level; ++uli)
            {
                pNext[uli] = NULL;
            }
        }


    public:
        int key;
        int value;
        SkipListNode* pNext[skip_list_max_level];
};

class SkipList
{
    public:
        SkipList()
        {
            init();
        }

        void init();
        int  search(int key);
        bool search(int key, int& value);
        void remove(int key);
        void insert(int key, int value);

        void display_all();
        void display_by_level(int level);

    private:
        int rand_insert_level();


    private:
        int _cur_level;
        SkipListNode* _pHead;
};

 

int SkipList::rand_insert_level()
{
    int level = 1;
    while (rand() % 2 == 1)
    {
        ++level;
    }

    return level;
}

void SkipList::init()
{
    _cur_level = 1;
    _pHead = new SkipListNode();
    assert(NULL != _pHead);

    return;
}

int SkipList::search(int key)
{
    SkipListNode* pcur = _pHead;
    for (int ulj = _cur_level - 1; ulj >= 0; --ulj)
    {
        while (pcur->pNext[ulj] && pcur->pNext[ulj]->key < key)
        {
            pcur = pcur->pNext[ulj];
        }

        if (pcur->pNext[ulj])
        {
            if (pcur->pNext[ulj]->key == key)
            {
                return pcur->pNext[ulj]->value;
            }
        }
    }

    return -1;
}

 

void SkipList::insert(int key, int value)
{
    SkipListNode* insert_pos[skip_list_max_level];
    for (int uli = 0; uli < skip_list_max_level; ++uli)
    {
        insert_pos[uli] = _pHead;
    }

    SkipListNode* pcur = _pHead;
    for (int ulj = _cur_level - 1; ulj >= 0; --ulj)
    {
        while (pcur->pNext[ulj] && pcur->pNext[ulj]->key < key)
        {
            pcur = pcur->pNext[ulj];
        }

        if (pcur->pNext[ulj])
        {
            if (pcur->pNext[ulj]->key == key)
            {
                pcur->pNext[ulj]->value = value;
            }
        }

        insert_pos[ulj] = pcur;
    }

    SkipListNode* pNewElement = new SkipListNode(key, value);
    assert(NULL != pNewElement);

    int rand_level = rand_insert_level();
    for (int ulk = rand_level - 1; ulk >= 0; --ulk)
    {
        pNewElement->pNext[ulk] = insert_pos[ulk]->pNext[ulk];
        insert_pos[ulk]->pNext[ulk] = pNewElement;
    }

    _cur_level = _cur_level > rand_level ? _cur_level : rand_level;
    return;
}

bool SkipList::search(int key, int& value)
{
    SkipListNode* pcur = _pHead;
    for (int ulj = _cur_level - 1; ulj >= 0; --ulj)
    {
        while (pcur->pNext[ulj] && pcur->pNext[ulj]->key < key)
        {
            pcur = pcur->pNext[ulj];
        }

        if (pcur->pNext[ulj])
        {
            if (pcur->pNext[ulj]->key == key)
            {
                value = pcur->pNext[ulj]->value;
                return true;
            }
        }
    }

    return false;
}

 

void SkipList::remove(int key)
{
    SkipListNode* remove_pos[skip_list_max_level];
    for (int uli = 0; uli < skip_list_max_level; ++uli)
    {
        remove_pos[uli] = NULL;
    }

    int rm_level = 0;
    SkipListNode* pcur = _pHead;
    for (int ulj = _cur_level - 1; ulj >= 0; --ulj)
    {
        while (pcur->pNext[ulj] && pcur->pNext[ulj]->key < key)
        {
            pcur = pcur->pNext[ulj];
        }

        if (pcur->pNext[ulj])
        {
            if (pcur->pNext[ulj]->key == key)
            {
                ++rm_level;
                remove_pos[ulj] = pcur->pNext[ulj];
            }
        }
    }

    if (rm_level > 0)
    {
        SkipListNode* pRemove = remove_pos[0]->pNext[0];
        for (int ulk = rm_level - 1; ulk >= 0; --ulk)
        {
            remove_pos[ulk]->pNext[ulk] = remove_pos[ulk]->pNext[ulk]->pNext[ulk];
        }

        delete pRemove;
    }

    int blank_level_count = 0;
    for (int ulm = _cur_level - 1; ulm >= 0; --ulm)
    {
        if (NULL == _pHead->pNext[ulm])
        {
            ++blank_level_count;
        }
    }

    _cur_level -= blank_level_count;
    return;
}

 

void SkipList::display_all()
{
    for (int level = skip_list_max_level - 1; level >= 0; --level)
    {
        std::cout << "current level is " << level << " : ";
        SkipListNode* pcur = _pHead->pNext[level];
        while (pcur)
        {
            std::cout << pcur->key;
            pcur = pcur->pNext[level];
        }
       std::cout << std::endl;
    }

    return;
}

void SkipList::display_by_level(int level)
{
    if (level > skip_list_max_level || level < 0)
    {
        std::cout << "input level is error " << level << std::endl;
        return;
    }

    std::cout << "current level is " << level << " : ";
    SkipListNode* pcur = _pHead->pNext[level];
    while (pcur)
    {
        std::cout << pcur->key;
        pcur = pcur->pNext[level];
    }
    std::cout << std::endl;

    return;
}

//   main.cpp
#include "skip_list.h"

void search_test()
{
    SkipList skip_list;
    skip_list.init();

    for (int uli = 0; uli < 10; ++uli)
    {
        skip_list.insert(uli * 2, uli * 10);
    }
    skip_list.search(2);

    for (int uli = 0; uli < 10; ++uli)
    {  
        skip_list.insert(uli * 2 + 1, uli * 10);
    }
    skip_list.search(3);
    skip_list.search(4);

    return;
}

void remove_test()
{
    SkipList skip_list;
    skip_list.init();

    for (int uli = 0; uli < 10; ++uli)
    {
        skip_list.insert(uli * 2, uli * 10);
    }

    for (int uli = 0; uli < 10; ++uli)
    {
        skip_list.insert(uli * 2 + 1, uli * 10);
    }
    skip_list.display_all();

    for (int uli = 0; uli < 10; ++uli)
    {
        skip_list.remove(rand() % 20);
    }
    skip_list.display_all();

    return;
}

int main()
{
//    search_test();
    remove_test();

    return 0;
}