线性表的顺序存储结构

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

在C++中的表现是什么样子的呢？
可以考虑用一个数组，一个固定大小的数组来作为存储介质存储线性表中的元素。

如何用C++里面的原生数组实现一个线性表。原生数组符合顺序存储的定义

设计思路
——可以用一维数组来实现顺序存储结构
　　存储空间：T* m_array;
　　当前长度：int m_length;

template <typename T>
class SeqList : public List<T>
{
protected:
    T* m_array;
    int m_length;
    ...
};
  

顺序存储结构的元素获取操作
——判断目标位置是否合法
——将目标位置作为数组下标获取元素

bool SeqList<T>:: 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 SeqList<T>:: insert(int i, const T& e)
{
    bool ret = ((0 <= i) && (i <= m_length)); //解释i<=m_length。5个手指头，可以在6个地方进行插入。
    ret = ret && ((m_length + 1) <= capacity()); //capacity()表示顺序存储结构的最大容量。为什么要做这个判断，因为
                                                 //现在使用的是C++中的原生数组来实现线性表，而原生数组就有一个预先定义好的最大存储量。
                                                 //每次插入之前，要判断一下当前的存储空间是不是用完了。
    
    if(ret)
    {
        for(int p=m_length-1; p>=i; p--) //从后面开始挪位置（最后的那个元素）。
        {
            m_array[p + 1] = m_array[p];
        }
        
        m_array[i] = e;
        m_length++;
    }
    
    return ret;
}

顺序存储结构的元素删除操作
1.判断目标位置是否合法
2.将目标位置后的所有元素前移一个位置
3.线性表长度减1

bool SeqList<T>:: remove(int i)
{
    bool ret = ((0 <= i) && (i < m_length));
                                                    
    if(ret)
    {
        for(int p=i; p<m_length-1; p++)
        {
            m_array[p] = m_array[p+1];
        }

        m_length--;
    }
    
    return ret;
}

实战预告