我們?cè)谇懊嬷v解了 SeqList  線性表的相關(guān)特性，下來(lái)我們來(lái)分析下它的效率。如下

沙灣網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站開(kāi)發(fā)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)建站公司2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專(zhuān)注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。

template < typename T >
class SeqList : public List
{
protected:
    T* m_array;        // 順序存儲(chǔ)空間
    int m_length;      // 當(dāng)前線性表長(zhǎng)度
public:
    bool insert(int i, const T& e);    // O(n)
    bool remove(int i);                // O(n)
    bool set(int i, const T& e);       // O(1)
    bool get(int i, T& e) const;       // O(1)
    int length() const;                // O(1)
    void clear();                      // O(1)
    
    // 順序存儲(chǔ)線性表的數(shù)組訪問(wèn)方式
    T& operator[] (int i);             // O(1)
    T& operator[] (int i) const;       // O(1)
    
    // 順序存儲(chǔ)空間的容量 
    virtual int capacity() const = 0;
};

       那么問(wèn)題來(lái)了，兩個(gè)長(zhǎng)度相同的 SeqList ，插入和刪除操作的平均耗時(shí)是否相同呢？插入操作的大O表示法是 O(n + 5)，等價(jià)于O(n)；而刪除操作是 O(n-1) ，等價(jià)于 O(n)。從時(shí)間復(fù)雜度上來(lái)說(shuō)，它們是相同的。我們?cè)賮?lái)想下，插入一個(gè) int 類(lèi)型的數(shù)字和插入一個(gè) string 類(lèi)型的字符串，兩個(gè)效率能一樣嗎？數(shù)字肯定是效率非常高的，但是字符串就涉及到字符串的 copy 了，因此效率肯定肯定沒(méi)有數(shù)字的高。

       接下來(lái)我們來(lái)看看下面代碼正確嗎？為什么？

StaticList s1;
StaticList s2;

for(int i=0; i
       我們咋一看，感覺(jué)這段代碼沒(méi)問(wèn)題。申請(qǐng)了兩個(gè) StaticList 類(lèi)型的指針數(shù)組，然后再在 s1 中插入元素，將 s1  賦值給 s2，最后刪除兩個(gè)指針數(shù)組。我們仔細(xì)想想，在 s1 賦值給 s2 的時(shí)候，s2 同時(shí)也指向了 s1 數(shù)組的地址，再次進(jìn)行兩個(gè)相同地址的釋放，難道代碼不會(huì)出錯(cuò)嗎？肯定會(huì)啊。我們?cè)賮?lái)看看下面這段代碼正確嗎？
void func()
{
    DynamicList d1(5);
    DynamicList d2 = d1;
    
    for(int i=0; i
       我們?cè)诙x d2 的時(shí)候，進(jìn)行了拷貝構(gòu)造，那么后面的插入操作便會(huì)出現(xiàn)問(wèn)題。會(huì)將 d2 的操作覆蓋掉 d1 的結(jié)果，因此會(huì)出現(xiàn)我們不想看到的結(jié)果。
       那么對(duì)于容器類(lèi)型的類(lèi)，我們可以考慮禁用，方法是將它們都聲明為 protected 屬性就行。那么我們之前的 List 類(lèi)代碼就可以優(yōu)化為這樣
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 length() const = 0;
    virtual void clear() = 0;
};
       將拷貝構(gòu)造和賦值操作聲明為 protected，那么就不會(huì)出現(xiàn)上面的問(wèn)題了。我們來(lái)看看下面的代碼正確嗎？
int main()
{
    StaticList list;
    
    for(int i=0; i
       在這份代碼中，我們將線性表當(dāng)成數(shù)組來(lái)使用了，線性表必須先插入元素，才能使用操作符 [] 訪問(wèn)元素。順序存儲(chǔ)結(jié)構(gòu)線性表提供了數(shù)組操作符重載，通過(guò)重載能夠快捷方便的獲取目標(biāo)位置處的數(shù)據(jù)元素，再具體的使用方式上類(lèi)似數(shù)組，但是由于本質(zhì)不同，不能代替數(shù)組使用。那么我們就有必要來(lái)開(kāi)發(fā)一個(gè)數(shù)組類(lèi)了。數(shù)組類(lèi)的結(jié)構(gòu)如下所示
       通過(guò)今天的學(xué)習(xí)，總結(jié)如下：1、線性表作為容器類(lèi)，應(yīng)該避免拷貝構(gòu)造和拷貝賦值；2、順醋存儲(chǔ)線性表可能被當(dāng)成數(shù)組誤用。
            

            當(dāng)前標(biāo)題：順序存儲(chǔ)線性表的分析（八）-創(chuàng)新互聯(lián)            

            標(biāo)題URL：http://weahome.cn/article/dedhee.html