2.2　线性表的概念与基本操作

2.2.1　线性表的概念

线性表（Linear_List）是一种基础且重要的线性结构，在现实世界中有许多线性结构。例如，向量( x ₁ , x ₂ ,…, x _n )是一个长度为 n 的线性表；英文小写字母表(a,b,c,…,z)是一个长度为26的线性表；一年中的四个季节(春,夏,秋,冬)是一个长度为4的线性表；矩阵（或二维表）是一个比较复杂的线性表。

线性表是由 n （ n ≥0）个数据元素 a ₁ , a ₂ ,… , a _n 组成的一个有限序列， n 为元素总个数，即表长， n =0时称为空表。即线性表或是一个空表L = ( )，或可以表示为L = ( a ₁ , a ₂ ,…, a _{i −1} , a _i , a _{i +1} ,…, a _n )，其中 a _i （ i =1,2,…, n ）是属于数据对象的元素，通常也称其为线性表中的一个节点； i 为数据元素 a _i 在线性表中的位序。

线性表中的每一个数据元素，除了第一个数据元素外，有且仅有一个直接前驱，除了最后一个数据元素外，有且仅有一个直接后继。因此，线性表元素之间是一对一的关系。

2.2.2　线性表的基本操作

线性表的基本操作包括初始化、插入元素、删除元素、访问元素等操作，是线性表应用实例的基础操作，并且可以进一步进行扩展。以下是线性表的抽象数据类型及线性表的基本操作。 t3yWYxd5dEdOk6lZQBbjI6E4idNxRaIg4lk5KDTTkTD6elQK5JC3toHBql3m4/ZQ

ADT List{
数据对象：D={ai|ai    ElemSet，i=1，2，...，n，n>=0}
数据关系：R={<ai-1，ai>|ai-1 ,ai    D，i=2，...，n}
基本操作如下。
（1）InitList(&L)：初始化线性表，构造一个空表L，长度为0。
（2）DestroyList(&L)：销毁线性表L。
（3）ClearList(&L)：置空表，即将线性表L还原为最初的空表。
（4）ListEmpty(L)：判断线性表L是否空表，若为空表返回值为True，否则为False。
（5）ListLength(L)：求线性表L的表长。
（6）GetElement(L, i, &e)：获取线性表L中的某个表元素，通过形参e返回。
（7）LocateElement(L, e)：查找线性表L中的某个元素e是否存在，若存在则返回该元素在线性表中的位序，否则返回0。
（8）ModifyElement(L, e, t)：将线性表L中的某个元素e修改为元素t，若修改成功则返回1。
（9）PriorElement(L, cur_e, &pre_e)：求线性表L中当前元素cur_e的直接前驱元素pre_e，并返回。
（10）NextElement(L, cur_e, &next_e)：求线性表L中当前元素cur_e的直接后继元素next_e，并返回。
（11）ListInsert(&L, i, e)：在线性表L的指定位置i插入一个新元素e。
（12）ListDelete(&L, i, &e)：在线性表L的指定位置i删除元素e，并返回。
（13）ListTraverse(L)：访问线性表L。
}ADT List