动手学数据结构与算法最新章节_俞勇著

2.2 线性表的定义

线性表的定义

线性结构是由一组数据元素构成的数据结构，这些数据元素之间存在顺序关系。在计算机中，处理线性结构的数据结构称作“线性表”，线性表就像一个可以插入或删除数据元素的队伍，能够方便、快捷、高效地管理和操作数据。图2-1中的站点信息就是一个线性表。

根据火车票管理系统的功能需求，采用面向对象设计，可以用抽象类描述对应的操作要求。线性表的抽象类的定义如代码清单2-1所示。

代码清单2-1　线性表的抽象类的定义

template <class elemType>
class list {
 public:
  virtual void clear() = 0;  // 清空线性表
  virtual int length() const = 0;  // 获取线性表的长度，即元素个数
  virtual void insert(int i, const elemType &x) = 0;
  // 在第i个位置插入一个元素x
  virtual void remove(int i) = 0;  // 删除第i个元素
  virtual int search(const elemType &x) const = 0;
  // 搜索元素x是否在线性表中出现
  virtual elemType visit(int i) const = 0;  // 访问线性表第i个元素
  virtual void traverse() const = 0;  // 遍历线性表
  virtual ~list(){};
};

线性表的抽象类是一个类模板，模板参数是线性表中数据元素的类型，在列车运行计划中就是StationInfo。线性表的每一个基本操作都被定义为一个纯虚函数。除此之外，抽象类list还定义了一个函数体为空的虚析构函数，以防内存泄漏。

如无特殊说明，本书中的示例总会先给出一个模板抽象类，采用纯虚函数声明这一数据结构的功能与调用接口，再由派生类给定数据结构的具体实现。