2.1 线性表的类型定义

线性表是最简单和最常用的一种数据结构。线性表的例子不胜枚举，例如，英文字母表（A,B,…,Z）是一个线性表，表中的每一个英文字母都是一个数据元素；又如成绩单是一个线性表，表中的每一行是一个数据元素，每个数据元素又是由学号、姓名、成绩等数据项组成的。线性结构的特点是：在数据元素的非空有限集合中，存在唯一的首元素和唯一的尾元素，首元素无直接前驱，尾元素无直接后继，集合中其他每个数据元素均有唯一的直接前驱和唯一的直接后继。本章首先介绍线性表的抽象数据类型定义，给出实现线性表的两种存储结构——顺序存储结构和链式存储结构，进一步给出在相应存储结构上实现的线性表运算。本章讨论线性表的定义、线性表的顺序存储结构和链式存储结构。

本章主要内容

&        线性表的逻辑结构特性

&        线性表的顺序存储结构和链式存储结构

&        顺序表上各种基本运算算法

&        链表上各种基本运算算法

2.1  线性表的类型定义

线性表是由n（n≥0）个节点组成的有限序列。为了便于讨论，有时将含n（n≥0）个节点的线性表表示为(a₁, a₂,…, a_i,…, a_n)，其中a₁称为起始节点，a_n称为终端节点。i是a_i在线性表中的序号或位置。对于任意一对相邻节点<a_i, a_i+1>（1≤i≤n），a_i称为a_i+1的前驱节点，a_i+1称为a_i的后继节点。为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何节点的情况，不含任何节点的线性表记为“()”或“Φ”。

线性结构的基本特征是：若至少含有一个节点，则除起始节点没有前驱节点外，其他节点有且仅有一个前驱节点；除终端节点没有后继节点外，其他节点有且仅有一个后继节点。在线性表中，每个节点至多只有一个前驱节点并且至多只有一个后继节点。

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