一、线性表的本质和操作

什么是线性表？

线性表是具有

相同类型

的n个

数据元素

的优先序列。

线性表（List）的表现形式：

1、零和多个数据元素的集合；

2、数据元素在位置上是有序排列的；

3、数据元素的

个数是有限

的；

4、数据元素的

类型必须相同

。

线性表的性质：

a0为线性表的第一个元素，只有一个后继；a（n-1）为最后一个元素，只有前驱；除了这两个外，其他元素，既有前驱，也有后继。

直接支持逐项访问和顺序存取。

如何在程序中描述和使用一个线性表？

先对线性表的操作进行抽象：插入元素、删除元素、获取元素、设置元素、获取长度、清空。

设计一个类模板来实现线性表的上述操作，并且将其设计为一个抽象类，针对不同类型的线性表功能设计，进行不同类型的子类设计。

上述操作的函数映射（面向对象的方法）为：

template <typename T>
class List : public Object
{
protected:
    List(){}
    List& operator= (const List&);
public:
    virtual bool insect(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;

};

抽象类无法定义对象，但是可以作为指针或者引用类型使用。在主函数中定义一个List类型的整型指针变量，编译成功。

int main()
{
    List<int> *l = NULL;

    return 0;
}

二、线性表的顺序存储结构（SeqList）

顺序存储的定义：线性表的顺序存储结构，指的是用一段

地址连续的存储单元

，

依次存储

线性表中的数据元素。

设计思路：可以使用一维数组来实现顺序存储结构。

    T* m_array; //存储空间
    int m_length;  //当前长度，使用capacity()函数来访问

顺序存储结构的元素获取：

1、判断目标位置是否合法； 2、将目标位置作为数组下标获取元素。

        bool get(int i,T& e) const
        {
            bool ret = ( (0 <= i) && (i< m_length));

            if(ret)
            {
                e = m_array[i];
            }

            return ret;
        }

元素插入：

1、判断是否合法； 2、插入后所有元素后移一个位置； 3、插入新元素； 4、线性表长度加1。

注意：原生数组有最大存储量。

        bool insert(int i, const T& e)
        {
            bool ret = ( (0 <= i) && ( i <= m_length) );

            ret = ret && (m_length < capacity());

            if (ret)
            {
                for( int p = m_length-1; p>=i; p--) //i之前的元素后移一位
                {
                    m_array[p + 1] = m_array[p];
                }

                m_array[i] = e;

                m_length++;
            }

            return ret;
        }

元素删除：

1、判断是否合法； 2、目标位置后的元素前移一位； 3、线性表长度减一。

        bool remove(int i)
        {
            bool ret = ( (0 <= i) && (i< m_length));

            if(ret)
            {
                for(int p = i;p<m_length-1;p++)  //i之后的元素前移一位
                {
                    m_array[p] = m_array[ p+ 1 ];
                }

                m_length--;
            }

            return ret;
        }

三、顺序存储结构的抽象实现（SeqList）

SeqList设计要点：

1、关键操作仍旧为抽象类，

存储空间的位置和大小

在子类中完成；（将capacity()函数声明为纯虚函数，在子类中实现，表示顺序存储空间的最大容量）

2、实现顺序存储结构线性表的关键操作（增、删、查、等）；

3、实现数组操作符，方便快速获取元素（重载两个操作符，const和非const版本）。

元素的设置和获取：

        bool set(int i,const T& e)
        {
            bool ret = ( (0 <= i) && (i< m_length));

            if(ret)
            {
                m_array[ i ] = e;

            }

            return ret;
        }

        bool get(int i,T& e) const
        {
            bool ret = ( (0 <= i) && (i< m_length));

            if(ret)
            {
                e = m_array[i];
            }

            return ret;
        }

重载数组操作符：

        T& operator[] (int i)
        {
            if( (0 <= i) && (i < m_length))
            {
                return m_array[i];
            }
            else
            {
                THROW_EXCEPTION(IndexOutOfBoundsException,"Parameter i is invalid..."); //自定义异常类抛出信息
            }
        }
        
        T operator[] (int i) const
        {
            return (const_cast<SeqList<T>&>(*this))[i]; //转换掉表达式的const性质
        }

此处的实现，并没有确定具体的存储空间在哪。

可以通过静态申请存储空间大小和动态申请存储空间，通过继承，实现静态线性表和动态线性表，它们的区别是什么？

四、静态线性表（StaticList）与动态线性表(DynamicList)的实现

StaticList

:使用原生数组作为顺序存储空间，使用模板参数决定数组大小。

template < typename T, int N>  //使用模板参数决定数组大小
class StaticList : public SeqList<T>
{
    protected:
        T m_space[N];   //使用原生数组作为顺序存储空间
    public:
        StaticList()
        {
            this->m_array = m_space;
            this->m_length = 0;
        }

        int capacity() const
        {
            return N;
        }
};

在主函数中对StaticList进行调用：

    StaticList<int, 5> sl;

    for(int i=sl.capacity(); i >= 0; i--)
    {
        sl.insert(0, i);
    }

    for(int i=0; i<sl.length(); i++)
    {
        cout << sl[i] << endl;
    }

