第2章 线性表
2.1 线性表的类型定义
线性结构的特点是：在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素只有一个前驱；（4）除最后一个外，集合中每个数据元素均只有一个后继。
线性表的类型定义
线性表（linear_list）是最常用的且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。在稍复杂的线性表中，一个数据元素可以由若干个数据项（item）组成。在这种情况下，常把数据数据元素成为记录（record）,含有大量记录的线性表成为文件（file）。
线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定是具有相同特性，即属同一数据对象，相邻元素之间存在着序偶关系。
若将线性表记为
(a1,···,ai-1,ai,ai+1,···,an)
则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，···，n-1是时，ai有且仅有一个直接后继，当i=2,3，···，n时，ai有且仅有一个直接直接前驱。
线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。
线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问还可以进行插入和删除等。
线性表的基本操作：
1、InitList(&L)
操作结果：构造一个空的线性表L。
2、DestroyList(&L)
初始条件：线性表L已存在
操作结果：销毁线性表L
3、ClearList(&L)
初始条件：线性表L已存在
操作结果：将线性表L重置为空表
4、ListEmpty(&L)
初始条件：线性表L已存在
操作结果：判断线性表是否为空表，若线性表L为空表则返回TRUE，否则返回FALSE
5、ListLength(L)
初始条件：线性表L已存在
操作结果：返回线性表中数据元素的个数，即求表长
6、GetElem(L,i,&e)
初始条件：线性表L已存在，1<=i<=ListLength(L)
操作结果：用e返回线性表L中第i个数据元素的值
7、LocateElem(L,e,compare())
初始条件：线性表L已存在，compare()是数据元素判定函数
操作结果：返回星星变L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0
8、PriorElem(L,cur_e,&pre_e)
初始条件：线性表L已存在
操作结果：若cur_e是线性表L的数据元素，且不是第1个，则用pre_e返回它的前驱，否则造作失败，pre_e无定义
9、NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在
操作结果：若cur_e是线性表L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
10、ListInsert(&L,i,e)
初始条件：线性表L已存在，1<=i<=ListLength(L)+1
操作结果：在线性表L中第i个位置之前插入新的数据元素e,线性表L的长度加1
11、ListDelete(&L,i,&e)
初始条件：线性表L已存在且非空，1<=i<=ListLength(L)
操作结果：删除线性表L中的第i个数据元素，并用e返回其值，线性表L的长度减1
12、ListTraverse(L,visit())
初始条件：线性表L已存在
操作结果：依次对线性表L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。