中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

順序表和單鏈表的對比（十二）

        我們在之前學(xué)習(xí)了線性表和單鏈表的相關(guān)特性，本節(jié)博客我們就來看看它們的區(qū)別。首先提出一個問題：如何判斷某個數(shù)據(jù)元素是否存在于線性表中？那肯定是直接遍歷一遍了，我們來看看代碼

成都創(chuàng)新互聯(lián)公司擁有十多年成都網(wǎng)站建設(shè)工作經(jīng)驗(yàn),為各大企業(yè)提供成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)服務(wù)，對于網(wǎng)頁設(shè)計(jì)、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、重慶APP軟件開發(fā)、wap網(wǎng)站建設(shè)（手機(jī)版網(wǎng)站建設(shè)）、程序開發(fā)、網(wǎng)站優(yōu)化（SEO優(yōu)化）、微網(wǎng)站、申請域名等，憑借多年來在互聯(lián)網(wǎng)的打拼，我們在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了很多網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、網(wǎng)絡(luò)營銷經(jīng)驗(yàn)，集策劃、開發(fā)、設(shè)計(jì)、營銷、管理等網(wǎng)站化運(yùn)作于一體，具備承接各種規(guī)模類型的網(wǎng)站建設(shè)項(xiàng)目的能力。

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

using namespace std;
using namespace DTLib;

int main()
{
    LinkList<int> list;

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

    for(int i=0; i<list.length(); i++)
    {
        if( list.get(i) == 3 )
        {
            cout << list.get(i) << endl;
        }
    }

    return 0;
}

        我們判斷 3 是都存在于當(dāng)前線性表中，如果存在，便輸出?？纯摧敵鼋Y(jié)果

順序表和單鏈表的對比（十二）

        我們看到在查找的時候還得去手動遍歷一遍，感覺很麻煩。那么我們在之前的實(shí)現(xiàn)中，少了一個操作，那便是查找操作 find。它可以為線性表（List）增加一個查找操作，原型為 int find(const T& e) const;參數(shù)為帶查找的數(shù)據(jù)元素；返回值：>=0 時，則表示數(shù)據(jù)元素在線性表中第一次出現(xiàn)的位置；為 -1 時，則表示數(shù)據(jù)元素不存在。下面我們看看數(shù)據(jù)元素查找的示例代碼，如下

LinkList<int> list;

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

cout << list.find(3) << endl;    // ==> 1

        下來我們在 List.h 源碼中添加 find 操作，如下

List.h 源碼

#ifndef LIST_H
#define LIST_H

#include "Object.h"

namespace DTLib
{

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 bool get(int i, T& e) const = 0;
    virtual int find(const T& e) const = 0;
    virtual int length() const = 0;
    virtual void clear() = 0;
};

SeqList.h 源碼

#ifndef SEQLIST_H
#define SEQLIST_H

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

namespace DTLib
{

template < typename T >
class SeqList : public List<T>
{
protected:
    T* m_array;
    int m_length;
public:
    bool insert(int i, const T& e)
    {
        bool ret = ((0 <= i)  && (i <= m_length));

        ret = ret &&  (m_length < capacity());

        if( ret )
        {
            for(int p=m_length-1; p>=i; p--)
            {
                m_array[p+1] = m_array[p];
            }

            m_array[i] = e;
            m_length++;
        }

        return ret;
    }

    bool insert(const T& e)
    {
        return insert(m_length, e);
    }

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

        if( ret )
        {
            for(int p=i; p<m_length-1; p++)
            {
                m_array[p] = m_array[p+1];
            }

            m_length--;
        }

        return ret;
    }

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

        if( ret )
        {
            m_array[i] = e;
        }

        return ret;
    }

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

        if( ret )
        {
            e = m_array[i];
        }

        return ret;
    }

    int find(const T& e) const  // O(n)
    {
        bool ret = -1;

        for(int i=0; i<m_length; i++)
        {
            if( m_array[i] == e )
            {
                ret = i;
                break;
            }
        }

        return ret;
    }

    int length() const
    {
        return m_length;
    }

    void clear()
    {
        m_length = 0;
    }

    T& operator[] (int i)
    {
        if( (0 <= i) && (i < m_length) )
        {
            return m_array[i];
        }
        else
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
        }
    }
    T operator[] (int i) const
    {
        return (const_cast<SeqList<T>&>(*this))[i];
    }

    virtual int capacity() const = 0;
};

}

#endif // SEQLIST_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;

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

    ~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++)
    {
        list.insert(0, i);
    }

    cout << list.find(3) << endl;

    return 0;
}

        我們來看看結(jié)果

順序表和單鏈表的對比（十二）

        我們來查找下 -3 呢

順序表和單鏈表的對比（十二）

        我們看到如果查找的元素在里面，則返回 1；如果沒有，則返回 -1。那么我們?nèi)绻檎业氖穷惸?？那程序還會編譯通過嗎？我們來看看，main.cpp 源碼如下

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

using namespace std;
using namespace DTLib;

class Test
{
    int i;
public:
    Test(int v = 0)
    {
        i = v;
    }
};

int main()
{
    Test t1(1);
    Test t2(3);
    Test t3(3);
    LinkList<Test> list;

    return 0;
}

        編譯結(jié)果如下

順序表和單鏈表的對比（十二）

        編譯報錯了，我們并沒有改動 LinkList 中的代碼，為什么這塊會報錯呢？那么此時我們想要讓兩個類對象進(jìn)行相等的比較，可是我們并沒有定義 == 操作符，此時肯定會出錯。那么我們在類 Test 中進(jìn)行 == 操作符的定義，如下

