线性表
线性表(List):由零个或多个具有相同特性的数据元素组成的有限序列。
- 序列:元素之间是有顺序的,第一个元素无前驱,最后一个元素无后继,其它每个元素都有且只有一个前驱和后继;
- 有限:在计算机中处理的对象都是有限的,无限的数列只存在于数学概念中。
在较复杂的线性表中,一个数据元素可以由若干个数据项组成。
ADT 线性表(List)
Data
线性表的数据对象集合为{a1, a2, a3, ……, 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
ADT List:
List(self) # 表构造操作,创建一个新表
is_empty(self) # 判断self是否为一个空表
len(self) # 获得self的长度
prepend(self, elem) # 将元素elem加入表中作为第一个元素
append(self, elem) # 将元素elem加入表中作为最后一个元素
insert(self, elem, i) # 将elem加入表中作为第i个元素,其他元素的顺序不变
del_first(self) # 删除表中的首元素
del_last(self) # 删除表中的微元素
del(self, i) # 删除表中的第i个元素
search(self, elem) # 查找元素elem在表中出现的位置,不出现时返回-1
forall(self, op) # 对表中的每个元素执行操作op