我們在前面講解了 SeqList  線性表的相關特性，下來我們來分析下它的效率。如下

企業(yè)建站必須是能夠以充分展現(xiàn)企業(yè)形象為主要目的，是企業(yè)文化與產(chǎn)品對外擴展宣傳的重要窗口，一個合格的網(wǎng)站不僅僅能為公司帶來巨大的互聯(lián)網(wǎng)上的收集和信息發(fā)布平臺，成都創(chuàng)新互聯(lián)面向各種領域：人造霧等網(wǎng)站設計、成都全網(wǎng)營銷推廣解決方案、網(wǎng)站設計等建站排名服務。

template < typename T >
class SeqList : public List
{
protected:
    T* m_array;        // 順序存儲空間
    int m_length;      // 當前線性表長度
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)
    
    // 順序存儲線性表的數(shù)組訪問方式
    T& operator[] (int i);             // O(1)
    T& operator[] (int i) const;       // O(1)
    
    // 順序存儲空間的容量 
    virtual int capacity() const = 0;
};

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

        接下來我們來看看下面代碼正確嗎？為什么？

StaticList s1;
StaticList s2;

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

            本文標題：順序存儲線性表的分析（八）            

            轉載來源：http://weahome.cn/article/iidjdi.html