第十八课顺序存储线性表的分析

　　这一节我们分析前面实现的线性表的功能和性能。

效率分析：

上图中给出了时间复杂度的分析，但是这还不是效率的分析。

长度相同的两个SeqList，插入和删除操作的平均耗时是否相同呢?

如下所示：

　　insert中最耗时的操作是那个for循环，假设两个SeqList，一个存的是int型，一个存的是string，它们的操作效率当然是不一样的，特别是当存一个很复杂的类对象时，for循环中的赋值操作会更耗时。

　　从上面的例子可以看出，评估一个算法的效率不能只看时间复杂度，时间复杂度只是一个参考指标，但并不是绝对的指标。我们还需要具体的分情况来考虑。

　　效率问题需要根据具体情况来看，基于顺序存储结构的线性表，就不适合使用类类型的对象来作为数据元素存储。

考察下面的代码：

s2=s1的赋值操作会变成下面的情形：

导致在释放的时候堆空间释放两次。可能会出现bug。

继续考察下面的代码：

用d1拷贝构造d2，并且在for循环中给d1、d2插入元素，执行这个函数会产生如下的情形：

　　执行完d2=d1，它们就指向了同一片内存，后面的插入操作会覆盖前面的操作，而且在析构时会将这片空间释放两次。

如何解决上面说到的这些问题呢？

对于容器类型的类，可以考虑禁用拷贝构造和赋值操作。这是一种简单粗暴的方法。容器类完全可以使用这种方法。

改造List.h如下：

 1 #ifndef LIST_H
 2 #define LIST_H
 3 
 4 #include "Object.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 template <typename T>
10 class List : public Object
11 {
12 protected:
13     List(const List&);
14     List& operator= (const List&);
15 public:
16     List() {}
17     virtual bool insert(const T& e) = 0;
18     virtual bool insert(int i, const T& e) = 0;
19     virtual bool remove(int i) = 0;
20     virtual bool set(int i, const T& e) = 0;
21     virtual bool get(int i, T& e) const = 0;
22     virtual int length() const = 0;
23     virtual void clear() = 0;
24 };
25 
26 }
27 
28 
29 #endif // LIST_H

13、14行我们将拷贝构造函数和赋值操作符的重载定义为了protected的，也就相当于禁用了拷贝构造和赋值操作。定义了拷贝构造函数后，编译器就不会帮我们生成默认的构造函数了，因此，16行我们自己定义一个。

此外，我们改造SeqList.h，添加一个insert函数的重载版本：

  1 #ifndef SEQLIST_H
  2 #define SEQLIST_H
  3 
  4 #include "List.h"
  5 #include "Exception.h"
  6 
  7 namespace DTLib
  8 {
  9 
 10 template <typename T>
 11 class SeqList : public List<T>
 12 {
 13 protected:
 14     T* m_array;   //顺序存储空间,具体在子类中指定
 15     int m_length; //当前线性表长度
 16 public:
 17     bool insert(int i, const T &e)
 18     {
 19         bool ret = ((0 <= i) && (i <= m_length));
 20 
 21         ret = ret && (m_length < capacity());
 22 
 23         if( ret )
 24         {
 25             for(int p = m_length -1; p >= i; p--)
 26             {
 27                 m_array[p + 1] = m_array[p];
 28             }
 29 
 30             m_array[i] = e;
 31 
 32             m_length++;
 33         }
 34 
 35         return ret;
 36     }
 37 
 38     bool insert(const T& e)
 39     {
 40         return insert(m_length, e);
 41     }
 42 
 43     bool remove(int i)
 44     {
 45         bool ret = ((0 <= i) && (i < m_length));
 46 
 47         if( ret )
 48         {
 49             for(int p = i; p < m_length - 1; p++)
 50             {
 51                 m_array[p] = m_array[p + 1];
 52             }
 53 
 54             m_length--;
 55         }
 56 
 57         return ret;
 58     }
 59 
 60     bool set(int i, const T &e)
 61     {
 62         bool ret = ((0 <= i) && (i < m_length));
 63 
 64         if( ret )
 65         {
 66             m_array[i] = e;
 67         }
 68 
 69         return ret;
 70     }
 71 
 72     bool get(int i, T &e) const
 73     {
 74         bool ret = ((0 <= i) && i < m_length);
 75 
 76         if( ret )
 77         {
 78             e = m_array[i];
 79         }
 80 
 81         return ret;
 82     }
 83 
 84     int length() const
 85     {
 86         return m_length;
 87     }
 88 
 89     void clear()
 90     {
 91         m_length = 0;
 92     }
 93     //顺序存储线性表的数组访问方式
 94     T& operator[](int i)
 95     {
 96         if((0 <= i) && (i < m_length))
 97         {
 98             return m_array[i];
 99         }
100         else
101         {
102             THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
103         }
104     }
105 
106     T operator[](int i) const
107     {
108         return (const_cast<SeqList<T>&>(*this))[i];
109     }
110 
111     //顺序存储空间的容量
112     virtual int capacity() const = 0;
113 };
114 
115 }
116 
117 #endif // SEQLIST_H

38-41行使我们的insert的重载版本。

main函数测试程序如下：

 1 #include <iostream>
 2 #include "List.h"
 3 #include "SeqList.h"
 4 #include "StaticList.h"
 5 #include "Exception.h"
 6 #include "DynamicList.h"
 7 
 8 using namespace std;
 9 using namespace DTLib;
10 
11 
12 int main()
13 {
14 
15     DynamicList<int> l(5);
16     DynamicList<int> n = l;
17 
18     return 0;
19 }

16行相当于拷贝构造，会出现编译错误，如下：

这说明我们禁用拷贝构造函数成功了。

将线性表当做数组来使用，下面的代码正确吗？

上面的程序直接执行会产生越界异常，这是为什么呢？我们的顺序表SeqList中确实重载了[]操作符，因此，可以以数组的形式访问线性表中的元素，但是前提是表中必须提前插入了元素，也就是表中相应的位置必须已经有元素了。SeqList中我们重载的[]操作符如下：

 1 T& operator[](int i)
 2     {
 3         if((0 <= i) && (i < m_length))
 4         {
 5             return m_array[i];
 6         }
 7         else
 8         {
 9             THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");
10         }
11     }

可以看到，当表中没有元素时，m_length是0，这时我们直接以数组下标的形式访问就会产生异常。

结论就是线性表有自己的使用方式，线性表不是数组。

　　顺序存储结构线性表提供了数组操作符重载，通过重载能够快捷方便的获取目标位置处的数据元素，在具体的使用形式上类似数组，但由于本质不同，不能代替数组使用。线性表中重载[]只是为了在使用线性表时能快捷方便的获取元素。

要想使用[]操作符，我们需要自己实现一个数组类来代替C++中的原生数组，如下：

小结：

　　顺序存储线性表的插入和删除操作存在重大的效率隐患

　　线性表作为容器类，应该避免拷贝构造和拷贝赋值

　　顺序存储线性表可能被当成数组误用

　　工程开发中可以考虑使用数组类代替原生数组使用

第十八课 顺序存储线性表的分析

第十八课顺序存储线性表的分析