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

• 线性表（List）：由零个或多个数据元素组成的有限序列

• 首先线性表是一个序列，元素之间有先来后到，没有顺序就不是线性表

• 若元素存在多个，则第一个元素无前驱，而最后一个元素无后继，其他元素都有且只有一个前驱和后继

• 线性表的强调是有限的，无论计算机发展到多强大，所处理的元素都是有限的

• {a1,ai-1,ai,ai+1}：表中 ai-1 领先于 ai ，ai 领先于 ai+1 ，ai-1 是 ai 的直接前驱元素， ai+1 是 ai 的直接后继元素

• 线性表元素的个数 n （n>=0）定义为线性表的长度，当 n = 0 时，称为空表

• 数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称

• C语言中，按照取值的不同，数据类型可以分为两类：

  • 原子类型：不可以再分解的基本类型，例如整型、浮点型、字符型等

  • 结构类型：由若干个类型组合而成，是可以在分解的，例如整型数组是由若干整型数据组成

• 抽象：是指抽取出事物具有的普遍性本质，要求抽出问题的特征而忽略非本质的细节，是对具体事务一个概况，抽象是一种思考问题的方式，隐藏了繁杂的细节

• 抽象数据类型（Abstract Data Type， 简称ADT）是指一个数学模型及定义在改模型上的一组操作

• 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关

• 抽象的意义在于数据类型的数学抽象特性

• 抽象数据类型不仅仅指已经定义并实现的数据类型，还可以是计算机编程者在设计软件程序时自己定义的类型数据

• 抽象数据类型的标准格式：

ADT 抽象数据类型名

Data

数据元素之间逻辑关系的定义

Operation

操作

endADT

• ADT 线性表（list）

• Data

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

• Operation

  • InitList(*L)：初始化操作，建立一个空的线性表 L

  • ListEmpty(L)：判断线性表是否为空表，若线性表为空，返回true，否则返回false

  • ClearList(*L)：将线性表清空

  • GetElem(L,i,*e)：将线性表 L 中的第 i 个位置元素值返回给 e

  • LocateElem(L,e)：在线性表 L 中查找与给定值 e 相等的元素，如果查找成功，返回该元素在表中序号表示成功，否则返回 0 表示失败

  • ListInsert(*L,i,e)：在线性表 L 中第 i 个位置插入新元素 e

  • ListDelete(*L,i,*e)：删除线性表 L 中第 i 个位置元素，并用 e 返回其值

  • ListLength(L)：返回线性表 L 的元素个数

• endADT

• 对于不同的应用，线性表的基础操作是不同的，上述操作是最基本的，对于实际问题中涉及关于线性表的更复杂的操作，可以用这些基本操作的组合来实现