2.1　线性表定义

线性表是零个或多个数据元素构成的线性序列，记为(a0,a1,…,an−1)。线性表中的数据元素个数n称为线性表的长度。当n=0时，此线性表为空表。

线性表(a0,…,ai−1,ai,ai+1,…,an−1)中，ai表示下标为i的元素，ai−1是ai的直接前驱元素，ai+1是ai的直接后继元素。线性表除第一个数据元素a0没有直接前驱元素，最后一个数据元素an−1没有直接后继元素之外，其他数据元素都有唯一一个直接前驱元素和直接后继元素。在不会引起混淆的情况下，我们简称直接前驱元素为“前驱”，直接后继元素为“后继”。线性表中数据元素之间存在着一对一关系，因此，线性表的逻辑结构为线性结构。

线性表是一种非常灵活的数据结构，可在线性表的任意位置执行插入、删除元素的运算，也可执行搜索、修改等运算。本章采用第1章给出的抽象数据类型格式对线性表进行描述，其中包括线性表最常见的运算，如ADT 2.1所示。

以上描述由抽象数据类型定义的线性表，暂不涉及具体的实现，因此所描述的参数和数据元素暂不必给出具体数据类型，可根据实际使用进行具体的表示和实现。

线性表有两种典型的存储结构：顺序存储结构和链式存储结构，以下分别介绍。