数据结构(03)_顺序存储结构线性表-创新互联
基于前面实现的数据结构类模板基础,继续完成基于顺序存储结构的线性表的实现,继承关系图如下:
1.线性表简介
1.1.线性表的表现形式
- 零个多多个数据元素组成的集合
- 数据元素在位置上是有序排列的
- 数据元素的个数是有限的
- 数据元素的类型必须相同
1.2.线性表的抽象定义、性质
线性表是具有相同类型的n(>=)个数据元素的有限序列,(a0, a1, a2... an-1),其中ai是表项,n是表长度。
性质: - a0为线性表的第一个元素,只有一个后继
- an-1为线性表的最后一个元素,只有一个前驱
- 其他数据项既有后继,也有前驱
- 支持逐项和顺序存储
1.3.线性表的抽象实现
- 插入、删除数据元素
- 获取、设置目标位置元素的值
- 获取线性表的长度
- 清空线性表
template
class List:public Object
{
protected:
List(const List&);
List& operator ==(const List&);
public:
List(){}
virtual bool insert(const T& e) = 0;
virtual bool insert(int i,const T& e) = 0;
virtual bool remove(int i) = 0;
virtual bool set(int i,const T& e) = 0;
virtual bool get(int i,T& e) const = 0;
virtual int length() const = 0;
virtual void clear() = 0;
};
1.4.总结:
线性表是数据元素的有序并且有限的集合,其中的数据元素类型相同,在程序中表现为一个特殊的数据结构,可以使用C++中的抽象类来表示,用来描述排队关系的问题。
2.线性表的顺序存储结构
2.1.概念和设计思路
定义:
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表中的数据元素。
设计思路:
使用一维数组来实现存储结构:
// 存储空间:T* m_array; 当前长度:int m_length;
template
class SeqList : public List
{
protected:
T* m_array;
int m_length;
};
3.SeqList的设计要点
- 抽象类模板,存储空间的大小和位置由子类完成;
- 实现顺序存储结构线性表的关键操作(增、删、查、等);
- 提供数组操作符重载,方面快速获取元素;
3.1SeqList实现
template
class SeqList : public List
{
protected:
T* m_array; // 顺序存储空间
int m_length; // 当前线性长度
public:
bool insert(int index, const T& e)
{
bool ret = ( (index>=0) && (index<=m_length) ); // <= 因为可以插入的点,必然比当前元素多1
if(ret && ( m_length < capacity() )) // 当前至少有一个空间可插入
{
for(int p=m_length-1; p>=index; p--)
{
m_array[p + 1] = m_array[p];
}
m_array[index] = e;
m_length++;
}
return ret;
}
bool insert(const T& e)
{
return insert(m_length, e);
}
bool remove(int index)
{
bool ret = ( (index>=0) && (index=0) && (index=0) && (index=0) && (index&>(*this)[index]; // 去除const属性,然后调用非const版本实现
}
// 顺序存储表的的容量
virtual int capacity() const = 0;
};
4.StaticList和DynamicList
4.1.StaticList的设计要点:
类模板
- 使用原生数组做为顺序存储空间
- 使用模板参数决定数组的大小
template < typename T, int N > class StaticList : public SeqList
{ protected: T m_space[]; // 顺序存储空间,N为模板参数 public: StaticList(); // 指定父类成员的具体值 int capacity() const; }; 4.2. StaticList实现
template < typename T, int N >
class StaticList : public SeqList
{
protected:
T m_space[N]; // 顺序存储空间,N为模板参数
public:
StaticList() // 指定父类成员的具体值
{
this->m_array = m_space;
this->m_length = 0;
}
int capacity() const
{
return N;
}
};
4.3.DynamicList的设计要点:
类模板
- 申请连续堆空间做为顺序存储空间
- 保证重置顺序存储空间的异常安全性
函数异常安全的概念: - 不允许任何内存泄露,不允许破坏数据
- 函数异常安全的基本保证:
- 如果有异常抛出,对象内的任何成员任然能保持有效状态,没有数据破话或者资源泄露。
template < typename T> class DynamicList : public SeqList
{ protected: int capacity; // 顺序存储空间的大小 public: DynamicList(int capacity); // 申请空间 int capacity(void) const // 返回capacity的值 // 重置存储空间的大小 void reset(int capacity); ~DynamicList(); // 归还空间 }; 4.4. DynamicList实现
template
class DynamicList : public SeqList
{
protected:
int m_capacity;
public:
DynamicList(int capacity)
{
this->m_array = new T[capacity];
if(this->m_array != NULL)
{
this->m_length = 0;
this->m_capacity = capacity;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ...");
}
}
int capacity()const
{
return m_capacity;
}
void resize(int capacity)
{
if(capacity != m_capacity)
{
T* array = new T[capacity];
if(array != NULL)
{
int length = (this->m_length < capacity ? this->m_length : capacity);
for(int i=0;im_array[i];
}
T* temp = this->m_array;
this->m_array = array;
this->m_length = length;
this->m_capacity = capacity;
delete[] temp;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException,"No memory to create DynamicList object ...");
}
}
}
~DynamicList()
{
delete[] this->m_array;
}
};
5.顺序存储结构线性表分析
5.1.时间复杂度
顺序存储结构线性表的效率为O(n),主要受其插入和删除操作的影响(譬如插入操作时,要插入位置之后的数据要向后挪动) 。
5.2.问题
两个长度相同的顺序存储结构线性表,插入、删除操作的耗时是否相同?
- 不相同,对顺序存储结构线性表,其插入、删除操作的复杂度还取决于存储的数据类型,譬如一个普通类型和一个字符串类型/类类型就完全不同(对于复杂数据类型,元素之间移动时必然耗时很多)。从这个角度考虑,线性表的效率存在隐患。
花费多少5.3.禁用拷贝构造和赋值操作。
拷贝构造和赋值操作会导致两个指针指向同一个地址,导致内存重复释放。对于容器类型的类,可以考虑禁用拷贝构造和赋值操作。
原因: 1、对于生活中容器类的东西,我们无法对其进行赋值(譬如生活中我们不可能将杯子中的水进行复制,只能使用另一个杯子重新去获取等量的水)。
实现:将拷贝构造和赋值操作函数定义为proteced成员,在类的外部,不能使用。protected: List(const List&){} List& operator = (const List&){}
5.4.注意事项
线性表不能直接当做数组来使用
顺序存储结构线性表提供了数组操作符的重载,可以直接像数组一样,同过下标直接获取目标位置的元素,在具体的使用上类似数组,但是本质上不同,不能代替数组使用: - 必须先进行插入操作,才能对其内部的数据进行操作。
- 原生数组是自带空间的,可以直接操作。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站栏目:数据结构(03)_顺序存储结构线性表-创新互联
当前URL:http://scyanting.com/article/dsicsp.html