數(shù)據(jù)結(jié)構(gòu)--線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

一 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

A.鏈?zhǔn)酱鎯Φ亩x
為了表示每個數(shù)據(jù)元素與直接后繼元素之間的邏輯關(guān)系；數(shù)據(jù)元素除了存儲本身的信息外，還需要存儲其直接后繼的信息
圖示

B鏈?zhǔn)酱鎯壿嫿Y(jié)構(gòu)
基于鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表中，每個結(jié)點都包含數(shù)據(jù)域和指針域
1.數(shù)據(jù)域：存儲數(shù)據(jù)元素本身
2.指針域：存儲相鄰結(jié)點的地址
圖示

C鏈表中的基本概念
1.頭結(jié)點--鏈表中的輔助結(jié)點，包含指向第一個數(shù)據(jù)元素的指針(方便插入和刪除)
2.數(shù)據(jù)結(jié)點--鏈表中代表數(shù)據(jù)元素的結(jié)點，表現(xiàn)形式為:(數(shù)據(jù)元素，地址)
3.尾節(jié)點--鏈表中的最后一個數(shù)據(jù)結(jié)點，包含的地址信息為空
代碼表示為

struct Node:public Object
{
    T value;
    Node* next;//指向后繼節(jié)點的指針
};

單鏈表的內(nèi)部結(jié)構(gòu)

頭結(jié)點在單鏈表中的意義是:輔助數(shù)據(jù)元素的定位，方便插入個刪除操作；因此，頭結(jié)點不存儲實際的數(shù)據(jù)元素
D插入與刪除的實現(xiàn)
a.插入數(shù)據(jù)元素
1.從頭結(jié)點開始，通過一個current指針定位到目標(biāo)位置
2.從堆空間申請新得Node結(jié)點
3.執(zhí)行操作
圖示

b.刪除操作
1.從頭結(jié)點開始，通過current指針定位到目標(biāo)位置
2.使用toDel指針指向需要刪除得結(jié)點
3.執(zhí)行操作
圖示

二 鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的實現(xiàn)

A.抽象類List的代碼如下

#include "Object.h"

namespace MyLib
{
//List抽象類
    template <typename T>
    class List:public Object
    {
    protected:
        List(const List&);
        List& operator=(const List&);//避免賦值操作
    public:
        List(){}
        virtual bool insert(const T&e)=0;//鏈表的插入
        virtual bool insert(int i,const T&e)=0;//重載版本
        virtual bool remove(int i)=0;//鏈表的刪除
        virtual bool set(int i,const T&e)=0;//
        virtual int find(const T&e)const=0;
        virtual bool get(int i,T&e)const=0;
        virtual int length()const=0;
        virtual void clear()=0;
    };
}

B.LinkList設(shè)計要點
1.類模板，通過頭結(jié)點訪問后繼結(jié)點
2.定義內(nèi)部結(jié)點類型，用于描述數(shù)據(jù)域和指針域
3.實現(xiàn)線性表的關(guān)鍵操作(增,刪,查,等)
LinkList的定義，代碼如下

template<typename T>
class LinkList:public List<T>
{
    protected:
        struct Node:public Object
        {
            T value;
            Node* next;
        };
        Node m_header;
        int m_length;
    public:
        LinkList();
        .......
};

LinkList的實現(xiàn)

template<typename T>
class LinkList:public List<T>
{
    protected:
        struct Node:public Object
        {
            T value;
            Node* next;
        };
        mutable Node m_header;
        int m_length;
    public:
        LinkList()
        {
            m_header.next=NULL;
            m_length=0;
        }
        bool insert(const T& e)
        {
            return insert(m_length,e);
        }

