2.1线性表的定义
2.1.1线性表的概念
线性表是一种线性结构。简言之，一个线性表是由n个数据元素构成的有限序列。线性表中的数据元素可以是一个数或一个字符，也可以是由若干数据项组成的记录，甚至可以是更复杂的信息。也就是说，线性表中的数据元素可以是任意类型的，但必须是相同类型的。
通常将n个数据元素构成的线性表记为：(a1,a2,…,ai－1,ai,ai+1,…,an)。其中，n称为线性表的表长，当n=0时称为空表。线性表中的数据元素之间存在着顺序关系，其中ai－1是ai的前驱，ai是ai－1的后继(i=2，3，…，n)，i称为数据元素ai在线性表中的位序。
在实际应用中，线性表的例子是很多的。例如，26个字母组成的字母表：
(A,B,…,Z)
是一个线性表，其中的数据元素是单个字母。又如学生信息表，如表2.1所示。其中每个数据元素是由姓名、学号、性别、年龄、班级等数据项组成的记录。
2.1.2线性表的抽象数据类型定义
抽象数据类型是指一个数据结构及其上的一组操作。数据结构的操作是定义在逻辑结构层次上的，而操作的具体实现是建立在存储结构上的，因此线性表的基本操作作为逻辑结构的一部分定义在抽象数据类型中，每个操作的具体实现只有在确定了线性表的存储结构之后才能完成。线性表的长度可以根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。
线性表的抽象数据类型定义如下：
ADT List{
数据对象:D={ai|ai∈ElemSet,i=1,2, …,n,n≥0}
数据关系:R1={|ai-1,ai∈D,i=2,…,n}
基本操作:
InitList(&L)
初始条件:线性表L不存在。
操作结果:构造一个空的线性表L。
CreateList(&L)
初始条件:线性表L为空表。
操作结果:建立一个含有n个元素的线性表L。
ListEmpty(L)
初始条件:线性表L已存在。
操作结果:若L为空表,则返回TRUE,否则返回FALSE。
ListLength(L)
初始条件:线性表L已存在。
操作结果:返回L中元素的个数。
GetElem(L,i,&e)
初始条件:线性表L已存在,且1≤i≤ListLength(L)。
操作结果:用e返回L中第i个元素的值。
LocateElem(L,e)
初始条件:线性表L已存在,e为给定值。
操作结果:返回L中指向元素值为e的第1个结点的指针。若这样的元素不存在,则返回空指针。
DispList(L)
初始条件:线性表L已存在。
操作结果:依次输出L中的每个元素。
DestroyList(&L)
初始条件:线性表L已存在。
操作结果:销毁线性表L。
ListInsert(&L,i,e)
初始条件:线性表L已存在,且1≤i≤LengthList(L)+1。
操作结果:在L的第i个元素之前插入新的元素e,L的长度增1。
ListDelete(&L,i,&e)
初始条件:线性表L已存在且非空,1≤i≤LengthList(L)。
操作结果:删除L的第i个元素,并用e返回其值,L的长度减1。
}ADT List
需要指出的是，以上线性表的抽象数据类型定义中的操作不是它的全部，只是一些常用的基本操作。可以利用上述基本操作实现其他更复杂的操作。这些基本操作要在确定了存储结构之后才能实现。
为了讨论方便，如无特别说明，本章假定ElemType为int类型，使用如下自定义类型语句定义：
typedef int ElemType;