线性表的抽象数据类型 - 《数据结构与算法》

在前一章的“数据结构导论”中，我们所讨论的抽象数据类型定义，包含如下三个方面的内容：

（1）对数据元素的定义；

（2）对数据元素之间关系的定义；

（3）对基于上述数据的逻辑模型的操作的抽象定义。

其实，上述（1）和（2）表示的就是数据的逻辑结构。

因此，抽象数据类型的定义主要包含数据的逻辑结构及基于该逻辑结构的操作的抽象定义，于是，后序各章节

中关于线性表、树、图等各种结构的抽象数据类型的定义都是对其逻辑结构的定义及相关操作的抽象定义。

本知识点教学目标：

（1）掌握线性表的逻辑结构；

（2）在线性表的逻辑结构基础上，理解线性表基本操作的逻辑意义。

（1）线性表数据元素的定义

线性表的数据元素LD：由n（n≥0）个类型相同的数据元素 a1,a2,…,ai-1,ai,…,an-1, an 构成

的有限数据元素的集合，记作:LD＝{a1, a2, …, ai-1, ai,…, an-1,an}。

（2）线性表数据元素之间关系的定义

数据元素之间是一种一对一的有序关系，记作：LR={,…,,…,,}。

① InitList (L)：初始化线性表L，即构造一个空的线性表L。

② DestroyList (L)：线性表L已存在，将表L销毁。

③ ClearList (L)：线性表L已存在，将表L置为空表。

④ ListEmpty (L)：线性表L已存在，如果表L为空则返回TRUE，否则返回FALSE。

⑤ ListLength (L)：线性表L已存在，返回表L的长度，即表中数据元素的个数。

⑥ GetElem (L, i)：线性表L已存在，返回表L中第i（1≤i≤ListLength (L)）个元素的值。

⑦ Locate (L, e)：线性表L已存在，返回表L中元素e所在位置；如果表L中不存在元素e，则返回0。

⑧ InsertList (L, i, e)：线性表L已存在，在表L中第i（1≤i≤ListLength (L)）个位置之前插入新的数据元素e，

表L的长度加1。（增加）

⑨ DeleteList (L, i, e)：线性表L已存在且非空，删除表L中的第i个数据元素，并用e返回其值，表的长度减1。
（删除）

⑩ PriorElem (L, e)：线性表L已存在，若e是表L的数据元素且不是第一个，则返回数据元素e的前驱元素；否

则操作失败。

⑪ NextElem (L, e)：线性表L已存在，若e是表L的数据元素且不是最后一个，则返回数据元素e的后继元素；

否则操作失败。