2.1 线性表的基本概念

2.1.1 线性表的定义

线性表是由n（n≥0）个相同类型数据元素组成的有限序列。当n=0时为空表，记为（）或Φ；当n＞0时，线性表的逻辑表示为（al，a2，…，ai，…，an），也可以用如图2.1所示的逻辑结构图表示。

在线性表逻辑表示中，al称为开始元素，an称为终端元素（或尾元素）。元素ai在线性表中的逻辑序号或位置为i。对于任意一对相邻元素<ai，ai+1> （1≤i≤n），ai称为ai+1的前驱元素（或结点），ai+1称为ai的后继元素。

线性表的逻辑特征是：若至少含有一个元素，则只有唯一的开始元素和终端元素，除了开始元素外其他元素有且仅有一个前驱元素；除了终端结点外其他元素有且仅有一个后继元素。

线性表中的每个元素有唯一的序号，同一个线性表中可以存在值相同的多个元素，但它们的序号是不同的。

例如，马路上排列成一排的行驶的汽车就是一个汽车线性表，如图2.2所示。

在不同的实际问题中，线性表中数据元素的类型可以不同，但要求同一个线性表中的所有数据元素具有相同的类型（比如数据项的个数相同，对应数据项的类型相同等）。

2.1.2 线性表的基本运算

通常线性表List的基本运算如下。

（1）初始化InitList（L）。其作用是建立一个空表L（即建立线性表的某种存储结果，但不含任何数据元素）。

（2）销毁线性表DestroyList（L）。其作用是释放线性表L的内存空间。

（3）求线性表的长度GetLength（L）。其作用是返回线性表L的长度。

（4）求线性表中第i个元素GetElem（L，i，e）。其作用是返回线性表L的第i个数据元素。

（5）按值查找Locate（L，x）。若L中存在一个或多个值与x相等的元素，则其作用是返回第一个值为x的元素的逻辑序号。

（6）插入元素InsElem（L，x，i）。其作用是在线性表L的第i个位置上增加一个以x为值的新元素，使L由（a1，…，ai—1，ai，…，an）变为（a1，…，ai—1，x，ai，…，an）。其中，参数i的合法取值范围是1≤i≤n+1。

（7）删除元素DelElem（L，i）。其作用是删除线性表L的第i个元素ai，使L由（a1，…，ai—1，ai，ai+1，…，an）变为（a1，…，ai—1，ai+1，…，an）。其中，参数i的合法取值范围是1≤i≤n。

（8）输出元素值DispList（L）。其作用是按前后次序输出线性表L的所有元素值。

包含基本运算的线性表如图2.3所示，其中，op1～ op8表示上述8个基本运算。

说明：线性表抽象数据类型由线性表中元素的逻辑结构和基本运算定义构成，为了突出后者，这里将两者分小节讨论，本书后面介绍各种数据结构时均采用这种表述方式。

使用以上基本运算可以实现线性表的更复杂的其他运算，如求任一给定数据元素的后继或前驱元素，将两个线性表合并成一个线性表或将一个线性表拆分成两个线性表等。另一方面，在实际应用中，可以根据具体需要选择适当的基本运算。

【例2.1】利用线性表List的基本运算，设计一个在线性表A中删除线性表B中出现的元素的算法。

解：本题的算法思路是：依次检查线性表B中的每个元素x，看它是否在线性表A中。若x在线性表A中，则将其从A中删除。本题的算法如下。

【例2.2】利用线性表List的基本运算，设计一个由线性表A和B中的公共元素产生线性表C的算法。

解：本题的算法思路是：先初始化线性表C，然后依次检查线性表A中的每个元素x，看它是否在线性表B中；若x在线性表B中，则将其插入到线性表C中。本题的算法如下。

从以上示例看到，一旦线性表及其基本运算算法实现好后，利用线性表求解实际问题就变得十分方便快捷。