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

 线性表的表现形式：数据元素个数有限，数据元素类型相同，数据元素是有序排列，数据元素个数为零或多个

 线性表的定义：线性表是具有相同类型的数据元素的有限序列。

 线性表的性质：一个表项对应于一个数据元素。线性表第一个元素只有一个后继，线性表最后一个元素只有一个前继，中间元素只有一个后记和一个前继。只能逐项访问线性表，顺序存储线性表。

 线性表的操作：插入元素，删除元素，获取元素值，设置元素值，获取线性表长度，将线性表的所有元素清零

 线性表在C++中表现为 ：线性表抽象类

List 抽象类。抽象类接口：不定义对象。定义纯虚函数（插入，删除，设置，获得，长度，清零）

Seqlist 抽象类。 抽象类模板：不定义对象。实现操作（增加，删除，查询，设置，长度，清零）添加（重载赋值操作符，存储空间最大容量）。不定义存储空间的位置和元素的大小。

StaticList 类。类模板：定义连续存储空间的位置（栈空间的原生数组），存储空间的大小（模板类型参数和数组长度）。

DynamicList 类。类模板：定义连续存储空间的位置（堆空间），存储空间的大小（动态设置）。异常安全，被异常抛出时对象成员保证有效状态，没有数据被破坏。

上列类关系图：

 

List.h

/*
* List类：线性表接口。
* 继承TopClass类，被SeqList继承。
* 实现纯虚函数：插入，删除，设置值，获得值，获得长度，清除线性表。
*
*/

#ifndef LIST_H
#define LIST_H

#include"TopClass.h"

namespace DSL
{
template <typename T>
class List: public TopClass 
{
    public:
    virtual bool insert(int pos, const T& obj) = 0;
    virtual bool remove(int pos) = 0;
    virtual bool set(int pos, const T& obj) = 0;
    virtual bool get(int pos, T& obj) const = 0;
    virtual int  length() const = 0;
    virtual void clean() = 0;
};

}

#endif
View Code

SeqList.h

/*
*      SeqList：线性表抽象类。
*    成员变量：m_array 存储空间指针
*              m_length 存储空间中的线性表长度
*    成员函数：insert()
*              remove()
*              set()
*              get()
*              length()   获得线性表长度
*              clear()    清除线性表
*              operator[] 重载数组成员访问符
*             capacity() 存储空间大小 
*          
*/

#ifndef SEQLIST_H
#define SEQLIST_H

#include"List.h"
#include"Exception.h"

namespace DSL
{
template <typename T>
class SeqList : public List<T>
{
    protected:
        int m_length;
        T *m_array;
    public:
        bool insert(int pos, const T & obj)
        {
            bool ret = ((pos >= 0) && (pos <= m_length));
            ret = ret && (m_length < capacity());
            if(ret)
                {
                    for(int post = m_length - 1; pos <= post; post--)
                    {
                        m_array[post + 1] = m_array[post];
                    }
                    m_array[pos] = obj;
                    m_length++;
                }
            return ret;
        }
        
        bool remove(int pos)
        {
            bool ret = ((0 <= pos) && (pos <= m_length-1));
            if(ret)
                {
                    for(int post = pos; post < m_length - 1; post++)
                    {
                        m_array[post] = m_array[post + 1];
                    }
                    m_length--;
                }
            return ret;
        }
        
        bool get(int pos, T& obj) const
        {
            bool ret = ((pos >= 0) && (pos <= m_length -1));
            if(ret)
            {
                obj = m_array[pos];
            }
            return ret;
        }
        bool set(int pos,const T& obj)
        {
            bool ret = ((pos >= 0) && (pos <= m_length -1));
            if(ret)
            {
                m_array[pos] = obj;
            }
            return ret;
        }
        
        int length() const
        {
            return m_length;
        }

        void clean()
        {
            m_length = 0;
        }
        
        T& operator[] (int pos)
        {
            if( pos >= 0 && pos <= m_length -1)
            {
                return m_array[pos];
            }
            else
            {
                THROW_EXCEPTION(IdexOutOfBoundException,"error: index out of bound!");
            }
        }

        T operator[] (int pos) const
        {
            return (const_cast<SeqList<T>&>(*this))[pos];
        }

        virtual int capacity() const = 0; 
};

}

#endif
View Code

StaticList.h

/*
*    StaticList：静态顺序存储链表
*    成员变量：m_space[] 静态数组
*
*    成员函数：StaticList() 初始化m_array指针指向线性表
*              capacity()   存储空间大小
*    
*    
*/

#ifndef STATICLIST_H
#define STATICLIST_H

#include"SeqList.h"

namespace DSL
{
    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;
        }

};

}

#endif
View Code

DynamicList.h

/*
*    DynamicList：动态顺序存储链表
*    成员变量：m_capacity        顺序存储空间大小
*            
*    成员函数：DynamicList       申请堆空间
*              capacity     返回堆空间大小m_capacity
*              resize       重新设置存储空间大小
*              ~DynamicList 归还空间
*/
#ifndef DYNAMICLIST_H
#define DYNAMICLIST_H

#include"SeqList.h"
#include"Exception.h"

namespace DSL
{
template <typename T>
class DynamicList : public SeqList<T>
{
    protected:
        int m_capacity;
    public:
        DynamicList(int size)
        {
            this->m_array = new T[size];
            if(this->m_array != NULL)
            {
                this->m_capacity = size;
                this->m_length = 0;
            }
            else
            {
                THROW_EXCEPTION(NotEnoughMemoryException,"error: no enough memory!");
            }
        }

        int capacity() const
        {
            return m_capacity;
        }

        void resize(int new_size)
        {
            if(new_size != m_capacity)
            {
                T* array_temp = new T[new_size];  // 如果直接将申请空间地址赋值给this->m_array，将会丢失原来的数据
                if(array_temp != NULL)
                {
                    int length_temp = (new_size > this->m_length ? this->m_length : new_size );
                    for(int i = 0; i < length_temp; i++)
                    {
                         array_temp[i] = this->m_array[i];  // 赋值操作符发重载函数发生异常？
                    }
                    T* temp_m_array = this->m_array;   //1.便于释放重定义大小前的空间
                                                       //2.如果直接delete this->m_array时，如果析构函数抛出异常将会直接返回，无法初始化成员变量
                    this->m_capacity = new_size;       // 异常安全
                    this->m_length = length_temp;
                    this->m_array  =array_temp;

                    delete[] temp_m_array;
                }
                else
                {
                    THROW_EXCEPTION(NotEnoughMemoryException,"error: no enough memory!");
                }
            }

        }

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

}

#endif
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zsy12138/p/10932761.html