"""
线性表
定义是零个或多个数据元素的有限序列
线性表的长度是线性表元素的个数n(n>=0),当n=0时,就是空表
线性表的抽象数据类型
ADT 线性表(List)
Data:
线性表的数据对象集合为{a1,a2,...an},每个元素的数据类型均为DataType。
Operation
InitList(List):初始化操作,建立一个空的线性表L
ListEmpty(List):若线性表为空,返回True,否则就是False
ClearList(List):将线性表清空
GetElem(L,i,e):将线性表L中的第i个位置元素值返回e
LocateElem(L,e):确定与给定值e相等的元素,查找成功,则返回True,否则False
ListInsert(L,i,e):在线性表L中的第i个位置插入新元素e
ListLength(L):返回线性表L的元素个数
"""
"""
顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素
"""
class SqList():
def __init__(self):
self.list = []
self.length = 0
def ListEmpty(self):
return self.length == 0
def ClearList(self):
self.list = []
def GetElem(self, i, e):
if (self.length == 0) or (i < 1) or (i > self.length):
return False
e = self.data[i - 1]
return e
def LocateElem(self, e):
for elem in self.list:
if elem == e:
return True
return False
def ListInsert(self, i, e):
if (self.length == 0) or (i < 1) or (i > self.length):
return False
for j in range(self.length, i-1, -1):
self.list[j+1] = self.list[j]
data[i-1] = e
self.length += 1
return True
def ListLength(self):
return self.length
def ListDelete(self, i, e):
if (self.length == 0) or (i < 1) or (i > self.length):
return False
for j in range(i, self.length):
self.list[j-1] = self.list[j]
self.length -= 1
return False
"""
然后这是复杂度的计算
最好的情况,插入和删除最后一个位置,时间复杂度为O(1),最坏的情况呢,显然是O(n)
"""