线性表

线性表，全名为线性存储结构
将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

对于非空的线性表和线性结构,其特点如下:

存在唯⼀的⼀个被称作”第⼀个”的数据元素;
存在唯⼀的一个被称作”最后⼀个"的数据元素 除了第一个之外,结构中的每个数据元素均有⼀个前驱 除了最后⼀个之外,结构中的每个数据元素都有一个后继.

注意
使用线性表存储的数据，如同向数组中存储数据那样，要求数据类型必须一致，也就是说，线性表存储的数据，要么全不都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一组数据无法使用线性表存储。

线性表存储结构可细分为:
-顺序存储结构
-链式存储结构

ADT List {

Data: 线性表的数据对象集合为{a1,a2,......an},每个元素的类型均为DataType. 其中,除了第一个元素a1外,每⼀个元素有且
只有⼀个直接前驱元素,除了最后⼀个元素an外,每个元素有且只有⼀个直接后继元素. 数据元素之间的关系是⼀对一的关系.

Operation

InitList(&L)

操作结果:初始化操作,建⽴一个空的线性表L.

DestroyList(&L)

初始条件: 线性表L已存在
操作结果: 销毁线性表L.

ClearList(&L)

初始条件: 线性表L已存在
操作结果: 将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已存在
操作结果: 返回L中第1个值与e相同的元素在L中的位置. 若数据不存在则返回0;

PriorElem(L, cur_e,&pre_e);

初始条件: 线性表L已存在
操作结果: 若cur_e是L的数据元素,且不是第⼀个,则用pre_e返回其前驱,否则操作失败.

NextElem(L, cur_e,&next_e);

初始条件: 线性表L已存在
操作结果: 若cur_e是L的数据元素,且不是最后一个,则用next_e返回其后继,否则操作失败.

ListInsert(L,i,e);

初始条件: 线性表L已存在,且1<=i<=listLength(L)
操作结果: 在L中第i个位置之前插入新的数据元素e,L长度加1.

ListDelete(L,i);

初始条件: 线性表L已存在,且1<=i<=listLength(L) 操作结果: 删除L的第i个元素,L的长度减1.

TraverseList(L);

初始条件: 线性表L已存在
操作结果: 对线性表L进行行遍历,在遍历的过程中对L的每个结点访问1次.

}ADT List.

单链表：

单链表的逻辑状态 增加头结点的单链表逻辑状态

增加头结点的好处：
1、便于首元节点的操作；
2、便于非空链表和链表的操作统一；

空链表 非空链表