欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-25 15:50:18
1、顺序存储的定义 定义:线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表中的数据元素 | $a_1$ | ...... | $a_{i 1}$ | $a_i$ | ...... | $a_{n 1}$ | 2、相关操作 程序设计思路: 可以用一维数组来实现顺序存储结构 存储空间: ......

1、顺序存储的定义

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

| \(a_1\) | ...... | \(a_{i-1}\) | \(a_i\) | ...... | \(a_{n-1}\) |

2、相关操作

程序设计思路:

可以用一维数组来实现顺序存储结构

  • 存储空间: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
bool SeqList<T>::insert(int i, const T& e)
{
    bool ret = ((0 <= i) && (i <= m_length));
    ret = ret && ((m_length + 1) <= 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++;
    }
}

顺序存储结构的元素删除操作:

  • 判断目标位置是否合法
  • 将目标位置后的所有元素前移一个位置
  • 线性表长度减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;
}