一、线性表的抽象数据类型

1）基本术语

线性表：有结点集N和定义在结点集N上的线性关系r所组成的线性结构，零个或多个元素组成的有穷序列 n₀, n₁, n₂,….n_k-1。线性关系也称前驱关系。
    前驱：对线性表的结点对< n_i, n_i+1>而言，结点n_i,是结点n_i+1的前驱。
    后继：对线性表的结点对< n_i, n_i+1>而言，结点n_i+1是结点n_i,的后继。
    开始结点：线性表中唯一一个没有前驱的结点。
    终止结点：线性表中唯一一个没有后继的结点。

2）线性关系的性质：具有反对称性和传递性。

3）线性结构的访问方式：

l         直接访问型：包括向量型线性表和记录类型。其特点是可以按照某种方式直接访问其元素，例如，向量可以通过元素的下标直接访问其元素，记录类型可以通过字段名访问其元素。

l         顺序访问型：包括顺序文件和限制访问点的线性表。其特点是只允许访问某些入口点。

l         目录索引型：包括带有字典型索引和散列型索引的线性表。其特点是按元素的内容建立目录型索引，并通过索引访问线性表的元素。