美文网首页
33_双向循环链表的实现

33_双向循环链表的实现

作者: 编程半岛 | 来源:发表于2018-07-12 14:55 被阅读32次

关键词:双向循环链表

0. 课程目标

  • 使用Linux内核链表实现双向循环链表
  • template < typename T > class DualCircleList

1. 双向循环链表的设计思路

数据结点之间在逻辑上构成双向循环链表头结点仅用于在结点的定位

双向循环链表原理图
双向循环链表继承层次结构图

2. 双向循环链表的实现思路

  • 通过模板定义DualCircleList类,继承自DualLinkList
  • DualCircleList内部使用Linux内核链表进行实现
  • 使用struct list_head定义DualCircleList的头结点
  • 特殊处理:循环遍历时忽略头结点

3. 双向循环链表的实现要点

  • 通过list_head进行目标结点定位position(i)
  • 通过list_entrylist_head指针转换为目标结点指针
  • 通过list_for_each实现int find(const T& e)函数
  • 遍历函数中的next()pre()需要考虑跳过头结点

4. 代码实现

DualCircleList.h

#ifndef DUALCIRCLELIST_H
#define DUALCIRCLELIST_H

#include "LinuxList.h"
#include "DualLinkList.h"

namespace DTLib
{

template < typename T >
class DualCircleList : public DualLinkList<T>
{
protected:
    struct Node : public Object
    {
        list_head head;
        T value;
    };

    list_head m_header;
    list_head* m_current;
    list_head* position(int i) const;
    int mod(int i) const;

public:
    DualCircleList();
    bool insert(const T& e);               // O(n)
    bool insert(int i, const T& e);        // O(n)
    bool remove(int i) ;                   // O(n)
    bool set(int i, const T& e);           // O(n)
    T get(int i) const;            // O(n)
    bool get(int i, T& e) const;           // O(n)
    int find(const T &e) const;            // O(n)
    int length() const ;                   // O(1)
    void clear();                          // O(n)

    /* 游标遍历相关函数 */
    bool move(int i, int step);
    bool end();
    bool next();
    bool pre();
    T current();
    ~DualCircleList();
};

template < typename T >
list_head* DualCircleList<T>::position(int i) const
{
    list_head* ret = const_cast<list_head*>(&m_header);

    for(int pos=0; pos<i; ++pos)
    {
        ret = ret->next;
    }

    return ret;
}

template < typename T >
int DualCircleList<T>::mod(int i) const
{
    return (this->m_length == 0) ? 0 : (i % this->m_length);
}

}

template < typename T >
DualCircleList<T>::DualCircleList()
{
    m_current = NULL;
    this->m_length = 0;
    this->m_step = 1;

    INIT_LIST_HEAD(&m_header);  //  初始化头结点
}

template < typename T >
bool DualCircleList<T>::insert(const T& e)
{
    return insert(this->m_length, e);
}

template < typename T >
bool DualCircleList<T>::insert(int i, const T& e)
{
    bool ret = true;

    i = i % (this->m_length + 1);

    Node* node = new Node();

    if( node != NULL )
    {
        node->value = e;
        list_add_tail(&(node->head), position(i)->next);
        ++this->m_length;
    }
    else
    {
        THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to insert new element in DualCircleList...");
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::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( this->m_current == toDel )
        {
            this->m_current = this->m_current->next;
        }

        list_del(toDel);
        --this->m_length;
        delete list_entry(toDel, Node, head);
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::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;
}

template < typename T >
T DualCircleList<T>::get(int i) const
{
    T ret;

    if( get(i, ret) )
    {
        return ret;
    }
    else
    {
        THROW_EXCEPTION(IndexOutOfBoundsException, "Invaild parameter i to get element...");
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::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;
}

template < typename T >
int DualCircleList<T>::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;
}

template < typename T >
int DualCircleList<T>::length() const
{
    return this->m_length;
}

template < typename T >
void DualCircleList<T>::clear()
{
    while(this->m_length > 0)
    {
        remove(0);
    }
}


template < typename T >
bool DualCircleList<T>::move(int i, int step = 1)
{
    bool ret = true;

    i = mod(i);

    ret = ret && (i >= 0) && (i < this->m_length) && (step > 0);

    if( ret )
    {
        this->m_current =position(i)->next;
        this->m_step = step;
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::end()
{
    return (this->m_length == 0) || (this->m_current == NULL);
}

template < typename T >
bool DualCircleList<T>::next()
{
    int i = 0;

    while( ( i<this->m_step ) && ( !end() ) )
    {
        if(this->m_current != &this->m_header)
        {
            this->m_current = this->m_current->next;
            ++i;
        }
        else
        {
            this->m_current = this->m_current->next;
        }
    }

    if( this->m_current == &this->m_header )
    {
        this->m_current = this->m_current;
    }

    return (i == this->m_step);
}

template < typename T >
bool DualCircleList<T>::pre()
{
    int i = 0;

    while( ( i<this->m_step ) && ( !end() ) )
    {
        if(this->m_current != &this->m_header)
        {
            this->m_current = this->m_current->prev;
            ++i;
        }
        else
        {
            this->m_current = this->m_current->prev;
        }
    }

    if( this->m_current == &this->m_header )
    {
        this->m_current = this->m_current;
    }

    return (i == this->m_step);
}

template < typename T >
T DualCircleList<T>::current()
{
    if( !end() )
    {
        return list_entry(this->m_current, Node, head)->value;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No value at current position...");
    }
}
template < typename T >
DualCircleList<T>::~DualCircleList()
{
    clear();
}

#endif // DUALCIRCLELIST_H

5. 小结

  • Linux内核链表是带头结点的双向循环链表
  • DualCircleList使用Linux内核链表进行内部实现
  • DualCircleList在循环遍历时需要跳过头结点
  • list_head指针转换为目标结点指针时,使用list_entry

声明:此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记,文章中包含狄泰软件资料内容,一切版权归狄泰软件所有!
实验环境:ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4

相关文章

  • 33_双向循环链表的实现

    关键词:双向循环链表 0. 课程目标 使用Linux内核链表实现双向循环链表 template < typenam...

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

  • C++实现双向循环链表

    本次博文是关于利用C++模板的方式实现的双向循环链表以及双向循环链表的基本操作,在之前的博文C++语言实现双向链表...

  • 0x05双向循环链表

    1 双向循环链表创建 2 双向循环链表插入元素 3 遍历双向循环链表 4双向循环链表删除结点

  • C语言中的链表(3)②

    双向链表中的双向循环链表的实现 第一步,创建出节点和链表并且进行初始...

  • JavaScript数据结构与算法-链表练习

    链表的实现 一. 单向链表 二. 双向链表 三. 循环链表 练习 一. 实现advance(n)方法,使当前节点向...

  • 双向链表

    双向链表的结构 既然单链表有循环链表,双向链表当然也有双向循环链表,如下图: 问: 双向链表中某个节点p的后继节点...

  • Python数据结构-链表

    自己实现一遍果然感觉不一样 Python实现单链表 Python实现单项循环链表 Python实现双向链表

  • java实现单向循环链表

    链表图解 带头结点的链表: 不带头结点的链表: 区别 带头结点的链表容易代码实现不带头结点的容易实现循环链表和双向...

  • 链表

    链表 缺点:查找复杂有点:定点删除/插入元素 单链表 双向链表 循环链表 双向循环链表 数组与链表的区别 数据存储...

网友评论

      本文标题:33_双向循环链表的实现

      本文链接:https://www.haomeiwen.com/subject/curhpftx.html