顺序存储线性表的分析（八）

我们在前面讲解了 SeqList 线性表的相关特性，下来我们来分析下它的效率。如下

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)        // 顺序存储线性表的数组访问方式    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 类型的数字和插入一个 string 类型的字符串，两个效率能一样吗？数字肯定是效率非常高的，但是字符串就涉及到字符串的 copy 了，因此效率肯定肯定没有数字的高。

接下来我们来看看下面代码正确吗？为什么？

StaticList s1;StaticList s2;for(int i=0; i
我们咋一看，感觉这段代码没问题。申请了两个 StaticList 类型的指针数组，然后再在 s1 中插入元素，将 s1 赋值给 s2，最后删除两个指针数组。我们仔细想想，在 s1 赋值给 s2 的时候，s2 同时也指向了 s1 数组的地址，再次进行两个相同地址的释放，难道代码不会出错吗？肯定会啊。我们再来看看下面这段代码正确吗？
void func(){    DynamicList d1(5);    DynamicList d2 = d1;        for(int i=0; i
我们在定义 d2 的时候，进行了拷贝构造，那么后面的插入操作便会出现问题。会将 d2 的操作覆盖掉 d1 的结果，因此会出现我们不想看到的结果。
那么对于容器类型的类，我们可以考虑禁用，方法是将它们都声明为 protected 属性就行。那么我们之前的 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 bool get(int i, T& e) const = 0;    virtual int length() const = 0;    virtual void clear() = 0;};
将拷贝构造和赋值操作声明为 protected，那么就不会出现上面的问题了。我们来看看下面的代码正确吗？
int main(){    StaticList list;        for(int i=0; i
在这份代码中，我们将线性表当成数组来使用了，线性表必须先插入元素，才能使用操作符 [] 访问元素。顺序存储结构线性表提供了数组操作符重载，通过重载能够快捷方便的获取目标位置处的数据元素，再具体的使用方式上类似数组，但是由于本质不同，不能代替数组使用。那么我们就有必要来开发一个数组类了。数组类的结构如下所示
通过今天的学习，总结如下：1、线性表作为容器类，应该避免拷贝构造和拷贝赋值；2、顺醋存储线性表可能被当成数组误用。