如何用Linux内核链表来实现DTLib中的双向循环链表

本篇内容介绍了"如何用Linux内核链表来实现DTLib中的双向循环链表"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

继承关系如下图所示

下来我们来讲讲它的设计思路：数据结点之间在逻辑上构成双向循环链表，头结点仅用于结点的定位。如下图所示

实现思路：

1、通过模板定义 DualCircleList 类。继承自 DualLinkList 类；

2、在 DualCircleList 内部使用 Linux 内核链表进行实现；

3、使用 struct list_head 定义 DualCircleList 的头结点；

4、特殊处理：循环遍历时忽略头结点

实现要点：

1、通过 list_head 进行目标结点定位（position(i)）；

2、通过 list_entry 将 list_head 指针转换为目标结点指针；

3、通过 list_for_each 实现 int find(const T& e) 函数；

4、遍历函数中的 next() 和 pre() 需要考虑跳过头结点

下来我们来看看基于 Linux 内核链表的双向循环链表是怎样写的

DualCircleList 源码

#ifndef DUALCIRCLELIST_H#define DUALCIRCLELIST_H#include "DualLinkList.h"#include "LinuxList.h"namespace DTLib{template < typename T >class DualCircleList : public DualLinkList{protected:    struct Node : public Object    {        list_head head;        T value;    };    list_head m_header;    list_head* m_current;    list_head* position(int i) const    {        list_head* ret = const_cast(&m_header);        for(int p=0; pnext;        }        return ret;    }    int mod(int i) const    {        return (this->m_length == 0) ? 0 : (i % this->m_length);    }public:    DualCircleList()    {        this->m_length = 0;        this->m_step = 1;        m_current = NULL;        INIT_LIST_HEAD(&m_header);    }    bool insert(const T& e)    {        return insert(this->m_length, e);    }    bool insert(int i, const T& e)    {        bool ret = true;        Node* node = new Node();        i = i % (this->m_length + 1);        if(node != NULL)        {            node->value = e;            list_add_tail(&node->head, position(i)->next);            this->m_length++;        }        else        {            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");        }        return ret;    }    bool remove(int i)    {        bool ret = true;        i = mod(i);        ret = ((0 <= i) && (i < this->m_length));        if( ret )        {            list_head* toDel = position(i)->next;            if( m_current == toDel )            {                m_current = toDel->next;            }            list_del(toDel);            this->m_length--;            delete list_entry(toDel, Node, head);        }        return ret;    }    bool set(int i, const T& e)    {        bool ret = true;        i = mod(i);        ret = ((0 <= i) && (i < this->m_length));        if( ret )        {            list_entry(position(i)->next, Node, head)->value = e;        }        return ret;    }    T get(int i) const    {        T ret;        if( get(i, ret) )        {            return ret;        }        else        {            THROW_EXCEPTION(IndexOutOfBoundsException, "Invaild parameter i to get element ...");        }    }    bool get(int i, T& e) const    {        bool ret = true;        i = mod(i);        ret = ((0 <= i) && (i < this->m_length));        if( ret )        {            e = list_entry(position(i)->next, Node, head)->value;        }        return ret;    }    int find(const T& e) const    {        int ret = -1;        int i = 0;        list_head* slider = NULL;        list_for_each(slider, &m_header)        {            if( list_entry(slider, Node, head)->value == e )            {                ret = i;                break;            }            i++;        }        return ret;    }    int length() const    {        return this->m_length;    }    void clear()    {        while( this->m_length > 0 )        {            remove(0);        }    }    bool move(int i, int step = 1)    {        bool ret = (step > 0);        i = mod(i);        ret = ret && ((0 <= i) && (i < this->m_length));        if( ret )        {            m_current = position(i)->next;            this->m_step = step;        }        return ret;    }    bool end()    {        return (m_current == NULL) || (this->m_length == 0);    }    T current()    {        if( !end() )        {            return list_entry(m_current, Node, head)->value;        }        else        {            THROW_EXCEPTION(INvalidOPerationException, "No value at current position ...");        }    }    bool next()    {        int i = 0;        while( (i < this->m_step) && !end() )        {            if( m_current != &m_header )            {                m_current  = m_current->next;                i++;            }            else            {                m_current = m_current->next;            }        }        if( m_current == &m_header )        {            m_current = m_current->next;        }        return (i == this->m_step);    }    bool pre()    {        int i =0;        while( (i < this->m_step) && !end() )        {            if( m_current != &m_header )            {                m_current  = m_current->next;                i++;            }            else            {                m_current = m_current->prev;            }        }        if( m_current == &m_header )        {            m_current = m_current->next;        }        return (i == this->m_step);    }    ~DualCircleList()    {        clear();    }};}#endif // DUALCIRCLELIST_H

下来我们写点测试代码看看上面的代码有没有问题

main.cpp 源码

#include #include "DualCircleList.h"using namespace std;using namespace DTLib;int main(){    DualCircleList d1;    for(int i=0; i<5; i++)    {        d1.insert(0, i);        d1.insert(0, 5);    }    cout << "begin" << endl;    d1.move(d1.length()-1);    while( d1.find(5) != -1 )    {        if( d1.current() == 5 )        {            cout << d1.current() << endl;            d1.remove(d1.find(d1.current()));        }        else        {            d1.pre();        }    }    cout << "end" << endl;    for(int i=0; i
我们先来分析下，在插入 i 后，随后便插入 5。先打印出 5 个 5，随后删除这 5 个数，然后在打印出剩下的 4 ~ 0。看看结果是否如我们所分析的那样
"如何用Linux内核链表来实现DTLib中的双向循环链表"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！