`
田庆阳
  • 浏览: 6379 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

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

阅读更多

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

// 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;
}

 

分享到:
评论

相关推荐

    算法导论——所有算法和数据结构的C++实现

    所有代码都是在我学习这本书时亲手敲出来的,并且调试正确了,包括:第三部分到第六部分(即10-26章),外加第七部分31和32章所有的算法和数据结构以及编程习题还有思考题的C++实现源代码; 第一、二部分学习的较早...

    算法书 Solutions for CLRS Computer Algorithms CLRS for Instructor 《算法导论——教师用书

    CLRS for Instructor 《算法导论——教师用书》(有部分习题答案) Computer Algorithms - Introduction to Design and Analysis 3rd - Sara Baase Solutions for CLRS (算法导论部分习题解答)

    MIT算法导论——算法顶尖经典教材

    通过学习《MIT算法导论》,读者不仅可以掌握各种算法的实现,还能理解算法设计的原则,培养解决问题的思维能力。此外,书中包含的习题和实例有助于巩固所学知识,提升实践能力。无论是对于计算机科学专业的学生,...

    算法导论——Introduction to Algorithms

    《算法导论》是计算机科学领域的一本经典教材,由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同编写,本书的第二版出版于2001年,由MIT出版社与McGraw-Hill Book Company...

    算法导论——《Introduction to Algorithms》

    《算法导论》由Thomas H.Cormen、Charles E.Leiserson、Ronald L.Rivest、Clifford Stein四人合作编著(其中Clifford Stein是第二版开始参与的合著者)。本书的最大特点就是将严谨性和全面性融入在了一起。

    算法导论 课后解答 教师用书

    - **解决方案**:课后解答不仅提供了排序算法的实现细节,还深入分析了各种排序算法的时间和空间复杂度,帮助学生理解每种算法的优点和局限性。 #### 第11章至第14章:数据结构 - **主题讲解**:从哈希表到二叉搜索...

    MIT公开课——算法导论教材

    《MIT公开课——算法导论》的讲义部分可能详细解释了这些概念,并通过实例演示了如何实现和分析算法的效率。答案部分则帮助学生检查自我学习的效果,加深对知识的理解。这本教材不仅适合初学者入门,也对有一定经验...

    算法导论第三版完整版答案

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书的第三版更是对前两版进行了完善和更新,涵盖了更广泛的主题和最新的研究成果。针对你提到的“算法导论第三版完整版...

    算法导论第四章答案

    算法导论第四章答案算法导论第四章答案算法导论第四章答案算法导论第四章答案

    算法导论第四版 英文

    《算法导论第四版》涉及了如红黑树、B树、二叉搜索树、平衡查找树、哈希表、图的搜索算法(深度优先搜索和广度优先搜索)以及最小生成树、最短路径问题等高级主题。这部分内容为读者提供了处理更复杂数据结构和算法...

    算法导论 +答案 MIT

    《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 《算法导论》由...

    算法导论中文第三版习题答案

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。中文第三版的出版,使得更多的中文读者能够接触到这本权威教材。本书覆盖了从排序和搜索到图算法,再到动态规划和贪心算法...

    算法导论答案第四版英文版

    《算法导论》是计算机科学领域的一本经典著作,它由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同撰写,全面深入地介绍了算法的设计、分析以及计算问题的解决方案。这本书...

    算法导论第三版及2-25章部分答案

    6. **数据结构**:如堆、栈、队列、哈希表、树(二叉搜索树、红黑树、AVL树等),它们是实现高效算法的基础。 7. **复杂度分析**:了解算法的时间复杂度和空间复杂度,可以帮助我们评估算法的效率,并在实际应用中...

    算法导论 第三版 中文pdf

    算法导论 第三版 中文pdf

    算法导论 第二十五章 答案

    算法导论 第二十五章 答案 算法导论 第二十五章 答案 算法导论 第二十五章 答案

    算法导论电子版

    Cormen 算法导论扫描版 清晰 算法入门 经典

    算法导论第二十四章答案

    算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案

    算法导论 中英文高清版本

    《算法导论》是一本备受推崇的计算机科学教材,它深入浅出地介绍了算法的设计、分析和实现。这本书由Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest和Clifford Stein四位作者共同撰写,是全球范围内...

    算法导论第二版课后答案中文完全版

    《算法导论》第二版是一本广泛应用于计算机科学与信息技术领域的经典教材,它深入浅出地介绍了各种核心算法,为读者提供了丰富的理论基础和实践指导。课后答案作为学习过程中的重要参考资料,可以帮助读者检验自己的...

Global site tag (gtag.js) - Google Analytics