线性表的定义及基本操作-《C语言程序设计》

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表是在实际应用中被广泛采用的一种数据结构。

用数学语言定义如下：

若将线性表记为（a1，…，ai－1，ai，ai＋1，…，an），则表中ai－1领先于ai，ai领先于ai＋1，称ai－1是ai的直接前驱元素，ai＋1是ai的直接后继元素。除a1、an外，中间元素都有一个直接前驱和一个直接后继。所有线性表元素的个数n（n≥0）定义为线性表长度，当n＝0时，称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

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

ADT List｛

数据对象：D＝｛ai|ai∈ElemSet，i＝1，2，…，n，n≥0｝

数据关系：R＝｛＜ai－1，ai＞|ai－1，ai∈D，i＝1，2，…，n｝

基本操作：

Init List（&L）

操作结果：构造一个空的线性表L。

Destroy List（&L）

初始条件：线性表L已存在。

操作结果：销毁线性表L。

Clear List（&L）

初始条件：线性表L已存在。

操作结果：将L重置为空表。

ListEmpty（L）

初始条件：线性表L已存在。

操作结果：若L为空表，则返回true，否则返回false。

List Length（L）

初始条件：线性表L已存在。

操作结果：返回L中数据元素个数。

Get Elem（L，i，&e）(www.xing528.com)

初始条件：线性表L已存在，且1≤i≤List Length（L）。

操作结果：用e返回L中第i个数据元素的值。

LocateElem（L，e）

初始条件：线性表L已存在。

操作结果：返回L中第1个值与e相同的元素在L中的位置。若这样的数据元素不存在，则返回值为0。

Prior Elem（L，cur_e，&pre_e）

初始条件：线性表L已存在。

操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。

Next Elem（L，cur_e，&next_e）

初始条件：线性表L已存在。

操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。

ListInsert（&L，i，e）

初始条件：线性表L已存在，且1≤i≤List Length（L）＋1。

操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。

ListDelete（&L，i）

初始条件：线性表L已存在且非空，且1≤i≤List Length（L）。

操作结果：删除L的第i个数据元素，L的长度减1。

TraverseList（L）

初始条件：线性表L已存在。

操作结果：对线性表L进行遍历，在遍历过程中对L的每个结点访问一次。

｝ADT List