读书笔记数据结构c语言版4

2.1线性表

线性表（linear_list）是n个性质（类型）相同的数据元素的有限序列。（n≥0）

记为：（a1，…，ai-1，ai，ai+1，…，an）

ai（1≤i≤n）称为数据元素，下标表示该数据元素在线性表中的位置或序号。

元素个数n称为线性表的长度，当n=0时，称为空表。

表中ai-1领先于ai，称ai-1为ai的直接前驱元素，同理，称ai+1为ai的直接后继元素，容易知道a1没有前驱元素，an没有后继元素，表不能发生断裂，即不能缺项。

表中的数据元素随具体问题的不同而不同，既可以是字母，也可以是数字等等，其中由若干数据项所组成数据元素称为记录（record），含有大量记录的线性表也被称为文件（file）。

ADT线性表的定义如下：

ADTList{

数据对象：D={ai

ai∈ElemSet,i=1,2,……,n,n≥0}

数据关系：R1={ai-1,ai

ai-1,ai∈D,i=2,……,n}

基本操作：

InitList(L)

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

DestoryList(L)

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

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

ClearList(L)

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

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

ListEmpty(L)

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

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

ListLength(L)

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

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

GetElem(L,i,e)

初始条件：线性表L已存在，1≤i≤ListLength(L)+1。

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