        bool insert(int i,const T& e)
        {
            bool ret=((0<=i)&&(i<=m_length));

            if(ret)
            {
                Node* node=new Node();

                if(node!=NULL)
                {
                    Node* current=&m_header;

                    for(int p=0;p<i;p++)
                    {
                        current=current->next;
                    }
                    node->value=e;
                    node->next=current->next;
                    current->next=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=&m_header;

                    for(int p=0;p<i;p++)
                    {
                        current=current->next;
                    }

                    Node* toDel=current->next;
                    current->next=toDel->next;
                    delete toDel;
                    m_length--;
                }
                return  ret;
        }

    bool set(int i,const T&e)
    {
        bool ret=((0<=i)&&(i<=m_length));

                if(ret)
                {
                    Node* current=&m_header;

                    for(int p=0;p<i;p++)
                    {
                        current=current->next;
                    }

                    current->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)
                {
                    Node* current=&m_header;

                    for(int p=0;p<i;p++)
                    {
                        current=current->next;
                    }
                    e=current->next->value;
                }
                return  ret;
    }

    int length()const
    {
        return m_length;
    }

    void clear()
    {
        while(m_header.next)
        {
            Node* toDel=m_header.next;
            m_header.next=toDel->next;
            delete toDel;
        }
        m_length=0;
    }

    ~LinkList()
    {
        clear();
    }

在編譯器的實現(xiàn)結(jié)果如圖所示

三.順序表與單鏈表的對比分析

效率的深度分析：
a.插入和刪除
1.順序表：涉及大量數(shù)據(jù)對象的復(fù)制操作
2.單鏈表：只涉及指針操作，效率與數(shù)據(jù)對象無關(guān)
b.數(shù)據(jù)訪問
1.順序表：隨機(jī)訪問，可直接定位數(shù)據(jù)對象
2.單鏈表：順序訪問，必須從頭訪問數(shù)據(jù)對象，無法直接定位
工程開發(fā)中的選擇：
順序表：
1.數(shù)據(jù)元素的類型相對簡單，不涉及拷貝
2.數(shù)據(jù)元素相對穩(wěn)定，訪問操作遠(yuǎn)多于插入和刪除操作
單鏈表：
1.數(shù)據(jù)元素的類型相對復(fù)雜，復(fù)制操作相對耗時
2.數(shù)據(jù)元素不穩(wěn)定，需要經(jīng)常插入和刪除，訪問操作較少
總結(jié)：
1.線性表中元素的查找依賴于相等比較操作符
2.順序表適用于訪問需求量較大的場合(隨機(jī)訪問)
3.單鏈表適用于數(shù)據(jù)元素頻繁插入刪除的場合(順序訪問)
4.當(dāng)數(shù)據(jù)類型相對簡單時,順序表和單鏈表的效率不相上下

四.單鏈表的遍歷與優(yōu)化

a.代碼的優(yōu)化

在單鏈表的實現(xiàn)中有代碼的重復(fù)

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

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

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

            return ret;
        }

       Node* create()
        {
            return new Node();
        }

        void destroy(Node* pn)
        {
            delete pn;
        }

插入部分的修改如圖所示

b.單鏈表的遍歷設(shè)計思路
當(dāng)前實現(xiàn)的單鏈表類不能以線性的時間復(fù)雜度完成單鏈表的遍歷，所以需要重新設(shè)計一種思路

1.在單鏈表的內(nèi)部定義一個游標(biāo)(Node* m_current)
2.遍歷開始前將游標(biāo)指向位置為0的數(shù)據(jù)元素
3.獲取游標(biāo)指向的數(shù)據(jù)元素
4.通過結(jié)點中的next指針移動游標(biāo)

c.遍歷函數(shù)原型設(shè)計
bool move(int i,int step=1);//step每次結(jié)點的移動
bool end();
T current();
bool next();
代碼實現(xiàn)如下

/*遍歷函數(shù)的實現(xiàn)*/
        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);
        }

最終的實現(xiàn)如下圖所示


小結(jié)：
1.單鏈表的遍歷需要在線性時間內(nèi)完成
2.在單鏈表內(nèi)部定義游標(biāo)變量，通過游標(biāo)遍歷提高效率
3.遍歷相關(guān)的成員函數(shù)是相互依賴，相互配合的關(guān)系
4.封裝結(jié)點的申請和刪除操作更有利于增強(qiáng)擴(kuò)展性