1、循环链表

A.循环链表的介绍

a.概念上

1.任意数据元素都有一个前驱和一个后继

2.所有数据元素的关系构成一个逻辑上的环

b.实现上

1.循环链表是一种特殊的单链表

2.尾节点的指针域保存了首结点的地址

关系图如下

循环链表的继承层次结构

2、循环链表的实现思路

A.思路

1.通过模板定义CircleList类，继承自LinkList类

2.定义内部函数last_to_first();用于将单链表首尾相连

        Node* last()const//尾节点        {            return this->position(this->m_length-1)->next;//返回尾节点(m_length-1)        }        void last_to_first()const//将链表首尾相连        {            last()->next=this->m_header.next;//尾节点的next指针指向首节点        }					    int mod(int i)const//取余的实现        {            return (this->m_length==0) ? 0 : ( i % this->m_length);        }

3.特殊处理:首元素的插入操作和删除操作

4.重新实现:清空操作和遍历操作

B.实现要点

a.插入位置为0时

1.头结点和尾结点均指向新结点

2.新结点成为首节点插入链表

       bool insert(int i,const T& e)        {            bool ret=true;            i=i%(this->m_length+1);//i值取余            ret=LinkList<T>::insert(i,e);//调用父类的insert来实现子类的insert            if(ret&&(i==0))            {                last_to_first();            }            return ret;        }

b.删除位置为0时

1.头结点和尾结点指向位置为1的结点

2.安全销毁首结点

【领QT开发教程学习资料，点击→Qt开发（视频教程+文档+代码+项目实战）←莬费领取，先码住不迷路~】

        bool remove(int i)        {            bool ret= true;            i= mod(i);            if(i==0)            {                Node *toDel=this->m_header.next;                if(toDel!=NULL)                {                    this->m_header.next=toDel->next;                    this->m_length--;                    //链表不为空                    if(this->m_length>0)                    {                        last_to_first();                        if(this->m_current==toDel)                        {                            this->m_current=toDel->next;                        }                    }                    else                    { //链表为空，置空                        this->m_header.next=NULL;                        this->m_current=NULL;                    }                    this->destroy(toDel);//在最后一步删除首节点  避免了异常安全                }                else                {                    ret=false;                }            }            else            {                ret=LinkList<T>::remove(i);            }            return ret;        }

循环链表的完整实现代码如下

#include "LinkList.h"namespace MyLib{    template <typename T>    class CircleList:public LinkList<T>    {    protected:        typedef typename LinkList<T>::Node Node;        Node* last()const//尾节点        {            return this->position(this->m_length-1)->next;//返回尾节点(m_length-1)        }        void last_to_first()const//将链表首尾相连        {            last()->next=this->m_header.next;//尾节点的next指针指向首节点        }        int mod(int i)const        {            return (this->m_length==0) ? 0 : ( i % this->m_length);        }    public:        bool insert(const T& e)//重载        {            return insert(this->m_length,e);//调用重载的版本        }        bool insert(int i,const T& e)        {            bool ret=true;            i=i%(this->m_length+1);//i值取余            ret=LinkList<T>::insert(i,e);//调用父类的insert来实现子类的insert            if(ret&&(i==0))            {                last_to_first();            }            return ret;        }        bool remove(int i)        {            bool ret= true;            i= mod(i);            if(i==0)            {                Node *toDel=this->m_header.next;                if(toDel!=NULL)                {                    this->m_header.next=toDel->next;                    this->m_length--;                    //链表不为空                    if(this->m_length>0)                    {                        last_to_first();                        if(this->m_current==toDel)                        {                            this->m_current=toDel->next;                        }                    }                    else                    { //链表为空，置空                        this->m_header.next=NULL;                        this->m_current=NULL;                    }                    this->destroy(toDel);//在最后一步删除首节点  避免了异常安全                }                else                {                    ret=false;                }            }            else            {                ret=LinkList<T>::remove(i);            }            return ret;        }        bool set(int i, const T &e)        {            i=mod(i);            return LinkList<T>::set(i,e);//调用父类函数        }        T get(int i)const        {            i=mod(i);            return LinkList<T>::get(i);        }        T get(int i,const T&e) const        {            i=mod(i);            return LinkList<T>::get(i,e);        }        int find(const T &e)const        {            int ret=-1;            Node* slide=this->m_header.next;//指针slide指向首节点            for(int i=0;i<this->m_length;i++)//slide指针遍历每个元素            {                if(slide->value==e)                {                    ret=i;                    break;                }                slide=slide->next;            }            return ret;        }        void clear()        {            while(this->m_length>1)            {                remove(1);//这里取1的原因是效率更高            }            if(this->m_length==1)            {                Node* toDel=this->m_header.next;                this->m_header.next=NULL;                this->m_current=NULL;                this->m_length=0;                this->destroy(toDel);            }        }        bool move(int i, int step)//i表示位置        {            i=mod(i);            return LinkList<T>::move(i,step);        }        bool end()        {            return (this->m_length==0)||(this->m_current==NULL);        }        ~CircleList()//析构函数直接调用clear()函数        {            clear();        }    };}

1.循环链表是一种特殊的单链表

2.尾结点的指针域保存了首结点的地址

3.特殊处理首元素的插入操作和删除操作

4.重新实现清空操作和遍历操作

4、双向链表

由之前的单链表我们可以看到单链表存在的缺陷

1.单向性==>只能从头结点开始高效访问链表中的数据元素

2.缺陷==>如果需要逆向访问单链表中的数据元素将极其低效

新的线性表实现

设计思路:在单链表的结点中增加一个指针pre，用于指向当前结点的前驱结点

示意图

双向链表的继承层次结构

简单的图示来说明双向链表的插入和删除操作

插入操作

如图所示四个步骤完成操作

1.将插入结点的next指向next

2.current的next指向插入的结点

3.插入结点的pre指向curret

4.next的pre指向node

实现代码

bool insert(int i,const T&e){	bool ret=((0<=i)&&(i<= m_length));	if(ret)	{		Node* node=creat();				if(node!=NULL)		{			Node* current=positon();			Node* next=current->next;						node->value=e;			node->next=next;//步骤1			current->next=node;//步骤2						if(current!=reinterpret_cast<Node*>(&m_header))			{				node->pre=current;//步骤3			}			else			{				node->pre=NULL;			}						if(next!=NULL)			{				next-pre=node;			}			m_length++;		}		else		{			THROW_EXCEPTION(NoEoughMemoryException,"NoEoughMemory");		}	}	return ret;}

删除操作

删除部分3个步骤

1.将current的next指向next

2.将next的pre指向current

3.删除toDel

代码实现如下

        bool remove(int i)        {            bool ret=((0<=i)&&(i<m_length));            if(ret)            {                Node* current=position(i);                Node* toDel=current->next;                Node* next=toDel->next;                if(m_current==toDel)                {                    m_current=next;                }                current->next=next;//步骤1                if(next!=NULL)                {                    next->pre=toDel->pre;//步骤2                }                m_length--;                destroy(toDel);//步骤3                //m_length--;            }            return ret;        }

双向链表的具体实现

#include "List.h"#include "Exception.h"namespace MyLib{    template <typename T>    class DuaLinkList:public List<T>    {    protected:        struct Node :public Object        {            T value;//数据域   保存数据的值            Node* next;//指针域 指向后继节点的指针            Node* pre;        };        mutable struct:public Object//没有类型名的结构        {            char reserved[sizeof(T)];            Node* next;            Node* pre;        }  m_header;//头节点  辅助定位元素        int m_length;        int m_step;        Node* m_current;        Node* position(int i) const//程序优化        {            Node* ret=reinterpret_cast<Node*>(&m_header);//reinterpret_cast强制类型转换            for(int p=0;p<i;p++)            {                ret=ret->next;            }            return ret;        }        virtual Node* create()        {            return new Node();        }        virtual void destroy(Node* pn)        {            delete pn;        }    public:        DuaLinkList()        {            m_header.next=NULL;            m_header.pre=NULL;            m_length=0;            m_step=1;            m_current=NULL;        }        bool insert(const T&e)        {           return insert(m_length,e);        }        bool insert(int i,const T&e)//i表示插入的位置，e表示插入的数据        {            bool ret=((0<=i)&&(i<= m_length));//m_length表示链表的长度            if(ret)            {                Node* node=create();                if(node!=NULL)                {                    Node* current=position(i);//定位位置                    Node* next=current->next;//表示插入的节点的后继节点                    node->value=e;                    node->next=next;                    current->next=node;                    if(current!=reinterpret_cast<Node*>(&m_header))                    {                        node->pre=current;                    }                    else                    {                        node->pre=NULL;                    }                    if(next!=NULL)                    {                        next->pre=node;                    }                    m_length++;                }                else                {                    THROW_EXCEPTION(NoEoughMemoryException,"No ...");                }            }            return ret;        }        bool remove(int i)        {            bool ret=((0<=i)&&(i<m_length));            if(ret)            {                Node* current=position(i);                Node* toDel=current->next;                Node* next=toDel->next;                if(m_current==toDel)                {                    m_current=next;                }                current->next=next;                if(next!=NULL)                {                    next->pre=toDel->pre;                }                m_length--;                destroy(toDel);                //m_length--;            }            return ret;        }        bool set(int i,const T&e)        {             bool ret=((0<=i)&&(i<m_length));             if(ret)             {                 position(i)->next->value=e;             }             return ret;        }        int find(const T&e) const        {            int ret=-1;            int i=0;            Node* node=m_header.next;            while(node)            {                if(node->value==e)                {                    ret=i;                    break;                }                else                {                    node=node->next;                    i++;                }            }            return ret;        }        virtual T get(int i)const        {            T ret;            if(get(i,ret))            {                return ret;            }            else            {                THROW_EXCEPTION(indexOutOfBoundsException,"...");            }            return ret;        }        bool get(int i,T&e)const        {            bool ret=((0<=i)&&(i<m_length));            if(ret)            {                e=position(i)->next->value;            }            return ret;        }        int length()const        {            return m_length;        }        void clear()        {            while(m_length>0)            {                remove(0);            }        }        virtual bool move(int i,int step=-1)        {            bool ret= (0<=i)&&(i<m_length)&&(step>0);            if(ret)            {                m_current=position(i)->next;                m_step=step;            }            return ret;        }        virtual bool end()        {            return (m_current==NULL);        }        virtual T current()        {            if(!end())            {                return m_current->value;            }            else            {                THROW_EXCEPTION(InvalidOperationException,"...");            }        }        virtual bool next()        {            int i=0;            while((i<m_step)&& !end())            {                m_current=m_current->next;                i++;            }            return (i==m_step);        }        virtual bool pre()        {            int i=0;            while((i<m_step)&& !end())            {                m_current=m_current->pre;                i++;            }            return (i==m_step);        }        ~DuaLinkList()        {            clear();        }    };}

1.双向链表是为了弥补单链表的缺陷而重新设计的

2.在概念上，双向链表不是单链表，没有继承关系

3.双向链表中的游标能够直接访问当前结点的前驱和后继

4.双向链表是线性表概念的最终实现