线性表的定义:

线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。

线性表的长度：线性表中数据元素的个数。

空表：长度等于零的线性表，记为：L=(  )。

非空表记为：L＝（a1,a2 ,…, ai-1, ai,…, an)

其中，ai（1≤i≤n）称为数据元素；

下角标 i表示该元素在线性表中的位置或序号 。

线性表的图形表示:

线性表（a1,a2, …, ai-1,ai , …,an)的图形表示如下：

a i可以是简单数据类型，也可以是复杂数据类型，如结构体等，在今后的讨论中如不特别声明，常用简单数据类型来表示数据元素。

线性表的特性:

      1.有限性：线性表中数据元素的个数是有穷的。

2.相同性：线性表中数据元素的类型是同一的。

3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系<ai-1, ai>，即ai-1是ai的前驱， ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。

ADT List{

     数据对象：D={ ai | ai∈ElemSet,i=1,2,3,…,n,n≥0}

     数据关系：R={<ai-1, ai> | ai-1, ai∈D , i=1,2,3,…,n }

基本操作集：

(1) Init_List(L)：构造并初始化一个空的线性表。

(2) Length_List(L) ：返回线性表中的所含元素的个数。

(3) Get_List(L,i)：返回线性表L中的第ｉ个元素的值或地址，1≤i≤Length_List(L)。

(4) Locate_List(L,x)：在表 L中查找值为ｘ的数据元素，其结果返回在 L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功;否则，在 L中未找到值为ｘ的数据元素，返回一特殊值（如-1）表示查找失败。

(5)Insert_List(L,i,x)：在线性表 L的第i 个位置上插入一个值为x 的新元素，这样使原序号为i , i+1, ... , n 的数据元素的序号变为i+1,i+2, ... , n+1，插入后新表长=原表长+1，1≤i≤n+1,ｎ为插入前的表长。

 (6)Delete_List(L,i)：在线性表 L中删除序号为i 的数据元素，删除后使序号为i+1,i+2,..., n的元素变为序号为i,i+1,...,n-1，新表长=原表长-１，1≤i≤n。

}ADTList