| |
| 线性表（linear_list）是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。一个数据元素可以由若干个数据项（item）组成，通常称为记录（record）,含有大量记录的线性表又被称为文件（file）。设序列中第i个元素为ai（1≤i≤n），则线性表一般表示为：
|
|
|
| （a1,a2,…,ai-1, a?, ai+1，…，an）
|
|
|
| 其中，ai-1在均ai的前面，称为ai的直接前驱元素。ai+1在ai的后面称为ai的直接后继元素。线性表中元素的个数n（n≥0）称为线性表的长度。当n=0时，线性表成为空表。
|
|
|
| 一个线性表也可以用标志符来命名，例如用A命名上面的线性表，则：
|
|
|
| A=（a1, a2,…,ai-1,ai, ai+1,…, an）
|
|
|
|
|
|
|
|
|
| 数据对象A=｛ai| 1≤i≤n,n≥0，ai为数据元素｝
|
|
|
| 数据关系R=｛i, ai+1>| 1≤i≤n-1｝
|
|
|
|
|
|
|
|
|
| 线性表是一个非常灵活的数据结构，对线性表的数据元素不仅可以访问，还可以对其进行诸如插入、删除等操作。因此，线性表的抽象数据类型包括了数据对象和数据关系两大部分，抽象数据类型的线性表定义如下所示：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
