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

        我们在前面讲解了 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、顺醋存储线性表可能被当成数组误用。
            
            
                        

            当前标题：顺序存储线性表的分析（八）            

            标题链接：http://shouzuofang.com/article/iidjdi.html