1、线性表
线性表(List)的表现形式
- 零个或多个数据元素组成的集合
- 数据元素在位置上是有序排列的
- 数据元素的个数是有限的
- 数据元素的类型必须相同
线性表的抽象定义：
线性表是具有相同类型的(n(geq0)) 个数据元素的有限序列
[(a_0, a_1, ..., a_{n-1})
]
(a_i)是表项（数据元素）， (n)是表长度
2、线性表的性质
- (a_0)为线性表的第一个元素，只有一个后继
- (a_{n-1})为线性表的最后一个元素，只有一个前驱
- 除(a_0)和(a_{n-1})外的其它元素(a_i)，既有前驱，又有后继
- 直接支持逐项访问和顺序存取
3、线性表的程序实现
线性表的常用操作
- 将元素插入线性表
- 将元素从线性表中删除
- 获取目标位置处元素的值
- 设置目标位置处元素的值
- 获取线性表的长度
- 清空线性表
线性表在程序中的表现形式为一种特殊的数据类型
创建一个线性表抽象类模板
template<typename T>
class List : public Object
{
public:
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;
}
4、小结
线性表是数据元素的有序并且有限的集合
线性表的数据元素必须是类型相同的
线性表可用于描述排队关系的问题
线性表在程序中表现为一种特殊的数据类型
线性表在C++中表现为一个抽象类