一、定义
线性表是具有相同特性的数据元素的一个有限序列。
线性表:
- 由n(n≥0)个数据元素(结点)组成的有限序列。
- 线性表中数据元素是一对一的关系,每个结点最多有一个直接前驱,和一个直接后继
二、线性表的基本操作
1、初始化
InitList(&L)
- 构建一个空的线性表
2、销毁
DestroyList(&L)
- 初始条件:线性表L已经存在
- 操作结果:销毁线性表L
3、清除
ClearList(&L)
- 初始条件:线性表L已经存在
- 操作结果:将线性表L重置为空表
4、判断是否为空
ListEmpty(L)
- 初始条件:线性表L已经存在
- 操作结果:若线性表L为空表,则返回True;否则返回False
5、判断线性表长度
ListLength(L)
- 初始条件:线性表L已经存在
- 操作结果:返回线性表L中的数据元素个数
6、获取线性表中的某元素
GetElem(L,i,&e)
- 初始条件:线性表L已经存在,1<=i<=ListLength(L)
- 操作结果:用e返回线性表L中第i个数据元素的值
7、定位线性表中的某元素
GetElem(L,e,compare())
- 初始条件:线性表L已经存在,compare()是数据元素判定函数
- 操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0
8、求一个元素的前驱
PriorElem(L,cur_e,&pre_e)
- 初始条件:线性表L已经存在
- 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败。
9、求一个元素的后继
NextElem(L,cur_e,&next_e)
- 初始条件:线性表L已经存在
- 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败。
10、在线性表中插入一个元素
ListInsert(&L,i,e)
- 初始条件:线性表L已经存在,1<=i<=ListLength(L)+1
- 操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加一
11、在线性表中插入一个元素
ListInsert(&L,i,e)
- 初始条件:线性表L已经存在,1<=i<=ListLength(L)+1
- 操作结果:在L的第i个位置之前插入新的数据元素e,L的长度加一
12、在线性表中删除一个元素
ListDelete(&L,i,&e)
- 初始条件:线性表L已经存在,1<=i<=ListLength(L)
- 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减一
13、遍历线性表
ListTraverse(&L,visited())
- 初始条件:线性表L已经存在
- 操作结果:依次对线性表中每个元素调用visited()