基于前面实现的数据结构类模板基础，继续完成基于顺序存储结构的线性表的实现，继承关系图如下：

1.线性表简介1.1.线性表的表现形式零个多多个数据元素组成的集合数据元素在位置上是有序排列的数据元素的个数是有限的数据元素的类型必须相同1.2.线性表的抽象定义、性质

线性表是具有相同类型的n(>=)个数据元素的有限序列，(a0, a1, a2... an-1),其中ai是表项，n是表长度。
性质：

a0为线性表的第一个元素，只有一个后继an-1为线性表的最后一个元素，只有一个前驱其他数据项既有后继，也有前驱支持逐项和顺序存储1.3.线性表的抽象实现插入、删除数据元素获取、设置目标位置元素的值获取线性表的长度清空线性表

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;};1.4.总结：

线性表是数据元素的有序并且有限的集合，其中的数据元素类型相同，在程序中表现为一个特殊的数据结构，可以使用C++中的抽象类来表示，用来描述排队关系的问题。

2.线性表的顺序存储结构2.1.概念和设计思路

定义：
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表中的数据元素。

设计思路：
使用一维数组来实现存储结构：

// 存储空间：T* m_array; 当前长度：int m_length；template <typename T>class SeqList : public List<T>{protected: T* m_array; int m_length;};3.SeqList的设计要点抽象类模板，存储空间的大小和位置由子类完成；实现顺序存储结构线性表的关键操作（增、删、查、等）；提供数组操作符重载，方面快速获取元素；3.1SeqList实现

template <typename T>class SeqList : public List<T>{protected: T* m_array; // 顺序存储空间 int m_length; // 当前线性长度public: bool insert(int index, const T& e) { bool ret = ( (index>=0) && (index<=m_length) ); // <= 因为可以插入的点，必然比当前元素多1 if(ret && ( m_length < capacity() )) // 当前至少有一个空间可插入 { for(int p=m_length-1; p>=index; p--) { m_array[p + 1] = m_array[p]; } m_array[index] = e; m_length++; } return ret; } bool insert(const T& e) { return insert(m_length, e); } bool remove(int index) { bool ret = ( (index>=0) && (index<m_length) ); // 目标位置合法 <m_length if(ret) { for(int p=index; p<m_length-1; p++) // 注意思考此处的边界条件 { m_array[p] = m_array[p+1]; } m_length--; } return ret; } bool set(int index, const T& e) { bool ret = ( (index>=0) && (index<m_length) ); if(ret) { m_array[index] = e; } return ret; } bool get(int index, T& e) const { bool ret = ( (index>=0) && (index<m_length) ); if(ret) { e = m_array[index]; } return ret; } int length() const { return m_length; } void clear() { m_length = 0; } // 顺序存储表的数组访问方式 T& operator [] (int index) { if( (index>=0) && (index<m_length) ) { return m_array[index]; } else { THROW_EXCEPTION(IndexOutOfBoundsException, "index out of range..."); } } T operator [] (int index) const { static_cast<SeqList<T>&>(*this)[index]; // 去除const属性，然后调用非const版本实现 } // 顺序存储表的的容量 virtual int capacity() const = 0;};4.StaticList和DynamicList4.1.StaticList的设计要点：

类模板

使用原生数组做为顺序存储空间使用模板参数决定数组的大小

template < typename T, int N >class StaticList : public SeqList <T>{protected:T m_space[]; // 顺序存储空间，N为模板参数public:StaticList(); // 指定父类成员的具体值int capacity() const;};4.2. StaticList实现

template < typename T, int N >class StaticList : public SeqList <T>{protected: T m_space[N]; // 顺序存储空间，N为模板参数public: StaticList() // 指定父类成员的具体值 { this->m_array = m_space; this->m_length = 0; } int capacity() const { return N; }};4.3.DynamicList的设计要点：

类模板

申请连续堆空间做为顺序存储空间保证重置顺序存储空间的异常安全性
函数异常安全的概念：不允许任何内存泄露，不允许破坏数据函数异常安全的基本保证：如果有异常抛出，对象内的任何成员任然能保持有效状态，没有数据破话或者资源泄露。

template < typename T>class DynamicList : public SeqList <T>{protected:int capacity; // 顺序存储空间的大小public:DynamicList(int capacity); // 申请空间int capacity(void) const // 返回capacity的值 // 重置存储空间的大小void reset(int capacity);~DynamicList(); // 归还空间};4.4. DynamicList实现

template <typename T>class DynamicList : public SeqList<T>{protected: int m_capacity;public: DynamicList(int capacity) { this->m_array = new T[capacity]; if(this->m_array != NULL) { this->m_length = 0; this->m_capacity = capacity; } else { THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ..."); } } int capacity()const { return m_capacity; } void resize(int capacity) { if(capacity != m_capacity) { T* array = new T[capacity]; if(array != NULL) { int length = (this->m_length < capacity ? this->m_length : capacity); for(int i=0;i<length;i++) { array[i] = this->m_array[i]; } T* temp = this->m_array; this->m_array = array; this->m_length = length; this->m_capacity = capacity; delete[] temp; } else { THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ..."); } } } ~DynamicList() { delete[] this->m_array; }};5.顺序存储结构线性表分析5.1.时间复杂度

顺序存储结构线性表的效率为O(n)，主要受其插入和删除操作的影响（譬如插入操作时，要插入位置之后的数据要向后挪动） 。

5.2.问题

两个长度相同的顺序存储结构线性表，插入、删除操作的耗时是否相同？

不相同，对顺序存储结构线性表，其插入、删除操作的复杂度还取决于存储的数据类型，譬如一个普通类型和一个字符串类型/类类型就完全不同（对于复杂数据类型，元素之间移动时必然耗时很多）。从这个角度考虑，线性表的效率存在隐患。
花费多少5.3.禁用拷贝构造和赋值操作。

拷贝构造和赋值操作会导致两个指针指向同一个地址，导致内存重复释放。对于容器类型的类，可以考虑禁用拷贝构造和赋值操作。
原因： 1、对于生活中容器类的东西，我们无法对其进行赋值（譬如生活中我们不可能将杯子中的水进行复制，只能使用另一个杯子重新去获取等量的水）。
实现：将拷贝构造和赋值操作函数定义为proteced成员，在类的外部，不能使用。

protected:List(const List&){}List& operator = (const List&){}5.4.注意事项

线性表不能直接当做数组来使用
顺序存储结构线性表提供了数组操作符的重载，可以直接像数组一样，同过下标直接获取目标位置的元素，在具体的使用上类似数组，但是本质上不同，不能代替数组使用：

必须先进行插入操作，才能对其内部的数据进行操作。原生数组是自带空间的，可以直接操作。