线性表的类型定义

线性结构是一个数据元素的有序（次序）集合。
“有序” 仅指在数据元素之间存在一个 “领先” 或“落后” 的次序关系，而非指数据元素 “值” 的大小可比性。

线性结构的基本特征

在数据元素的非空有限集中:
1. 存在唯一的一个“第一个”数据元素；
2. 存在唯一的一个“最后一个”数据元素；
3. 除第一个之外，每个数据元素均只有“唯一的前驱”；
4. 除最后一个之外，每个数据元素均只有“唯一的后继”。

记为(a1,…,ai-1,ai,…an)

抽象数据类型定义

ADT List{
    数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}
    数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3,4,...,n}
    基本操作：
    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已存在，l≤i≤ListLength(L)。
        操作结果：用e返回L中第i个数据元素的值。
    LocateElem(L,e,compare())
        初始条件：线性表L已存在，compare()是数据元素的判定函数。
        操作结果：用e返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。
    PriorElem(L,cur_e,&pre_e)
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
    NextElem(L,cur_e,&next_e)
        初始条件：线性表L已存在。
        操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的前驱，否则操作失败，next_e无定义。
    ListInsert(&L,i,e)
        初始条件：线性表L已存在，l≤i≤ListLength(L)+1。
        操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1.
    ListDelete(&L,i,&e)
        初始条件；线性表L已存在且非空，l≤i≤ListLength(L)。
        操作结果：删除L中第i个数据元素，并用e返回其值，L长度减1.
    ListTraverse(L,visit())
        初始条件：线性表L已存在。
        操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT List