15_线性表的顺序存储结构

关键词： 顺序存储 、 元素获取、元素插入、元素删除

1. 顺序存储的定义

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

2. 设计思路

1. 用一维数组来实现顺序存储结构
   存储空间：T* m_array;
   当前长度：int m_length;

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

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

template <typename T>
bool SeqList<T>::get(int i, T &e) const
{
    bool ret = ((0 <= i) && (i < m_length));

    if(ret)
    {
        e = m_marry(m_length);
    }

    return ret;
}

3. 顺序存储结构的元素插入操作
   判断目标位置是否合法
   如果合法：将目标位置之后的所有元素后移一个位置
   将新元素插入目标位置
   线性表长度加1

template <typename T>
bool SeqList<T>::insert(int i, const T& e)
{
    bool ret = ( (0 <= i ) && ( i <= m_length ) );  // 注意：i<= m_length

    ret = ret && ( (m_length + 1) <= capacity() );  // capacity()为数组的存储量

    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;
}

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

template <typename T>
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;
}

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！

实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4