03.03 线性表的抽象数据类型

以下均从计算机的视角理解

抽象是指抽取出事物具有的普遍性的本质。比如说动物都会发出叫声，可以抽出一个 shut 的方法来给每个动物写入不同的程序。

抽象数据类型（ADT）：具有类似行为的特定类别的数据结构的数学模型。它体现了程序设计中问题分解、抽象和信息隐藏的特性。比如说

ADT 抽象数据类型名
DATA
    数据元素之间逻辑关系的定义

Operation
    操作1
        初始条件
        操作结果描述
    操作2
        ...
endADT

对应到线性表，行为指的是增删改查，特定类别指的是链表或者数组实现，也就是说，数据结构指的是它们怎么形成的一个整体。

ADT 线性表（List）
DATA
    数据元素之间逻辑关系的定义

Operation
    #*号指的是指针。具体来说，*L 存储的是这个线性表的内存地址。
    InitList（*L）： 初始化操作，建立一个空的线性表L。
    ListEmpty（L）： 若线性表为空，返回true，否则返回false。
    ClearList（*L）： 将线性表清空。
    GetElm（L，i，*e）：将线性表L中的第i个位置元素返回给e。
    LocateElem（L，e）：查找与e相等的元素
    ListInsert（*L，i，e）：插入新元素e
    ListDelete（*L，i，*e）：删除第i个元素
    ListLength（L）：返回元素个数
endADT