    sl[3] *= sl[3];

    for(int i=0; i<sl.length(); i++)
    {
        cout << sl[i] << endl;
    }

DynamicList:

申请连续堆空间作为顺序存储空间；动态设置顺序存储空间；保证重置顺序存储空间时的异常安全性。

什么是异常安全？

不泄露任何资源，不允许破坏数据。

函数异常安全的基本保证：

如果异常被抛出，对象内的任何成员仍能保持有效状态；没有数据的破坏以及资源泄露。

构造函数用来动态申请空间，定义整型的capacity，用来表示申请的空间大小。

申请空间后必须进行非空检查。

    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...");
        }
    }

定义一个

resize()

函数用来实现动态设置顺序存储空间的大小。（必须考虑重置前后的大小是否一致，不一致再进行操作）

    void resize(int capacity)    //动态设置 顺序存储空间的大小
    {
        if(capacity != m_capacity)
        {
            T* array = new T[capacity];    //保证数据元素没丢掉，即重置之后，剩余的元素不能丢失，用m_array来保存旧的，array来保存新的

            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;  // delete[] this->m_array 只要发生异常，线性表对象不可用

                this->m_array =array;
                this->m_length = length;
                this->m_capacity = capacity;    //temp的作用在于保重置前的数据存储空间

                delete[] temp;  //即便异常返回，线性表对象依然可用
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException,"");
            }
        }

    }

针对resize()函数的实现，必须注意一下几点：

保证复制前，数据元素不至于丢失。

delete会调用析构函数，如果抛出异常（泛指类型为类类型的话），线性表对象将不可用。

保存在temp后，即使发生异常，线性表对象依旧可用。

在析构函数中，对构造函数中申请的堆空间进行释放。

    ~DynamicList()
    {
        delete[] this->m_array;
    }

两种线性表的效率分析：大O表示法

时间复杂度：

        bool insert(int i, const T& e);  //O(n)

        bool remove(int i);//O(n)

两个相同的SeqLis，插入和删除操作的平均耗时是否相同？

答案是不同的。必须注意赋值、删除时的

操作对象

。比如int直接赋值即可，但是对于类类型或者自定义类类型，就可能需要进行拷贝构造等操作，时间复杂度一样，但是耗时肯定是不同的。

下面的代码正确吗？为什么？

在上面的代码中，s2指向了s1new出来的空间的地址，所以当对s1进行delete操作时，已经将new出来的空间还了回去，再进行delete s2，将会出现同一个堆空间被释放两次，行为是未定义的。

如何解决？——深拷贝（deep copy）

C++ Primer Plus第436页:如果类中包含了使用new初始化的指针成员，应对定义一个复制构造函数，以复制指向的数据，而不是指针，这被称为深度拷贝。

复制的另一种形式（成员复制或浅复制）只是复制指针值。

浅复制仅浅浅地复制指针信息，而不会深入“挖掘”以复制指针引用的结构。

下面的代码正确吗？为什么？

当对d2进行拷贝构造的时候，是将d2直接指向了d1的存储空间，用d1来初始化d2，所以实际上他们指向的是同一块存储空间。（C++ Primer Plus第434页：

隐式复制构造函数是按值进行复制的

，即上述代码复制的并不是int型数据，而是一个指向int型数据的指针，也就是说将d2=d1后，得到的是两个指向同一组数据的指针，再进行对象析构的时候，会将d1(d2）指向的内存释放两次，会导致不确定、可能有害的结果）。

对于容器类型的类，可以考虑禁止拷贝构造和赋值操作。

代码实现：将拷贝构造函数声明为保护，不需实现，赋值操作符也声明为保护。注：需手动实现构造函数。

protected:
    List(const List&);
    List& operator= (const List&);

添加代码后将无法实现赋值和拷贝：

int main()
{
    DynamicList<int> sl(5);
    DynamicList<int> sn(5);
    //DynamicList<int> sn =  sl;  报错

    //sn = sl;  报错
    return 0;
}

在线性表尾部直接添加参数，重载insert()：

        bool insert(const T &e) //直接在线性表的尾部添加参数
        {
            return insert(m_length, e);
        }

下面的代码正确吗？为什么？

    StaticList<int , 5> list;

    for(int i=0; list.capacity(); i++)
    {
        list[i] = i*i;
    }

答案：不正确

；

在实现数组访问操作符的重载时，对数组内容先进行了检查：

T& operator[] (int i)
        {
            if( (0 <= i) && (i < m_length))
            {
                return m_array[i];
            }
            else
            {
                THROW_EXCEPTION(IndexOutOfBoundsException,"Parameter i is invalid...");
            }
        }

当数组内没有元素的时候(未进行insert()操作）时，将不能访问数组元素。

线性表不是数组，线性表必须先插入元素，再能使用操作符[]访问元素。

顺序存储结构线性表提供了数组操作符重载，

通过重载能够方便快捷的获取目标位置处的数据层元素（实现顺序存储结构线性表的意义）

，在具体的使用形式上类似数组，但是本质不同，不能代替数组使用。

五、数组类的实现

在上一节的最后可以发现，线性表很容易被当做数组使用（功能上的缺陷），但是由于本质不同，两者是不同的，且效率有隐患。——实现一个可以代替原生数组的数组类。

需求分析：创建数组类必须能够

替代原生数组

的使用

数组类包含长度信息；

数组类能够主动发现越界访问（数组是一片连续的存储空间）。

父类Array

实现要点：

1、抽象类模板，

存储空间的位置和大小

由子类完成；

2、重载数组操作符，判断访问下标是否合法；

3、提供数组长度的抽象访问函数；

4、提供

数组对象间的复制操作

。

template < typename T >
class Array : public Object
{
protected:
    T* m_array;
public:
    virtual bool set(int i ,const T& e) //O(1)
    {
    }

    virtual bool get(int i ,T& e) const  //O(1)

    {
    }

    virtual int length() const = 0;  

T& operator[] (int i)

//O(1)

{ } T& operator[] (int i) const

//O(1)

{ }};

StaticArray设计要点：类模板

1、封装原生数组

2、使用

模板参数决定数组大小

3、实现函数

返回数组长度

4、

拷贝构造

和赋值操作

template < typename T ,int N>
class StaticArray : public Array<T>
{
protected:
    T m_space[N];
public:
    StaticArray()
    {
        this->m_array = m_space;  //将父类的m_array挂接在m_space
    }

    StaticArray( const StaticArray<T, N>& obj)
    {
        this->m_array = m_space;  //原生数组

        for(int i=0; i<N; i++)  //具体的复制
        {
            m_space[i] = obj.m_space[i];
        }
    }

    StaticArray<T,N>& operator = (const StaticArray<T,N>& obj)
    {
       if(this != &obj)
       {
         for(int i=0; i<N; i++)
         {
            m_space[i] = obj.m_space[i];
         }
       }
       return *this;
    }

    int length() const
    {
        return N;
    }
};

使用StaticArray可以进行拷贝构造和赋值操作，具体实现如下：

int main()
{
    StaticArray<int, 5> sa;

    for(int i=0; i<sa.length(); i++)
    {
        sa[i] = i;
    }

    for(int i=0; i<sa.length(); i++)
    {
        cout << sa[i] << endl;
    }

    StaticArray<int, 5> sa1;
    sa1 = sa;

    for(int i=0; i<sa1.length(); i++)
    {
        cout << sa1[i] << endl;
    }

    for(int i=0; i<sa.length(); i++)
    {
        sa[i] = i*i;
    }

    for(int i=0; i<sa.length(); i++)
    {
        cout << sa[i] << endl;
    }

    //sa[6] = 100;  越界异常可以被抛出异常（重载数组访问操作符中会对数组下标进行检查）
    
    return 0;
}

利用原生数组实现了静态数组类的实现，那么如何实现动态数组的实现？两者又有何异同呢？

DynamicArray设计要点：类模板

1、

动态确定内部数组空间的大小

2、实现函数

返回数组长度

3、拷贝构造和赋值操作

下面代码实现了代码优化。

template < typename T>
class DynamicArray : public Array<T>
{
protected:
    int m_length;

    T* copy( T* array, int len , int newlen) //在堆空间中申请新的内存空间，并执行拷贝操作
    {//复制前进行长度判断、异常安全检查
    }

    void update(T* array, int length) //将指定的堆空间作为内部存储数组使用，更新数据
    {//注意异常安全，对数据先进性保存，使用局部指针指向m_array指向的堆空间，操作成功后删除临时申请的堆空间
    }

    void init(T* array, int length) //对象构造时的初始化操作
    {
    }

public:
    DynamicArray(  int length = 0)
    {
        init(new T[length],length);
    }

    DynamicArray(const DynamicArray<T>& obj)
    {
        T* array = copy(obj.m_array,obj.m_length,obj.m_length);

        init(array,obj.m_length);
    }

    DynamicArray<T>& operator= (const DynamicArray<T>& obj)
    {
        if(this != &obj)   //出过BUG
        {
            update(copy(obj.m_array, obj.m_length, obj.m_length), obj.m_length);
        }
    }

    int length() const
    {
        return m_length;
    }

    void resize(int length)
    {
        update(copy(this->m_array, m_length, length),length);
    }

    ~DynamicArray()
    {
       delete[] this->m_array;
    }

};

在主函数中运行如下：

int main()
{
    DynamicArray<int> s1(5);

    for(int i=0; i<s1.length(); i++)
    {
        s1[i] = i*i;
    }

    for(int i=0; i<s1.length(); i++)
    {
        cout << s1[i] << endl;
    }

    DynamicArray<int> s2(10);

    s2 = s1;

    for(int i=0; i<s2.length(); i++)
    {
        cout << s2[i] << endl;
    }

    s2.resize(3);

    for(int i=0; i<s2.length(); i++)
    {
        cout << s2[i] << endl;
    }

    //s2[5] = 100; //越界

    return 0;
}

数组对象能够代替原生的数组，并且使用上功能更多，更安全。

代码优化是项目开发过程中不可或缺的环节，对于重复代码，使用函数模板进行封装。