class Test
{
    int i;
public:
    Test(int v = 0)
    {
        i = v;
    }
    
    bool operator == (const Test& obj)
    {
        return true;
    }
};

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

順序表和單鏈表的對比（十二）

        編譯是通過的，那么我們此時便覺得奇怪了。我們?yōu)槭裁匆?Test 類中定義 == 操作符呢，此時最好的解決辦法是在頂層父類 Object 中添加 == 和 ！= 操作符，然后將 Test 類繼承自 Object 類就可以了。

Object.h 源碼

#ifndef OBJECT_H
#define OBJECT_H

namespace DTLib
{

class Object
{
public:
    void* operator new (unsigned int size) throw();
    void operator delete (void* p);
    void* operator new[] (unsigned int size) throw();
    void operator delete[] (void* p);
    bool operator == (const Object& obj);
    bool operator != (const Object& obj);
    virtual ~Object() = 0;
};

}

#endif // OBJECT_H

Object.cpp 源碼

#include "Object.h"
#include <cstdlib>

namespace DTLib
{

void* Object::operator new (unsigned int size) throw()
{
    return malloc(size);
}

void Object::operator delete (void* p)
{
    free(p);
}

void* Object::operator new[] (unsigned int size) throw()
{
    return malloc(sizeof(size));
}

void Object::operator delete[] (void* p)
{
    free(p);
}

bool Object::operator == (const Object& obj)
{
    return (this == &obj);
}

bool Object::operator != (const Object& obj)
{
    return (this != &obj);
}

Object::~Object()
{

}

}

        此時的 main.cpp 代碼如下

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

using namespace std;
using namespace DTLib;

class Test : public Object
{
    int i;
public:
    Test(int v = 0)
    {
        i = v;
    }

    bool operator == (const Test& obj)
    {
        return (i == obj.i);
    }
};

int main()
{
    Test t1(1);
    Test t2(3);
    Test t3(3);
    LinkList<Test> list;

    list.insert(t1);
    list.insert(t2);
    list.insert(t3);

    cout << list.find(t2) << endl;

    return 0;
}

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

順序表和單鏈表的對比（十二）

        那么我們在 main.cpp 測試代碼中將 t1, t2, t3 對象插入到 list 中，然后查找 t2 是否存在，那么它肯定是存在的，因此會輸出 1。那么我們來分析下順序表和單鏈表的時間復(fù)雜度的對比，如下

順序表和單鏈表的對比（十二）

        我們看到順序表只有三個 O(n) ，而單鏈表幾乎是全部是 O(n)。從時間復(fù)雜度上來看，似乎順序表更占優(yōu)勢，那么我們在平時的開發(fā)中，為什么經(jīng)常見到的是單鏈表而不是順序表呢？在實(shí)際的工程開發(fā)中，時間復(fù)雜度只是一個參考指標(biāo)，對于內(nèi)置基礎(chǔ)類型，順序表和單鏈表的效率不相上下，而對于自定義類型來說，順序表在效率上低于單鏈表。在插入和刪除操作中，順序表涉及大量數(shù)據(jù)對象的復(fù)制操作，而單鏈表只涉及指針操作，效率與數(shù)據(jù)對象無關(guān)。對于數(shù)據(jù)訪問，順序表是隨機(jī)訪問，可直接定位數(shù)據(jù)對象；而對于單鏈表來說是順序訪問，必須從頭訪問數(shù)據(jù)對象，無法直接定位。

        一般在工程開發(fā)中，順序表主要用于：數(shù)據(jù)元素類型相對簡單，不涉及深拷貝；數(shù)據(jù)元素相對穩(wěn)定，訪問操作遠(yuǎn)多于插入和刪除操作。單鏈表主要用于：數(shù)據(jù)元素的類型相對復(fù)雜，復(fù)制操作相對耗時；數(shù)據(jù)元素不穩(wěn)定，需要經(jīng)常插入和刪除，訪問操作較少的情況。通過今天的學(xué)習(xí)，總結(jié)如下：1、線性表中元素的查找依賴于相等比較操作符（==）；2、順序表適用于訪問需求量較大的場合（隨機(jī)訪問）；3、單鏈表適用于數(shù)據(jù)元素頻繁插入刪除的場合（順序訪問）；4、當(dāng)數(shù)據(jù)類型相對簡單時，順序表和單鏈表的效率不相上下。

本文題目：順序表和單鏈表的對比（十二）
網(wǎng)頁鏈接：http://www.rwnh.cn/article48/jiesep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、網(wǎng)站改版、App開發(fā)、標(biāo)簽優(yōu)化、App設(shè)計(jì)、電子商務(wù)

廣告

聲明：本網(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è)網(wǎng)站維護(hù)公司
乌拉特后旗| 江达县| 太保市| 班戈县| 景泰县| 敦化市| 西藏| 旌德县| 郯城县| 邓州市| 宝鸡市| 涡阳县| 新丰县| 大兴区| 沿河| 德阳市| 康平县| 沙河市| 灵宝市| 当雄县| 从化市| 师宗县| 屯留县| 鄢陵县| 韶关市| 资阳市| 舟山市| 济宁市| 云霄县| 镇康县| 东丰县| 青州市| 仁寿县| 中宁县| 广丰县| 万全县| 巫溪县| 德江县| 德惠市| 土默特左旗| 绵竹市|