2.2 线性表的抽象数据类型

把"一行字符"推广一下：不限于字符，任何n个同类型元素排成一个序列，相邻元素之间是一对一的前后关系，这样的结构叫线性表，记作 (a₀, a₁, …, aₙ₋₁)。n叫线性表的长度，n=0时是空表。a₀前面没有元素，aₙ₋₁后面没有元素，其余每个元素都恰好有一个前驱和一个后继。本书约定位置从0开始编号，与C语言数组一致。

线性表上最基础的操作有六个：

操作	含义	前提
Init(L)	建立一个空表
Length(L)	返回表的长度n
Get(L, i)	返回第i个元素	0 ≤ i < n
Insert(L, i, x)	在第i个位置插入x，原来第i个及之后的元素依次后移	0 ≤ i ≤ n
Delete(L, i)	删除第i个元素，之后的元素依次前移	0 ≤ i < n
Locate(L, x)	返回x第一次出现的位置，不存在返回−1

注意Insert允许i=n，表示在末尾追加；Delete不允许。表满不满、位置越界怎么办，是实现层面的事，这里只规定合法的前提。

这六个操作加上线性关系，就是线性表的抽象数据类型。它没有提到光标，也没有提到字符——线性表是通用的，编辑器只是它的一个应用。编辑器可以看成"一个元素类型为字符的线性表，外加一个整数记录光标位置"：敲字符是Insert(L, cursor, c)然后cursor加一；退格是Delete(L, cursor−1)然后cursor减一；左右方向键只改cursor；显示就是从0到Length(L)−1逐个Get。

到这里，编辑器的问题已经完全转化为线性表的问题。剩下的事是把线性表在计算机里实现出来。第1章介绍了两种存储手段，我们先用顺序存储。