數(shù)據(jù)結(jié)構(gòu)--循環(huán)鏈表與雙向鏈表

一.循環(huán)鏈表

A.循環(huán)鏈表的介紹
a.概念上
1.任意數(shù)據(jù)元素都有一個前驅(qū)和一個后繼
2.所有數(shù)據(jù)元素的關(guān)系構(gòu)成一個邏輯上的環(huán)
b.實現(xiàn)上
1.循環(huán)鏈表是一種特殊的單鏈表
2.尾節(jié)點的指針域保存了首結(jié)點的地址
關(guān)系圖如下
、
循環(huán)鏈表的繼承層次結(jié)構(gòu)

二.循環(huán)鏈表的實現(xiàn)思路

A.思路
1.通過模板定義CircleList類，繼承自LinkList類
2.定義內(nèi)部函數(shù)last_to_first();用于將單鏈表首尾相連

        Node* last()const//尾節(jié)點
        {
            return this->position(this->m_length-1)->next;//返回尾節(jié)點(m_length-1)
        }

        void last_to_first()const//將鏈表首尾相連
        {
            last()->next=this->m_header.next;//尾節(jié)點的next指針指向首節(jié)點
        }

        int mod(int i)const//取余的實現(xiàn)
        {
            return (this->m_length==0) ? 0 : ( i % this->m_length);
        }

3.特殊處理:首元素的插入操作和刪除操作
4.重新實現(xiàn):清空操作和遍歷操作
B.實現(xiàn)要點
a.插入位置為0時
1.頭結(jié)點和尾結(jié)點均指向新結(jié)點
2.新結(jié)點成為首節(jié)點插入鏈表

       bool insert(int i,const T& e)
        {
            bool ret=true;

            i=i%(this->m_length+1);//i值取余

            ret=LinkList<T>::insert(i,e);//調(diào)用父類的insert來實現(xiàn)子類的insert

            if(ret&&(i==0))
            {
                last_to_first();
            }

            return ret;
        }

b.刪除位置為0時
1.頭結(jié)點和尾結(jié)點指向位置為1的結(jié)點
2.安全銷毀首結(jié)點

        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);//在最后一步刪除首節(jié)點  避免了異常安全
                }
                else
                {
                    ret=false;
                }
            }
            else
            {
                ret=LinkList<T>::remove(i);
            }

            return ret;
        }

循環(huán)鏈表的完整實現(xiàn)代碼如下

#include "LinkList.h"

namespace MyLib
{
    template <typename T>
    class CircleList:public LinkList<T>
    {
    protected:
        typedef typename LinkList<T>::Node Node;
        Node* last()const//尾節(jié)點
        {
            return this->position(this->m_length-1)->next;//返回尾節(jié)點(m_length-1)
        }

        void last_to_first()const//將鏈表首尾相連
        {
            last()->next=this->m_header.next;//尾節(jié)點的next指針指向首節(jié)點
        }

        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);//調(diào)用重載的版本
        }

        bool insert(int i,const T& e)
        {
            bool ret=true;

            i=i%(this->m_length+1);//i值取余

            ret=LinkList<T>::insert(i,e);//調(diào)用父類的insert來實現(xiàn)子類的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);//在最后一步刪除首節(jié)點  避免了異常安全
                }
                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);//調(diào)用父類函數(shù)
        }

        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指向首節(jié)點
            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()//析構(gòu)函數(shù)直接調(diào)用clear()函數(shù)
        {
            clear();
        }
    };
}

三.小結(jié)

1.循環(huán)鏈表是一種特殊的單鏈表
2.尾結(jié)點的指針域保存了首結(jié)點的地址
3.特殊處理首元素的插入操作和刪除操作
4.重新實現(xiàn)清空操作和遍歷操作

四.雙向鏈表

由之前的單鏈表我們可以看到單鏈表存在的缺陷
1.單向性==>只能從頭結(jié)點開始高效訪問鏈表中的數(shù)據(jù)元素
2.缺陷==>如果需要逆向訪問單鏈表中的數(shù)據(jù)元素將極其低效
新的線性表實現(xiàn)
設(shè)計思路:在單鏈表的結(jié)點中增加一個指針pre，用于指向當前結(jié)點的前驅(qū)結(jié)點
示意圖

雙向鏈表的繼承層次結(jié)構(gòu)

簡單的圖示來說明雙向鏈表的插入和刪除操作
插入操作

如圖所示四個步驟完成操作
1.將插入結(jié)點的next指向next
2.current的next指向插入的結(jié)點
3.插入結(jié)點的pre指向curret
4.next的pre指向node
實現(xiàn)代碼

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
代碼實現(xiàn)如下

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

雙向鏈表的具體實現(xiàn)

#include "List.h"
#include "Exception.h"

namespace MyLib
{
    template <typename T>
    class DuaLinkList:public List<T>
    {
    protected:
        struct Node :public Object
        {
            T value;//數(shù)據(jù)域   保存數(shù)據(jù)的值
            Node* next;//指針域 指向后繼節(jié)點的指針
            Node* pre;
        };

        mutable struct:public Object//沒有類型名的結(jié)構(gòu)
        {
            char reserved[sizeof(T)];
            Node* next;
            Node* pre;
        }  m_header;//頭節(jié)點  輔助定位元素
        int m_length;
        int m_step;
        Node* m_current;

        Node* position(int i) const//程序優(yōu)化
        {
            Node* ret=reinterpret_cast<Node*>(&m_header);//reinterpret_cast強制類型轉(zhuǎn)換

            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表示插入的數(shù)據(jù)
        {
            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;//表示插入的節(jié)點的后繼節(jié)點

                    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();
        }
    };
}

小結(jié)

1.雙向鏈表是為了彌補單鏈表的缺陷而重新設(shè)計的
2.在概念上，雙向鏈表不是單鏈表，沒有繼承關(guān)系
3.雙向鏈表中的游標能夠直接訪問當前結(jié)點的前驅(qū)和后繼
4.雙向鏈表是線性表概念的最終實現(xiàn)