一、数据结构_线性表的本质和操作

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++中表现为一个抽象类

一、数据结构_线性表的本质和操作

1、线性表

2、线性表的性质

3、线性表的程序实现

4、小结

推荐阅读更多精彩内容