python线性表顺序存储实现_数据结构（三）——基于顺序存
储结构的线性表
数据结构(三)——基于顺序存储结构的线性表
⼀、基于顺序存储结构的线性表实现
1、顺序存储的定义
线性表的顺序存储结构是⽤⼀段地址连续的存储单元依次存储线性表中的数据元素。
2、顺序存储结构的操作
使⽤⼀维数组实现顺序存储结构。
template
class SeqList:public List
{
protected:
T* m_array;//顺序存储空间
int m_length;//当前线性表的长度
};
⼀维顺序存储结构可以是原⽣数组或是动态分配的空间。因此，根据空间分配的不同，分为静态线性表和动态线性表。
(1)元素的获取
顺序存储结构的元素获取操作：
A、判断⽬标位置是否合法
B、将⽬标位置作为数组下标获取元素
bool get(int index, T& value)
{
//判断⽬标位置是否合法
bool ret = (0 <= index) && (index < m_length);
if(ret)
{
//将⽬标位置作为下标获取元素
value = m_array[index];
}
return ret;
}
(2)元素的插⼊操作
顺序存储结构的元素插⼊操作：
A、判断⽬标位置是否合法
B、将⽬标位置后的所有元素向后移⼀位
C、将新元素插⼊⽬标位置
D、线性表长度增加1
bool insert(int index, const T& value)
{
//判断⽬标位置是否合法
bool ret = (0 <= index) && (index <= m_length); ret = ret && ((m_length + 1) <= capacity());
if(ret)
{
//将⽬标位置后的所有元素后移⼀个位置
for(int i = m_length -1; index <= i; i--)
{
m_array[i+1] = m_array[i];
}
//将新元素插⼊到⽬标位置
python获取数组长度
m_array[index] = value;
//线性表长度加1
m_length++;
}
return ret;
}
(3)元素的删除操作
顺序存储结构的元素删除操作：
A、判断⽬标位置是否合法
B、将⽬标位置后的所有元素前移⼀个位置
C、线性表长度减1
bool remove(int index)
{
//判断⽬标位置是否合法
bool ret = (0 <= index) && (index < m_length); if(ret)
{
//将⽬标位置后的所有元素前移⼀位
for(int i = index; i < m_length-1; i++)
{
m_array[i] = m_array[i+1];
}
//将线性表长度减1
m_length--;
}
return ret;
}
(4)元素值的修改
顺序存储结构中元素值的修改：
A、判断⽬标位置是否合法
B、修改⽬标位置元素的值
bool set(int index, const T& value)
{
//判断⽬标位置是否合法
bool ret = (0 <= index) && (index < m_length); if(ret)
{
//修改⽬标位置元素的值
m_array[index] = value;
}
return ret;
}
(5)线性表长度的获取
顺序存储结构线性表的长度获取
int length()const
{
//线性表长度
return m_length;
}
(6)线性表的清空
void clear()
//清空线性表
m_length = 0;
}
(7)[]操作符重载
//[]操作符重载
T& operator[](int index)
{
//判断⽬标位置是否合法
if((0 <= index) && (index < m_length))
{
//返回下标相应的元素
return m_array[index];
}
else
{
THROW_EXCEPTION(IndexOutOfBoudsException, "Paramenter index "); }
}
//const对象的[]重载
T operator[](int index)const
{
//转换为⾮const对象后使⽤[]操作
return (const_cast&>(*this))[index];
}
(8)顺序存储结构空间的⼤⼩
virtual int capacity()const = 0;
由于存储空间在⼦类分配，因此为纯虚函数。
3、顺序存储结构的抽象实现
template
class SeqList:public List
{
public:
bool insert(int index, const T& value)
//判断⽬标位置是否合法
bool ret = (0 <= index) && (index <= m_length); ret = ret && ((m_length + 1) <= capacity());
if(ret)
{
//将⽬标位置后的所有元素后移⼀个位置
for(int i = m_length -1; index <= i; i--)
{
m_array[i+1] = m_array[i];
}
//将新元素插⼊到⽬标位置
m_array[index] = value;
//线性表长度加1
m_length++;
}
return ret;
}
bool remove(int index)
{
//判断⽬标位置是否合法
bool ret = (0 <= index) && (index < m_length); if(ret)
{
//将⽬标位置后的所有元素前移⼀位
for(int i = index; i < m_length-1; i++)
{
m_array[i] = m_array[i+1];
}
//将线性表长度减1
m_length--;
}
return ret;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。