3.2 线性表的逻辑结构

3.2.1 线性表的定义

线性表（linearlist）简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。线性表中数据元素的个数称为线性表的长度。长度等于零的线性表称为空表。一个非空表通常记为：L=（a1，a2，…，an），其中，ai（1≤i≤n）称为数据元素，下角标i表示该元素在线性表中的位置或序号①，称元素ai位于表的第i个位置，或称ai是表中的第i个元素。a1称为第一个元素，an称为最后一个元素，任意一对相邻的数据元素 ai-1和 ai（1＜i≤n）之间存在序偶关系＜ai-1，ai＞，且ai-1称为ai的前驱，ai称为ai-1的后继。在这个序列中，元素a1无前驱，元素an无后继，其他每个元素有且仅有一个前驱和一个后继。

图3-4 线性表的逻辑结构图

线性表的数据元素具有抽象（即不确定）的数据类型，在实际问题中，数据元素的抽象类型将被具体的数据类型所取代。例如，约瑟夫环问题中n个人的编号（1，2，…，n）是一个线性表，表中数据元素的类型是整型；学籍管理问题中n个人的学籍信息（a1，a2，…，an）是一个线性表，表中数据元素的类型是相应的结构体类型。

3.2.2 线性表的抽象数据类型定义

线性表是一个相当灵活的数据结构，对线性表的数据元素不仅可以进行存取访问，还可以进行插入和删除等基本操作。其抽象数据类型定义为：

            ADTList
              Data
                  线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系
              Operation
                  InitList
                      前置条件：线性表不存在
                      输入：无
                      功能：线性表的初始化

                      输出：无
                      后置条件：一个空的线性表
                  Creat
                      前置条件：线性表不存在
                      输入：n个数据元素
                      功能：建立一个具有n个元素的线性表
                      输出：无
                      后置条件：一个具有n个元素的线性表
                  Length
                      前置条件：线性表已存在
                      输入：无
                      功能：求线性表的长度
                      输出：线性表中数据元素的个数
                      后置条件：线性表不变
                  Get
                      前置条件：线性表已存在
                      输入：元素的序号i
                      功能：按位查找，在线性表中查找序号为i的数据元素
                      输出：如果序号合法，返回序号为i的元素值，否则抛出异常
                      后置条件：线性表不变
                  Locate
                      前置条件：线性表已存在
                      输入：数据元素x
                      功能：按值查找，在线性表中查找值等于x的元素
                      输出：如果查找成功，返回元素x在表中的序号，否则返回0
                      后置条件：线性表不变
                  Insert
                      前置条件：线性表已存在
                      输入：插入位置i；待插元素x
                      功能：插入操作，在线性表的第i个位置处插入一个新元素x
                      输出：若插入不成功，抛出异常
                      后置条件：若插入成功，表中增加了一个新元素
                  Delete
                      前置条件：线性表已存在
                      输入：删除位置i
                      功能：删除操作，删除线性表中的第i个元素
                      输出：若删除成功，返回被删元素，否则抛出异常
                      后置条件：若删除成功，表中减少了一个元素
                  Empty
                      前置条件：线性表已存在
                      输入：无
                      功能：判空操作，判断线性表是否为空表
                      输出：若是空表，返回1，否则返回0
                      后置条件：线性表不变

                  PrintList
                      前置条件：线性表已存在
                      输入：无
                      功能：遍历操作，按序号依次输出线性表中的元素
                      输出：线性表的各个数据元素
                      后置条件：线性表不变
            endADT

需要强调的是：（1）对于不同的应用，线性表的基本操作不同；（2）上述操作是基本操作，对于实际问题中更复杂的操作，可以用这些基本操作的组合（即调用基本操作）来实现；（3）对于不同的应用，上述操作的接口可能不同，例如删除操作，若要求删除表中值为x的元素，则Delete操作的输入参数就不能是位置而应该是元素值。