内射老阿姨1区2区3区4区_久久精品人人做人人爽电影蜜月_久久国产精品亚洲77777_99精品又大又爽又粗少妇毛片

單鏈表的優(yōu)化(十三)

        我們在之前實(shí)現(xiàn)了單鏈表,那么我們?nèi)绾伪闅v單鏈表中的每一個數(shù)據(jù)元素呢?肯定直接一個 for 循環(huán)就可以搞定啊,我們來看看當(dāng)前基于我們實(shí)現(xiàn)的單鏈表遍歷的方法,main.cpp 如下

成都創(chuàng)新互聯(lián)專注于秦淮企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站設(shè)計,購物商城網(wǎng)站建設(shè)。秦淮網(wǎng)站建設(shè)公司,為秦淮等地區(qū)提供建站服務(wù)。全流程按需定制網(wǎng)站,專業(yè)設(shè)計,全程項目跟蹤,成都創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

#include <iostream>
#include "LinkList.h"

using namespace std;
using namespace DTLib;

int main()
{
    LinkList<int> list;

    for(int i=0; i<5; i++)      // O(1)
    {
        list.insert(0, i);
    }

    for(int i=0; i<list.length(); i++) // O(n)
    {
        cout << list.get(i) << endl;
    }

    return 0;
}

        我們來看看輸出結(jié)果,看看是不是遍歷呢

單鏈表的優(yōu)化(十三)

        結(jié)果是正確的,我們來分析下上面的測試代碼的效率。第一個 for 循環(huán),因?yàn)槊看味际窃?0 位置處插入數(shù)據(jù)元素,因此它的時間復(fù)雜度是 O(1);而第二個 for 循環(huán),因?yàn)樗垦h(huán)一遍,因此它的時間復(fù)雜度為 O(n)。我們就奇怪了,明明同樣是兩個 for 循環(huán),效率竟然不相同。不能以線性的時間復(fù)雜度完成單鏈表的遍歷,那么此時新的需求就產(chǎn)生了:為單鏈表提供新的方法,在線性時間內(nèi)完成遍歷。

        下來說說設(shè)計思路,利用游標(biāo)的思想:

        1、在單鏈表的內(nèi)部定義一個游標(biāo)(Node* m_current);

        2、遍歷開始前將游標(biāo)指向位置為 0 的數(shù)據(jù)元素;

        3、獲取游標(biāo)指向的數(shù)據(jù)元素;

        4、通過結(jié)點(diǎn)中的 next 指針移動游標(biāo)。


        提供一組遍歷相關(guān)的函數(shù),以線性的時間復(fù)雜度完成遍歷鏈表,如下

單鏈表的優(yōu)化(十三)

        遍歷函數(shù)原型設(shè)計如下:

        bool move(int i, int step = 1);

        bool end();

        T current();

        bool next();

        下來我們來看看優(yōu)化后的 LinkList.h 是怎樣的,如下

LinkList.h 源碼

#ifndef LINKLIST_H
#define LINKLIST_H

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

namespace DTLib
{

template < typename T >
class LinkList : public List<T>
{
protected:
    struct Node : public Object
    {
        T value;
        Node* next;
    };

    mutable struct : public Object
    {
        char reserved[sizeof(T)];
        Node* next;
    } m_header;

    int m_length;
    int m_step;
    Node* m_current;

    Node* position(int i) const
    {
        Node* ret = reinterpret_cast<Node*>(&m_header);

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

        return ret;
    }
public:
    LinkList()
    {
        m_header.next = 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)
    {
        bool ret = ((0 <= i) && (i <= m_length));

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

            if( node != NULL )
            {
                Node* current = position(i);

                node->value = e;
                node->next = current->next;
                current->next = node;

                m_length++;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
            }
        }
    }

    bool remove(int i)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if( ret )
        {
            Node* current = position(i);
            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 )
        {
            position(i)->next->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 = ((0 <= i) && (i < m_length));

        if( ret )
        {
            e = position(i)->next->value;
        }

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

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

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

    bool end()
    {
        return (m_current == NULL);
    }

    T current()
    {
        if( !end() )
        {
            return m_current->value;
        }
        else
        {
            THROW_EXCEPTION(INvalidOPerationException, "No value at current position ...");
        }
    }

    bool next()
    {
        int i = 0;

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

        return (i == m_step);
    }

    ~LinkList()
    {
        clear();
    }
};

}

#endif // LINKLIST_H

 

main.cpp 源碼

#include <iostream>
#include "LinkList.h"

using namespace std;
using namespace DTLib;

int main()
{
    LinkList<int> list;

    for(int i=0; i<5; i++)      // O(1)
    {
        list.insert(0, i);
    }

    for(list.move(0); !list.end(); list.next()) // O(1)
    {
        cout << list.current() << endl;
    }

    return 0;
}

        我們來看看編譯結(jié)果

單鏈表的優(yōu)化(十三)

        我們看到結(jié)果還是正確的,證明我們上面代碼的編寫是沒有錯誤的。我們再來分析下,它每次移動,移動后 current 指針就停在那塊,等到下次移動的時候還是從這塊開始移動。也就是說,每次遍歷的時候,它只需要遍歷一次就可以輸出結(jié)果了,這樣的話它遍歷的時間復(fù)雜度就為 O(1) 了。我們再來將 new 和 delete 操作封裝下,方便后面的使用,具體封裝如下

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

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

        然后將下面的 new 和 delete 操作全部換成 create 和 destory 函數(shù)。我們來試下將 main.cpp 測試代碼中移動的 step 改為 2,那么它便輸出的是偶數(shù)了。我們來看看結(jié)果

單鏈表的優(yōu)化(十三)

        確實(shí)是輸出的只有偶數(shù)。那么我們移動的 step 為 10 呢?那它就應(yīng)該只輸出 4 了,我們再來看看結(jié)果單鏈表的優(yōu)化(十三)

        現(xiàn)在我們的 LinkList 類已經(jīng)近乎完美了,優(yōu)化后的效率遍歷的時候極大的提高了。通過今天對 LinkList 優(yōu)化的學(xué)習(xí),總結(jié)如下:1、單鏈表的遍歷需要在線性時間內(nèi)完成;2、在單鏈表內(nèi)部定義游標(biāo)變量,通過游標(biāo)變量提高效率;3、遍歷相關(guān)的成員函數(shù)是相互依賴,相互配合的關(guān)系;4、封裝結(jié)點(diǎn)的申請和刪除操作更有利于增強(qiáng)擴(kuò)展性。

分享名稱:單鏈表的優(yōu)化(十三)
URL鏈接:http://www.rwnh.cn/article16/jicigg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供搜索引擎優(yōu)化、企業(yè)建站網(wǎng)站營銷、定制網(wǎng)站、App設(shè)計微信小程序

廣告

聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)公司
叙永县| 湘潭市| 宁德市| 定西市| 白银市| 巴东县| 双江| 塔城市| 焉耆| 上杭县| 田阳县| 江西省| 马鞍山市| 汝城县| 雅江县| 新巴尔虎左旗| 古丈县| 枝江市| 邯郸市| 秦皇岛市| 金乡县| 襄城县| 富裕县| 平顺县| 罗源县| 获嘉县| 连云港市| 阆中市| 永善县| 牡丹江市| 阿荣旗| 通许县| 巩留县| 静宁县| 遂昌县| 本溪市| 蚌埠市| 澎湖县| 娄底市| 丰县| 叙永县|